Einzelnen Beitrag anzeigen

Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#9

AW: Entwicklung einer Fahrplanauskunft

  Alt 4. Aug 2013, 22:54
Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.
Nö. Dann gibt es einfach keine Lösung.
Man will aber trotzdem nicht, dass das ganze System abschmiert, bloß weil der User eine Route berechnen will, die nicht existiert.
Bei der Graphentraversierung markiert man die besuchten Knoten, dann passiert das nicht.
Hier ist der Graph aber unendlich und man findet (in zeitlicher Dimension) an jedem Knoten einen weiteren Knoten, der nicht zum Ziel führt.

Jedes Stehen eines Busses an einer Haltestelle ist eigentlich ein Knoten. Man kann sich dann an jedem Knoten jeweils dafür entscheiden, ob man mit dem Bus zur nächsten Haltestelle (1. adjazenter Knoten) fährt, oder ob man auf den nächsten Bus wartet (2. adjazenter Knoten). Nun kann man aber beliebig lange an der Haltestelle stehen und darauf warten, dass ein Bus kommt, der einen in Richtung des Ziels bringt. Wenn ein solcher aber niemals kommt, dann sitzt man bei einer naiven Implementierung in einer Endlosschleife...

Geändert von Namenloser ( 4. Aug 2013 um 23:01 Uhr)
  Mit Zitat antworten Zitat