Routenplanung programmieren
-
Sers Leute,
ich weiß zwar nicht, ob das oder das Java-Forum das richtige ist, aber ich schreibs mal hier rein.
Ich bin grad dabei, für ein Schulprojekt (unter anderem) eine Routenplanung zu erstellen.
Soll nichts allzu Großes werden, nur für das Schulgebäude - also in etwas "Ich bin in Raum A, wie komm ich am schnellsten nach Raum B".Hab mich schon ein bisschen umgeschaut und hab jetzt zwei Alternativen:
1. A*- Pathfinding (http://www.blitzbase.de/artikel/path_1.htm)
2. Graphentheorie (wobei ich da, anders als beim Pathfinding, noch keine konkrete Idee für die Umsetzung in Java hab).Das Ganze soll auf einer Website laufen, darum dachte ich an ein Java-Servlet.
Programmiererfahrung hab in C, C++ und Java, hab aber auch fast ein Jahr nichts mehr gemacht, bin daher aus der Übung.Meine Fragen sind jetzt: Was (Pathfinding oder Graphentheorie) ist am einfachsten zu implementieren? Gibt es vielleicht bereits Routenplanungsprogramme, bei denen man nur die Umgebungsdaten eingeben muss (würde mir eine Menge Arbeit ersparen)? Wenn nicht, gibt es Tutorials, wie man eine Routenplanung in Java erstellt?
Ich weiß, viele Fragen. Ich hoffe auf viele Antworten.
MfG
Zoidberg
-
Da vergleichst Du grad Äpfel mit Birnen. Graphentheorie kann man nicht implementieren. Es handelt sich um eine Theorie. Genausowenig wie Du eben die Relativitätstheorie implementieren kannst. A* ist ein konkreter Wegfindungsalgorithmus. Der ist dem Bereich Graphentheorie zuzuordnen, ist aber beileibe nicht der einzige Routenplanungsalgorithmus.
Graphentheorie ist also auf jeden Fall die richtige Ecke zum suchen. Ob Du nun konkret den A* einsetzen willst oder was anderes solltest Du noch überlegen.
A* ist sicher nicht das schlechteste. Damit kann man kleine bis mittlere Aufgaben sehr effizient lösen. Für Routenplanung in Deutschland/Europa wäre er ein bissel schwach, aber für ein Schulgebäude reicht's allemal.
-
Für ein Schulgebäude sollte auch ein ganz normaler Dijkstra reichen.
Eine wichtige Entscheidung sollte sein, wie du den Graphen repräsentierst, auf dem der Algorithmus laufen läßt. Denn mit einem Graphen hast du auf jeden Fall zu tun. Ob explizit oder implizit.
-
Dann hab ich da was durcheinandergebracht.
A* wollt ich deshalb nehmen, weil ich gelesen hab, dass der Algorithmus einer der einfacheren is.Und danke für die schnellen Antworten.
-
KönigZoidberg schrieb:
Dann hab ich da was durcheinandergebracht.
A* wollt ich deshalb nehmen, weil ich gelesen hab, dass der Algorithmus einer der einfacheren is.Das ist wahr. Aber er ist auch ziemlich schnell. Dijkstra ist noch etwas einfacher. Vielleicht implementierst Du zuerst den und schaust dann, ob der dir genügt. Wenn nicht ist es nicht schwer den zu nem A* umzubauen.
-
Seh mich eh schon nach dem Dijkstra um.
Welchen Aufwand hat man als (fortgeschrittener
) Anfänger bei sowas in etwa zu erwarten?Nur grob geschätzt, also Tage, Wochen....
-
KönigZoidberg schrieb:
Seh mich eh schon nach dem Dijkstra um.
Welchen Aufwand hat man als (fortgeschrittener ) Anfänger bei sowas in etwa zu erwarten?Nur grob geschätzt, also Tage, Wochen....
Drei bis vier Stunden.
-
Jester schrieb:
A* ist sicher nicht das schlechteste. Damit kann man kleine bis mittlere Aufgaben sehr effizient lösen. Für Routenplanung in Deutschland/Europa wäre er ein bissel schwach, aber für ein Schulgebäude reicht's allemal.
Ich schreibe gerade Diplomarbeit in diesem Bereich und mich würde mal interessieren, was du für große Suchräume als bessere Lösung siehst...
Meine Erachtens nach ist der A*-Algorithmus das schnellste bekannte Graphensuchverfahren, auch wenn natürlich alles mit seiner Heuristik steht oder fällt. Um mit großen Suchräumen umzugehen bietet sich ein mip-mapping an, so hat man auch zwischen bestimmten Knoten in darunterliegenden Schichten eine exakte Heuristik. Wie viel besser (von der Skalierbarkeit her) soll es denn noch werden?
Ponto schrieb:
KönigZoidberg schrieb:
Seh mich eh schon nach dem Dijkstra um.
Welchen Aufwand hat man als (fortgeschrittener ) Anfänger bei sowas in etwa zu erwarten?Nur grob geschätzt, also Tage, Wochen....
Drei bis vier Stunden.
Das schaffst du auf jeden Fall an einem Tag, auch wenn du den Algorithmus noch nicht kennst. Die Frage ist eher, was du schon hast. Du musst ja irgendwie den Graphen repräsentieren, bevor du darauf suchen kannst. Der Algorithmus selber ist einfach.
-
Was die "Karte angeht", hab ich noch nix. Ich dachte mir, ich schreib erstmal das Programm und teste, ob ich den Algorithmus richtig umgesetzt hab.
Immerhin muss ich mir ja dann die Pläne der Schule besorgen und die ganzen Daten einhacken, das will so lang wie möglich vermeiden.
-
Optimizer schrieb:
Jester schrieb:
A* ist sicher nicht das schlechteste. Damit kann man kleine bis mittlere Aufgaben sehr effizient lösen. Für Routenplanung in Deutschland/Europa wäre er ein bissel schwach, aber für ein Schulgebäude reicht's allemal.
Ich schreibe gerade Diplomarbeit in diesem Bereich und mich würde mal interessieren, was du für große Suchräume als bessere Lösung siehst...
Meine Erachtens nach ist der A*-Algorithmus das schnellste bekannte Graphensuchverfahren, auch wenn natürlich alles mit seiner Heuristik steht oder fällt. Um mit großen Suchräumen umzugehen bietet sich ein mip-mapping an, so hat man auch zwischen bestimmten Knoten in darunterliegenden Schichten eine exakte Heuristik. Wie viel besser (von der Skalierbarkeit her) soll es denn noch werden?
Bei einem statischen Graphen kann man ja vieles vorberechnen. Im Extremfall speichert man einfach alle Zweipunktdistanzen ab und hat dann konstante Laufzeit.
Man hat also einen Tradeoff zwischen Speicherplatz und Laufzeit einer Abfrage.
Mit den ganzen mobilen Routenplanern hat sich in letzter Zeit wieder viel in der Forschung auf statischen Graphen getan. Ein Beispiel dazu: http://www.avglab.com/andrew/pub/reach.pdf
-
Optimizer schrieb:
Meine Erachtens nach ist der A*-Algorithmus das schnellste bekannte Graphensuchverfahren...
Das kommt ganz auf die Aufgabenstellung an. Wenn du dir mehrere Routenplaner (besonders die kleinen fuer handy) anschaust, siehst du das trotz selbem start und endpunkt, oft verschiedene wege gefunden werden. das waere mit A* schonmal nicht moeglich.
Klar koennte man sagen "Es liegt an den unterschiedlichen inputdaten" und dann kann man sich aber auch denken "wenn die inputdaten schon nicht 100% perfekt sind, wieso muss der suchalgorithmus es sein?" und deswegen gibt es seit ca 20jahren mobile systeme die das problem loesen konnten.vorberechnete graphen sind natuerlich auch eine moeglichkeit, kommt halt auf das system an, server im netz mit ein paar TB speicher oder handy mit ner flashcard
Jester schrieb:
Da vergleichst Du grad Äpfel mit Birnen.
Als ich seine Frage las, musste ich schon drank denken dass du das Zucken bekommst wenn du sie liest :xmas2:
-
rapso schrieb:
Optimizer schrieb:
Meine Erachtens nach ist der A*-Algorithmus das schnellste bekannte Graphensuchverfahren...
Das kommt ganz auf die Aufgabenstellung an.
Ja, das war ungenau. Ich habe das auf Verfahren bezogen die garantieren, den kürzesten Pfad zu finden, aber das war eine implizite Annahme von mir, die so nicht angesprochen wurde. Durch das mip-mapping ist das pathfinding dann ohnehin auch nicht mehr 100% optimal.
Ich frage mich nur, was Jester für Algorithmen gemeint haben könnte, die dann noch viel besser mit steigender Knotenzahl skalieren. Fast alle Verfahren, die garantiert den kürzesten Weg bestimmen sind eine Spezialisierung von A* (auch Dijkstra). Vielleicht hat Jester aber auch einfach nur Verfahren wie best-first search gemeint, die teilweise ganz schön danebenliegen und die ich in meinem Perfektionismus unbewusst ausgeblendet habe.
-
Optimizer schrieb:
Ich frage mich nur, was Jester für Algorithmen gemeint haben könnte, die dann noch viel besser mit steigender Knotenzahl skalieren. Fast alle Verfahren, die garantiert den kürzesten Weg bestimmen sind eine Spezialisierung von A* (auch Dijkstra). Vielleicht hat Jester aber auch einfach nur Verfahren wie best-first search gemeint, die teilweise ganz schön danebenliegen und die ich in meinem Perfektionismus unbewusst ausgeblendet habe.
Ne, ich meine schon exakte Algorithmen.
- Highway Hierarchies
- Reach based routing
- Landmarks
- Shortest Path Containers
- Arc Flags
- Transit Nodes
- SHARC: http://arrival.cti.gr/index.php/Documents/0078