Navigations-App und Wegfindung selber programmieren - Erfahrungen, Ideen, Anregungen

[NoahPillich]

Hallo,
ich bin schon länger auf der Suche nach Ideen, wie ich folgendes Problem lösen kann:
Es geht darum ein Programm zu schreiben, das auf einer Karte mit Straßen und Hausnummern von einem Ort zu einem anderen Ort den schnellstmöglichen weg findet.Über die Programmierung dieses Algorithmuses weiß ich bereits einiges (Über Ideen freue ich mich trotzdem ). Das Problem ist viel eher eine passende Karte zu finden, auf der dem Programm klar ist, wo ein weg ist und wo nicht. Ich bin kein völliger Programmieranfänger, habe jedoch meistens nur mit js (html) und python zu tun gehabt. Wie man so etwas realisiert weiß ich deshalb nicht.
Wenn es jemanden gibt, der so etwas schon gemacht hat, würde ich moch sehr freuen.
Viele Grüße

 

[mrBrown]

Über die Programmierung dieses Algorithmuses weiß ich bereits einiges (Über Ideen freue ich mich trotzdem ).

Was weißt Du denn schon darüber? Das ist ja ein relativ breites Feld...

Problem ist viel eher eine passende Karte zu finden, auf der dem Programm klar ist, wo ein weg ist und wo nicht.

OpenStreetMap

 

[Oneixee5]

Routing ist nichts für Anfänger, das ist nicht nur Problem der Programmierung, sondern auch ein mathematisches Problem. Karten mit den nötigen Informationen gibt es bei Openstreetmap, https://wiki.openstreetmap.org/wiki/Routing

 

[NoahPillich]

Was weißt Du denn schon darüber? Das ist ja ein relativ breites Feld...


OpenStreetMap

Das stimmt. Ich wollte damit nur darauf hinaus, dass es mir eher darum geht, wie ich zum Beispiel einen Algorithmus wie den Dijkstra-Algorithmus auf eine Karte anwenden kann. Der Algorithmus ist aufgebaut wie ein Baum, der an jeder Abzweigung versucht den besten Weg zu finden, dabei berücksichtigt er das Verkehrsaufkommen, Bergsteigung und Straßenbedingungen, Einbahnstraßen. nehmen wir an ich hätte einen perfekten Algorithmus, der nur noch Daten aus einer Karte bracht (Anzahl der Kreuzungen, Länge der Straßen hinter jedem Abzweig). Diese Informationen muss er ja aus einer Karte bekommen, die im Idealfall schon alle Längen jeder Straße inbegriffen hat. Die Frage ist woher ich genau solch eine Karte bekomme. Vielleicht gibt es ja auch schon openSource Karten, die diesen Algorithmus anwenden.
Aber OpenStreetMap ist da schon ganz gut.
Danke dir für den Tipp.

 

[NoahPillich]

Routing ist nichts für Anfänger, das ist nicht nur Problem der Programmierung, sondern auch ein mathematisches Problem. Karten mit den nötigen Informationen gibt es bei Openstreetmap, https://wiki.openstreetmap.org/wiki/Routing

ok, das ist echt nochmal nen ordentliches Stück komplexer. Danke für den Link.

 

[mihe7]

Dijkstra-Algorithmus

https://i11www.iti.kit.edu/_media/teaching/theses/ba-hamme-13.pdf

 

[LimDul]

Dijkstra ist dafür allerdings nicht wirklich geeignet. Sinnvoller ist da etwas wie A*: https://de.wikipedia.org/wiki/A*-Algorithmus

Dijkstra hat das Problem, dass er ganz schlecht skaliert. Wenn du die Route von Köln nach München berechnest, berechnest du gleichzeitig sämtliche Ziele die maximal genausoweit von Köln entfernt sind wie München - also vermutlich auch Routen nach Hamburg & Paris. Wenn man dann berücksichtigt, wie Kleinteilig Straßennetze sind (teilweise bis auf Abbiegespuren runter gebrochen) kannst du dir vermutlich mehr als einen Kaffee holen gehen, währen die Route berechnet wird.