Das Thema "Pathfinding" ist hochinteressant und nicht so trivial, wie
allgemein angenommen. Dennoch kann es in seiner einfachsten Methode
(BruteForce) auf minimalen Aufwand reduziert werden. Soll heissen:
Kleiner Code, aber hoher Rechenaufwand.
Z.B. 4 Punkte stehen in Verbindung zueinander: A B C D
Alle Informationen (Entfernung) sind bekannt:
A/B=100 Km
A/C=80
A/D=50
B/C=60
B/D=80
C/D=90
Aufgabenstellung: Alle Punkte auf dem kürzesten Wege miteinander
verbinden.
Die BruteForce-Methode bildet in diesem Fall alle Variationen (nicht Kombinationen!!
Irgendwie verfolgt mich dieses Thema, guckst du
hier):
4! (bedeutet Fakultät von 4) = 1*2*3*4 = 24
und berechnet die jeweilige Gesamtentfernung für jede dieser
Variationen. Die Variation mit der kleinsten Gesamtentfernung ist das
gesuchte Ergebnis.
Leichter gesagt als getan (für den Computer). 4 oder 8 oder 10 Ziele so
zu routen ist ja noch ein Kinderspiel (8!=40320 Variationen, 10!=3628800).
Sobald es aber mehr Varianten sind (wie hier: 50! = 3*10 hoch 63) gehen
jedem GHz Bolzen die Lötstellen auf.
Code: Alles auswählen
OpenConsole()
Dim POI(4,4) ; Points of Interest's
a=1 ; Ort A
b=2 ; Ort B
c=3 ; Ort C
d=4 ; Ort D
; die Entfernungen der Orte zueinander
; in eine Tabelle eintragen
POI(a,b)=100: POI(b,a)=100
POI(a,c)=80 : POI(c,a)=80
POI(a,d)=50 : POI(d,a)=50
POI(b,c)=60 : POI(c,b)=60
POI(b,d)=80 : POI(d,b)=80
POI(c,d)=90 : POI(d,c)=90
MinKm =100+60+90 ; vorbelegen mit Entfernung Route "ABCD"
Route$="ABCD" ; beste bisherige Route
; Routing, Bildung aller Variationen
For V1=a To d
For V2=a To d
For V3=a To d
For V4=a To d
; um zu verhindern, dass 2x der gleiche Ort angefahren wird...
If V1=V2 Or V1=V3 Or V1=V4 Or V2=V3 Or V2=V4 Or V3=V4
Else
AktEntfernung=POI(V1,V2)+POI(V2,V3)+POI(V3,V4)
If AktEntfernung<MinKm
; neue, kürzere Route gefunden
MinKm=AktEntfernung
Route$=Chr(64+V1)+Chr(64+V2)+Chr(64+V3)+Chr(64+V4)
EndIf
EndIf
Next V4
Next V3
Next V2
Next V1
PrintN("kuerzeste Route: "+Route$+" mit "+Str(MinKm)+" Km")
Input()
CloseConsole()
Auf dem Gebiet der Schachprogrammierung (aber nicht nur hier) gibt es
div.Methoden, um die Folgen des BruteForce-Prozess einzudämmen.
Stichwort: Alpha/Beta. Alpha/Beta ist, wenn man es einmal begriffen hat,
recht einfach anzuwenden (wer mehr wissen möchte ->Google).
Um die Funktion von Alpha/Beta in einem Satz zu beschreiben: Wenn ich
an einem bestimmten Punkt feststelle, dass das Teilergebnis bereits
schlechter als das bisherige beste (Gesamt-)Ergebnis ist, dann kann ich
die Berechnung bereits an dieser Stelle abbrechen und wieder hierarchisch
eine Iterationsebene (bei der Bildung der Variationen) zurückgehen.
einen Routenplaner erstellen 
... 
