| |
Effiziente Ermittlung
optimaler Wege durch ein neues 2-Wurzel-Verfahren
Das neue innovative
Wegebestimmungsverfahren basiert auf der simultanen (parallelen) Entwicklung
zweier "Wegeerweiterungswellen". Die eine Welle startet konventionell im
Startpunkt s in Kantenrichtung der aus s auslaufenden Kanten (Ermittlung eines
"Optimal Path graph OPG"). Die andere Welle startet im Zielpunkt t und erweitert
sich entgegen der Kantenrichtung der in t einlaufenden Kanten ("Reverse Optimal
path graph ROPG). Treffen beide Wellen aufeinander, ist der kürzeste Weg
gefunden (stark vereinfacht ). Der entsprechende Algorithmus A-2
der
O&S Consultancy
schlägt alle existierenden optimalen Wege Algorithmen, sofern Start s und Ziel t
in der digitalen Karte nicht über die Hälfte der Kartenbreite (ausgedrückt durch
die Anzahl der Kanten eines optimalen Weges von einem Rand zum anderen).
hinausgeht, siehe Fig. unten. Dies ist für die überwiegende Anwendung aller
Applikationen auf Basis digitaler Karten der Fall.
|
|
|