Betrachten wir ein einfaches Gitter, bei dem jeder Punkt mit höchstens 4 anderen Punkten verbunden ist (Nord-Ost-West-Süd-Nachbarschaft).
Ich muss ein Programm schreiben, das die minimale Route von einem ausgewählten Startpunkt zu cualquier von Zielpunkten, die miteinander verbunden sind (es gibt eine aus Zielpunkten bestehende Route zwischen zwei beliebigen Zielen). Natürlich kann es Hindernisse auf dem Gitter geben.
Meine Lösung ist ganz einfach: Ich verwende den A*-Algorithmus mit einer variablen heuristischen Funktion h(x) - der Manhattan-Distanz von x zum nächstgelegenen Zielpunkt. Um den nächstgelegenen Zielpunkt zu finden, muss ich eine lineare Suche durchführen (in O(n), wobei n die Anzahl der Zielpunkte ist). Meine Frage lautet: Gibt es eine effizientere Lösung (heuristische Funktion), um dynamisch den nächstgelegenen Zielpunkt zu finden (mit einer Zeit < O(n))?
Oder ist A* vielleicht kein guter Weg, um dieses Problem zu lösen?
