Algorithmus, um den kürzesten Weg zu finden, mit Hindernissen
Habe ich eine Sammlung von Punkten, das entspricht einem raster, ich bin auf der Suche nach einem Algorithmus, der bekommt von mir die kürzeste Entfernung zwischen Punkt A und B.
Der Fang jeder Stelle (ohne A und B) können ein Hindernis versperren den Weg, und so muss abgemildert werden. Der Pfad kann sich nicht bewegen in der diagonalen.
Für jemand anderes suchen, lösen diese Art von problem, fand ich diese Hinweise sehr nützlich zu sein:
http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html
- Nettes problem! Wo sind Sie stecken?
- Dijkstra wäre der normale Weg zu gehen en.wikipedia.org/wiki/Dijkstra's_algorithm
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies ist ein ausgezeichneter Ort, um zu verwenden, die A* - Suchalgorithmus, einen heuristischen Suchalgorithmus, der findet optimale Pfade zwischen den Punkten sehr schnell, selbst wenn es Hindernisse vorhanden. Die Idee ist die Umwandlung von raster-in ein Grafik, wobei jede Zelle in dem Gitter ein Knoten und eine Kante zwischen zwei benachbarten Zellen, die nicht behindert voneinander. Sobald Sie diese Grafik, die Antwort, die du suchst, ist der kürzeste Pfad im Graphen vom Startknoten zum Zielknoten.
Damit Eine* benötigen Sie eine Heuristik-Funktion, die "Vermutungen" die Entfernung von jeder Stelle auf dem raster, um das Ziel-Platz. Eine gute Heuristik für diese wäre die Verwendung die Manhattan-Distanz zwischen den beiden Punkten.
Wenn Sie suchen für eine einfachere, aber immer noch äußerst effizienten Algorithmus für die Suche nach dem kürzesten Pfad, prüfen, Blick in die Der Dijkstra-Algorithmus, was gedacht werden kann, als eine einfachere version von Einem*. Es ist ein bisschen langsamer als A* ist, aber noch läuft extrem schnell und garantiert eine optimale Antwort.
Hoffe, das hilft!
Dies ist ein einfaches problem, das gelöst werden kann mit der Breite zum Ersten mal Suche
Ich glaube, dass das gegebene problem kann gelöst werden, indem die Breite First Search(BFS) wie bereits erwähnt. Die Gründung einer problem-Anweisung ist wichtig. Also lassen Sie uns beschreiben Sie das problem, und dann bewegen wir uns an der Lösung Teil.
Problem Beschreibung:
Sind Sie verantwortlich für die Vorbereitung einer kaufte vor kurzem viel für eine von einer
neue Gebäude. Die Menge ist bedeckt mit Gräben und verfügt über ein einzelnes Hindernis, das
muss abgenommen werden, bevor das Fundament vorbereitet werden können für das Gebäude.
Die Abriss-Roboter muss das Hindernis entfernen, bevor ein Fortschritt gemacht werden kann, auf
die Gebäude.
Schreiben Sie einen Algorithmus zur Bestimmung des mindestabstands erforderlich, für die
Abbruch-Roboter um das Hindernis entfernen.
Annahmen:
immer flach und bewegen kann, einen block nach oben, unten, rechts oder Links gleichzeitig.
Hindernis 9.
Ausgabe:
Eine Ganzzahl zurück, die die minimale Distanz Durchlaufen, um die zu entfernen
Hindernis else return -1.
Lösung