2

私はゆっくりと VBA を学んでおり、自分自身を助けるために巡回セールスマン問題のバージョンに取り組んでいます。この特定のケースでは、セールスマンは 2 地点間で可能な限り長いルートを選択して、都市から都市へと移動します。ルートは、デカルト座標とユークリッド距離を使用して計算されます。この特定の例では、以下の座標の表があります。

City X  Y
1   2   4
2   5   3
3   6   1
4   2   3
5   1   2
6   3   6
7   3   8
8   2   6
9   7   6
10  3   3

これに対する私のコードは以下の通りです。

Option Explicit

Sub newTSP()
    Dim nCities As Integer
    Dim distance() As Single
    Dim wasVisited() As Boolean
    Dim route() As Integer
    Dim totalDistance As Single
    Dim step As Integer
    Dim nowAt As Integer
    Dim nextAt As Integer
    Dim minDistance As Single 'TODO remove this
    Dim maxDistance As Single 'just to use in the distance loop
    Dim i As Integer, j As Integer
    Dim x1 As Integer, x2 As Integer, y1 As Integer, y2 As Integer
    Dim temp_dist As Single
    Dim coords As Range 'this is the table of coordinates

'my Euclidean distance array
    'count number of cities in the cartesian coordinates matrix
    nCities = Range(TSP.Range("a3").Offset(1, 0), TSP.Range("a3").Offset(1, 0).End(xlDown)).Rows.Count
    'now that we know the number of cities, redimension distance array
    ReDim distance(1 To nCities, 1 To nCities)
    'take the coordinates as a range
    Set coords = Range(TSP.Range("a3"), TSP.Range("a3").End(xlDown)).Resize(, 3)
    'put in the first arm of the matrix
    TSP.Range("e3") = "City"
    TSP.Range("e3").Font.Bold = True
    TSP.Range("e1") = "Distance Matrix"
    TSP.Range("e1").Font.Bold = True
    With TSP.Range("e3")
    For i = 1 To nCities
        .Offset(i, 0) = i
        .Offset(i, 0).Font.Bold = True
    Next
    'second arm of the matrix
    For j = 1 To nCities
        .Offset(0, j) = j
        .Offset(0, j).Font.Bold = True
    Next
    'fill it in with distances
    For i = 1 To nCities
        For j = 1 To nCities
            'the default value is 0
            If i = j Then
                TSP.Range("e3").Offset(i, j) = 0
            'otherwise look for euclidean distance
            Else
            'search for the coordinates for each value
                x1 = WorksheetFunction.VLookup(i, coords, 2, False) 'x of i
                y1 = WorksheetFunction.VLookup(i, coords, 3, False) 'y of i
                x2 = WorksheetFunction.VLookup(j, coords, 2, False) 'x of j
                y2 = WorksheetFunction.VLookup(j, coords, 3, False) 'y of j
                temp_dist = Sqr(((x1 - x2) ^ 2) + ((y1 - y2) ^ 2))
                TSP.Range("e3").Offset(i, j) = temp_dist
            End If
        Next
    Next
    End With

    'Array where route will be stored. Starts and ends in City 1
    ReDim route(1 To nCities + 1)
    route(1) = 1
    route(nCities + 1) = 1

    'Boolean array indicating whether each city was already visited or not. Initialize all cities (except City 1) to False
    ReDim wasVisited(1 To nCities)
    wasVisited(1) = True
    For i = 2 To nCities
        wasVisited(i) = False
    Next

    'Total distance traveled is initially 0. Initial current city is City 1
    totalDistance = 0
    nowAt = 1

    'Find at each step the FARTHEST not-yet-visited city
    For step = 2 To nCities
        'initialize maxDistance to 0
        maxDistance = 0
        For i = 2 To nCities
            If i <> nowAt And Not wasVisited(i) Then
                If distance(nowAt, i) > maxDistance Then
                    nextAt = i
                    maxDistance = TSP.Range("e3").Offset(nowAt, i)
                    'TODO: does this distance call work with the new table format?
                End If
            End If
        Next i
        'store the next city to be visited in the route array
        route(step) = nextAt
        wasVisited(nextAt) = True
        'update total distance travelled
        totalDistance = totalDistance + maxDistance
        'update current city
        nowAt = nextAt
    Next step

    'Update total distance traveled with the distance between the last city visited and the initial city, City 1.
    totalDistance = totalDistance + distance(nowAt, i) 'TODO: does this call work? Original had it as 1, not i.

    'Print Results
    With TSP.Range("A3").Offset(nCities + 2, 0)
        .Offset(0, 0).Value = "Nearest neighbor route"
        .Offset(1, 0).Value = "Stop #"
        .Offset(1, 1).Value = "City"

        For step = 1 To nCities + 1
            .Offset(step + 1, 0).Value = step
            .Offset(step + 1, 1).Value = route(step)
        Next step

        .Offset(nCities + 4, 0).Value = "Total distance is " & totalDistance
    End With
End Sub

私の行「wasVisited(nextAt) = True」で問題が発生しているようです。ここでは、添え字が範囲外になります。添え字は、i = 1 から nCities の範囲内にしっかりと収まっている必要があります。よくわかりません私の問題はどこから来ているのですか?

4

1 に答える 1