Laden...

Weg von Punkt A zu Punkt B finden (in einem Graphen)

Erstellt von DeZio vor 12 Jahren Letzter Beitrag vor 12 Jahren 1.050 Views
DeZio Themenstarter:in
76 Beiträge seit 2008
vor 12 Jahren
Weg von Punkt A zu Punkt B finden (in einem Graphen)

Hallo Community,

ich brauche einen Gedankenschub für einen Algorithmus.

Ich habe in einer Datenstuktur Punkte (Rot, Gelb) mit X, Y und ID eingetragen. Zudem ist notiert, welche ID mit welcher ID (blauer Weg) verknüpft ist (bidirektional, keine Inkonsistenzen).
Nun möchte ich gerne einen Weg von Punkt A (Gelb) nach Punkt B (Gelb) finden, der nur über Wegpunkte (Rot) läuft. Dies ist nur ein Kartenausschnitt, sodass es natürlich nicht nur 2 Start/Endpunkte gibt.
Da ich das ganze ich PHP zu realisieren habe, wird mir in der Theorie kein Threading helfen.

Habt Ihr Ideen?

Grüße Dennis Z.

T
415 Beiträge seit 2007
vor 12 Jahren

Als guten Einstieg empfehle ich dir da den A* Algorithmus. Versuche dich darüber mal in das Thema der Wegfindung einzulesen. Sollten sich dann dazu noch weitere Fragen ergeben, dann kannst diese ja hier stellen.

A*-Algorithmus

DeZio Themenstarter:in
76 Beiträge seit 2008
vor 12 Jahren

Danke. Das wird mir erstmal weiterhelfen! 😃

M
29 Beiträge seit 2011
vor 12 Jahren

Der wohl bekannteste Algorithmus ohne Heuristik ist der gute alte Dijkstra. Würd ich persönlich bevorzugen - finde ihn simpler als A*

Dijkstra-Algorithmus

49.485 Beiträge seit 2005
vor 12 Jahren

Hallo MrHiggins,

da A* direkt auf dem Dijkstra-Algorithmus aufbaut und lediglich die Reihenfolge beeinflusst, in der die Knoten besucht werden und da es fertige Implementierungen oder zumindest "fertigen" Psuedo-Code gibt, ist A* gegenüber dem Dijkstra-Algorithmus nun wirklich nicht die Klippe. Da A* in den meisten Fällen - und gerade bei größeren Entfernungen - mit deutlich weniger Versuchen ans Ziel kommt, ist er normalerweise der Algorithmus der Wahl.

herbivore

799 Beiträge seit 2007
vor 12 Jahren

Der große Vorteil vom A* ist, dass der Algorithmus mehr oder weniger als ein Framework für Wegesuchen verstanden werden kann.

Denn je nachdem wie du deine Bewertungsfunktionen programmierst, kannst du steuern wie die Suche aussieht.

Ob du eine Breitensuche, Tiefensuche, Dijkstra oder eine Suche speziell an das vorliegende Problem angepasst daraus machst liegt in deinen Händen.

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl
M
29 Beiträge seit 2011
vor 12 Jahren

Um es aber erstmal zu verstehen, finde ich es sinnvoller den Dijkstra anzuschauen, und dann auf den A* zu erweitern. Natürlich ist der A* sinnvoller - aber wenn der Threadsteller es nich gleich versteht kann er ja mit der Basisvariante Dijkstra anfangen.

So war das gemeint:-)