|
Guten tag zusammen.
Ich habe folgende Aufgabe zu lösen:
Auf einer Platine sollen Bohrungen plaziert werden. Die Koordinaten der Bohrungen sind gegeben. Es soll nun der Verfahrweg des Bohrers berechnet werden, damit dieser alle Bohrungen bohren kann, wobei der den kürzesten Weg gehen soll.
Für die Punkte habe ich ich bereits eine Distanzmatrix aufgestellt. Diese zeigt die Distanzen zwischen den einzelnen Bohrungen. Das klappt soweit gut.
Die sieht so aus: (auf der x und y-Achse sind jeweils die Punkte aufgetragen. Als Bsp: 1.Feld: Die Distanz von Punkt 1 zu Punkt 1 ist 0. Das Feld darunter oder auch rechts daneben: Die Distanz von Punkt 1 zu Punkt 2 oder von Punkt 2 zu Punkt1 ist 24)
|
0 |
24 |
6 |
20 |
4 |
20 |
10 |
20 |
18 |
18 |
|
24 |
0 |
30 |
5 |
28 |
5 |
34 |
4 |
6 |
7 |
|
6 |
30 |
0 |
26 |
2 |
26 |
4 |
26 |
24 |
24 |
|
20 |
5 |
26 |
0 |
24 |
10 |
30 |
6 |
6 |
2 |
|
4 |
28 |
2 |
24 |
0 |
24 |
6 |
24 |
22 |
22 |
|
20 |
5 |
26 |
10 |
24 |
0 |
30 |
4 |
4 |
12 |
|
10 |
34 |
4 |
30 |
6 |
30 |
0 |
30 |
28 |
28 |
|
20 |
4 |
26 |
6 |
24 |
4 |
30 |
0 |
2 |
8 |
|
18 |
6 |
24 |
6 |
22 |
4 |
28 |
2 |
0 |
8 |
|
18 |
7 |
24 |
2 |
22 |
12 |
28 |
8 |
8 |
0 |
Jetzt soll ich zunächst mit Hilfe der BruteForceMethode den kürzesten Verfahrweg des Bohrers berechnen. Und da beginnen die Probleme. Ich habe die Tabelle für die Distanzen schon in ein Array eingelesen aber ich finde keine Möglichkeit, dass er mir alle Kombinationen für die Distanzen berechnet. Dabei interessiert mich letztlich auch nur die kürzeste. Also nur die soll am Ende ausgegeben werden.
Die Reihenfolge der Punkte ist unwichtig und kann außer Acht gelassen werden. Genauso sind Distanzen mit 0 unwichtig. Diese sind ja die Hauptdiagonale. Also Punkt1 zu Punkt, Punkt2 zu Punkt2 usw.
Überlegungen habe ich schon gemacht, wenn man es als Beispiel jetzt auf 3 Punkte beschränkt:
Weg von Punkt1 zu Punkt2 zu Punkt3: 24 +30
Weg von Punkt2 zu Punkt1 zu Punkt3: 24 +6 -----> kürzesterWeg
Weg von Punkt1 zu Punkt3 zu Punkt2: 30 +6
Ich füge euch mal meinen bisherigen Code dazu. Ich glaube aber daran ist nicht viel richtig.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | Function PermutationArray(vntdata, k, m)
Worksheets("Distanzmatrix").Range("A1").Activate
Do Until ActiveCell.Value = ""
Z = Z + 1
Cells(Z, 1).Activate
Loop
Dim perArray As Variant
Dim perRng As Range
Dim perWks As Worksheet
If k = (Z - 2) Then
zeile = Cells(65536, 1).End(xlUp).Row
If Cells(1, 1) <> "" Then zeile = zeile + 1
For t = 1 To (Z - 2)
For i = 1 To (Z - 2)
If vntdata(i, t) <> 0 Then
Cells(zeile, i) = vntdata(i, t)
End If
Next
Next
Else
For t = m To (Z - 1)
For i = k To (Z - 1)
x = vntdata(i, t)
vntdata(i, t) = vntdata(k, m)
vntdata(k, m) = x
Call PermutationArray(vntdata, k + 1, m + 1)
Next
Next
End If
End Function
Als kleine Erklärung was ich mir bei dem Gewirr gedacht habe:
vntdata ist das Array, welches die Daten der Distanzmatrix enthält
Mit Hilfe der beiden ineinanderverschachtelten Schleifen dachte ich mir mich durch das Array zu navigieren.
Also durchlaufen der x und y- Koordinaten. Das was da ausgegeben wird ist aber einerseits falsch und andererseits
gibt das mir alle verschiedenen Reihenfolgen der Punkte aus. Also z.B Punkt 1-2-3-4-5-6-7-8-9-10 oder
Punkt 1-2-3-4-5-6-7-8-10-9 usw. Das bringt mir aber nichts. Ich habe mich also völlig verrannt.
|
Ich habe mir hier ausgeben lassen was der Algorithmus da macht. Das war als Hilfe für mich. Allgemein ist das aber unwichtig.
Letztlich könnt ihr diesen Code also in die Tonne kloppen.
Ich suche jetzt schon seit mehreren Tagen nach ähnlichen Problemen mit denen ich was anfangen kann. Allerdings war ich erfolgslos. Ich hoffe jetzt auf euch, dass ihr mir weiterhelfen könnt. Am wichtigsten wäre mir herauszufinden, was ich eingeben muss um die verschienenen Kombinationen der Punkte zu durchlaufen und mir die kürzeste Distanz und so die Kombination der Punkte auszugeben.
Versucht es nach Möglichkeit etwas einfach zu halten, da ich nicht zu geübt bin mit programmieren.
Bitte helft mir.
|