Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
5. Aug 2013
Aber deine Wartezeiten hängen ja von der Uhrzeit ab und damit von deinem zurückgelegten Pfad. Die Kantengewichte in einem Graphen sind aber unabhängig vom Pfad.
Der Graph, den du dir mit deinem Dijkstra anschaust, ist eigentlich ein Teilgraph. Das funktioniert mit Dijkstra, aber z.B. mit Bellman-Ford würde es nicht funktionieren, weil dort alle Knoten/Kanten bekannt sein müssen. Zugegeben, bei...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
5. Aug 2013
Dein Algorithmus ist im Prinzip derselbe wie meiner, nur du hast es etwas anders dargestellt als ich. Was du machst, ist halt kein reiner Dijkstra-Algorithmus, weil bei Dijkstra die Kantengewichte fest sind. Was du also eigentlich machst, wenn du das Gewicht einer Kante „dynamisch berechnest“, ist, dass du einen neuen Knoten im Graphen erzeugst (der vorher nie berührt wurde, deshalb hätte er auch...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
5. Aug 2013
Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben. ;)
Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
5. Aug 2013
Hmm, aber es könnte doch sein, dass zuerst ein Zug kommt, der zwar in die richtige Richtung fährt, aber zwischendurch an zig Haltestellen hält („Bummelzug“), und 10 Minuten später eine wesentlich schnellere Direktverbindung kommt, mit der man schneller ankommt, obwohl man vorher länger gewartet hat. Hab jetzt nicht ganz verstanden, wie das bei dir berücksichtigt wird...
Vielleicht wolltest du...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
4. Aug 2013
Man will aber trotzdem nicht, dass das ganze System abschmiert, bloß weil der User eine Route berechnen will, die nicht existiert.
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...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
4. Aug 2013
Ja, das ist schon richtig, am Ende hat man natürlich einfach einen Graphen mit Kantengewichten. Ich persönlich finde es bloß anschaulicher, wenn man sich vorstellt, dass man kürzeste Wege auf einer zweidimensionalen Karte berechnet und die Kosten zwischen zwei Knoten der geometrischen Distanz entsprechen. In der Praxis muss natürlich der geometrisch kürzeste Weg nicht der schnellste sein, da man...
Forum: Algorithmen, Datenstrukturen und Klassendesign
Delphi
by Namenloser,
4. Aug 2013
Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).
