Guten Abend,
Ich arbeite zur Zeit am Traveling Salesman Problem, über das ich schon früher ein Thema erstellt habe.
Nachdem ich nun 5 Städte erfolgreich abgeliefert habe, sagte mein Professor mir, dass ich doch mal 10 nehmen sollte.
Ich habe mir nun Gedanken gemacht und bin dabei auf die Website von R.Hirte gestoßen:
http://rhirte.de/vb/travsales.htm
Das habe ich als Innovation genommen, um eine etwas abgeänderte Form über Zufallszahlen zu bekommen - allerdings mit definierten Städten, Herr Hirte nimmt einfach irgendwelche willkürlichen Städtedaten.
Das sieht bisher so aus:
Public Sub Rechnung6St()
Dim n As Integer
Dim a, b, c, d, e, f As Variant
Dim arrX, arrY, arrSt As Range
Dim arrBX, arrBY, arrBSt As Range
Dim ax, ay, bx, by, cx, cy, dx, dy, ex, ey, fx, fy As Single
Dim tmp As Double
Dim Zeile As Long
Dim StMax As Integer
Dim str(1000, 1000) As Single
Dim Weg As Single, wegVor As Single
Dim diff As Double
Dim x, y As Integer
Dim StA As Long, StB As Long, StC As Long, StD As Long, StE As Long, StF As Long
a = Me.comSt1
b = Me.comSt2
c = Me.comSt3
d = Me.comSt4
e = Me.comSt5
f = Me.comSt6
[...]
With Worksheets("Daten")
Set arrSt = .Range("B7:B60") 'Große Daten in Arrays packen, um Zugriff zu erleichtern
Set arrX = .Range("D7:D60")
Set arrY = .Range("E7:E60")
End With
[...]
With Worksheets("Daten")
Set arrBSt = .Range("K100:K105") 'Zugriff erleichtern
Set arrBX = .Range("L100:L105")
Set arrBY = .Range("M100:M105")
End With
'Berechne Abstandsmatrix
StMax = 6
For x = 1 To StMax
For y = 1 To StMax
str(x, y) = Sqr((arrBX(x) - arrBX(y)) ^ 2 + (arrBY(x) - arrBY(y)) ^ 2)
Sheets("Matrix").Cells(x, y).Value = str(x, y)
Next y
Next x
wegVor = 100000
(Do)
Do
Randomize
StA = 1
StB = Int(6 * Rnd + 1)
StC = Int(6 * Rnd + 1)
StD = Int(6 * Rnd + 1)
StE = Int(6 * Rnd + 1)
StF = Int(6 * Rnd + 1)
Loop Until (hier steht noch ein langer text, der der schleife sagt, dass die stX-werte sich nie gleichen dürfen, der passt aber wegen der größer / kleiner zeichen nicht ins forum)
Weg = str(StA, StB) + str(StB, StC) + str(StC, StD) + str(StD, StE) + str(StE, StF) + str(StF, StA)
If Weg kleiner als wegVor Then
wegVor = Weg
End If
(Loop Until....)
Das sind die wichtigen Stellen.
Das Do und das Loop Until in Klammern sind die Stellen, wo ich eine weitere Schleife einbauen möchte.
Im optimalfall soll ja "Weg" minimal werden. Ich habe allerdings keine Ahnung, wie ich dem Programm das sage, da es ja keine festen Kombinationen durchgeht, sondern zufällig die Städte abgrast und dann das beste nehmen soll.
In der vorigen version konnte ich ja aussuchen, ob er tmp behalten soll oder ersetzen, aber hier in der Schleife muss ich ihm ja einen festen Wert als Ausgabe setzen, wann er aufhören soll... Da die Städte aber variabel sind, habe ich ja keine festen Werte dafür.
Evtl könnte man die Schleife auch 1000 mal laufen lassen, dann stehen die Chancen gut, den kürzesten Weg gefunden zu haben.
Allerdings hoffe ich, eine gute Alternative zu finden.
Danke fürs Lesen
Alex