Wegfindung: Wie funktioniert sowas (theoretisch)

[everdream]

Bei Dijkstra reicht es doch die Straßen, die von der Kreuzung, an der man sich befindet, abgehen und die Straßen, in denen man schon war, zu kennen, oder sehe ich das grade falsch?

[yankee]

Zitat von everdream:

Bei Dijkstra reicht es doch die Straßen, die von der Kreuzung, an der man sich befindet, abgehen und die Straßen, in denen man schon war, zu kennen, oder sehe ich das grade falsch?

Ja, das siehst du falsch. Es könnte schliesslich sein, dass du in eine Sackkasse läufst oder sowas. Das ist dann garantiert nicht der kürzeste Weg. Um den kürzesten Weg zu finden brauchst du in jedem Fall Kenntnis vom ganzen Graphen.
Mit A* wird das möglicherweise gehen, da A* mit Heuristik arbeitet. Das ist wesentlich schneller, liefert aber nicht unbedingt den kürzesten Weg. Aber so genau weiss ich das auch nicht, da ich mich mit A* nie genau beschäftigt habe .

[everdream]

Dijkstra liefert doch von einem festen Starpunkt aus den kürzesten Weg zu jedem Knoten. Sackgassen bilden da keine Ausnahme. Und dabei geht der Algorithmus so vor, dass von einem Knoten aus alle Abzweigungen nimmt (nur die von der aktuellen Kreuzung ausgehenden Straßen) und wenn er eine kürzere Verbindung zu einem Knoten findet, dann wird die alter Verbindung (also ein schon bekannter Weg) gelöscht.

Dijkstra funktioniert meiner Meinung nach in einem Labyrinth.

[yankee]

Ja, das ist schon richtig. Wenn ich von der Frage ausgehe "wie komme ich am sichersten aus einem Lapyrinth", dann gehe ich davon aus, dass du dich in einem Lapyrinth befindest, dass du nicht kennst, sprich zu dem du keine Karte hast um dir den Weg zu berechnen.
Um Dijkstra anwenden zu könenn müsstest du dann erstmal das komplette Lapyrinth abgehen. Das Karte zeichenen und Weg berechnen könntest du dann natürlich in einem machen und dir somit einen Arbeitsschritt sparen, aber vermutlich hast du den Ausgang gefunden, bevor du dir sicher sein kannst den kürzesten Weg von deinem Ausgangspunkt gefunden zu haben. Da du dich jedoch ständig im Labyrinth fortbewegen musst, ändert sich dein Startknoten quasi die ganze Zeit und am Ende interessierst du dich sowieso nichtmehr für den Weg zu deinem ehemaligen Startknoten...

[everdream]

Den sichersten/kürzesten Weg aus einem Labyrinth kannst du mit keinem Algo sicher finden, ohne z.B. in Sackgassen zu laufen oder vershciedene Wege zu probieren. Das kann weder ein PC, noch ein Mensch. Und wenn ich richtig informiert bin, kannst du mit einer heuristischen Methode ohne globale Karte auch nichts anfangen,...