[MySQL] Streckenberechnung

Interessant wäre noch, dass Postgresql wohl eine connectby() Funktion hat. Habe eben auf die Schnelle in den Docs aber nichts gefunden, vielleicht ist sie auch nur per Patch nachinstallierbar.
 
Könnte man denn jetzt nicht aus dem Algorithmus von Dijkstra und den MySQL User Defined Functions etwas machen? Ich überblicke das noch nicht ganz, aber das müsste doch möglich sein, oder?
 
dms schrieb:
Könnte man denn jetzt nicht aus dem Algorithmus von Dijkstra und den MySQL User Defined Functions etwas machen? Ich überblicke das noch nicht ganz, aber das müsste doch möglich sein, oder?
Zum Vergrößern anklicken....

Dijkstra wird dir nicht viel helfen. Der findet nur den kürzesten Weg.

Aber du möchtest ALLE Wege wenn ich das richtig verstanden habe? Wozu eigentlich? :p
 
Das hat sich geändert. :) Ich bin davon ausgegangen dass der Nutzer sich einen der möglichen Wege aussuchen kann. Nun soll Ihm aber nur der kürzeste angeboten werden, was mir natürlich entgegen kommt.

Allerdings bin ich dennoch auf dem völlig falschen Weg. Mein Anstatz war eigentlich von vornherein falsch. Im Moment denke ich garnicht mehr an Perfomance, sondern an überhaupt eine Lösung.

Das Problem ist folgendes: Bei den Strecken handelt es sich um Schiffahrtswege. Es gibt also keine direkten vorgegebenen Strecken im Sinne von Strassen oder Gleisen.

Mit puren Koordinaten zu rechnen, bringt also nichts (Beispiel Hamburg<->Kiel)

In meinem bisherigen Modell habe ich mit Entfernungen zum nächstmöglichen Ziel gearbeitet. Aber auch das ist ja Schwachsinn. Beispiel:

Code: 
A--B
|  |
|  D 
| /
C

Der Weg C<->B würde sich über D berechnen. Die Luftlinie C<->B ist jedoch etwas kürzer.

Ich brauche also wohl einen komplet neuen Ansatz. :mad:

Die Aufgabenstellung würde also lauten: Finde den optimalen Weg durch einen Hindernispakur anhand von Koordinaten. :eek:
 
Soll es auch eine „via c“-Funktion geben? Ansonsten ist es doch mit Koordinaten (falls bekannt) sehr viel einfacher. Du speicherst einfach nur die Koordinaten aller Orte und berechnest jedes Mal mathematisch den Weg. Keine Rekursion, kein Umständliches Eingeben von Teilstrecken.

Aber kann den das Schiff wirklich immer den direkten Weg fahren?
 
Na genau das ist ja nun das Problem daran.
Mit puren Koordinaten zu rechnen, bringt also nichts (Beispiel Hamburg<->Kiel)
Zum Vergrößern anklicken....
Irgendwie müsste ich die Landmassen bei der Streckenberechnung berücksichtigen.

Edit: Nein, keine Via-C-Funktion. Nur der direkte Weg.
 
Ui, dann wird das ja ein richtiger Routenplaner. Darüber sollte es genug Literatur geben, hab jetzt schnell bei Amazon nix gefunden, aber ich gucke morgen mal in der Uni-Bibliothek, da gibt's alles :)

Die Informationen über Wasserstraßen sind frei erhältlich.

Ein ähnliches System (Routenplaner fürs Wasser) habe ich im Internet nicht gefunden, aber ich denke oberer Link hilft schon mal.
 
Zuletzt bearbeitet:
Ich glaube, der A*-Algorithmus wurde in diesem Topic schon mal genannt. Der würde Dich weiterbringen. Allerdings kannst Du Dich dann sicher von schnellen Reaktionszeiten des Systems verabschieden, sofern Du nicht cachst.
 
Ja, der A*-Algorithmus wurde schon genannt. Ich weis nur nicht wie er mich weiterbringen soll. Ich weis noch nicht mal wie ich die Landmassen erfassen soll.

Im Prinzip ist die Aufgabenstellung ja umgekehrt. Ich will nicht den kürzesten Weg anhand von Teilstrecken/Knoten ermitteln, da ich mit festen Strecken keine "realistischen" Ergebnisse erziele. Ich brauche also eine Möglichkeit um nicht erlaubte Gebiete (Land) zu definieren und einen Algorithmus der den kürzesten Weg in erlaubtem Gebiet (Wasser) berechnet.

Wie gesagt bin ich vom Performance-Aspekt ganz abgekommen. Sollte ich irgendwie eine Möglichkeit finden, wird es wohl so ablaufen dass die Strecken zwischen allen Punkten (ca. 250) ein einziges Mal berechnet und in der DB abgelegt werden.

@Jakob Danke für den Link. Aber geht es dort nicht nur um Wasserstandsmeldungen und ähnliches. Ich finde die Seite insgesammt recht verwirrend. :) Irgendwie beschreiben sie nur was sie machen, aber ein tatsächliches Informationsangebot kann ich nicht finden. :confused:
 
Es gibt ein Info-PDF. Ja, es sind ganz viele Infos dabei, aber anscheinend unter anderem auch die Wasserstraßen. Wenn nicht, sind die bestimmt ne gute Anlaufstelle, zu fragen, wo man sonst diese Infos herbekommt.

Hintergrund ist einfach, dass Du ja quasi ein Schiffs-Routenplaner bauen willst. Die Auto-Routenplaner (map24 etc.) nutzen auch vom Vermessungsamt frei zugängliche Daten zur Straßenlage. Wenn Du diese Schiff-Straßen hast, brauchst Du nur noch eine Art rausfinden, wie Du sie geschickt abfragst, musst aber nicht die Karte nachbauen.

Es sollte doch Bücher über das Problem „kürzeste und schnellste Strecke“ geben. Ist ja ein Standardbeispiel aus der Informatik.
 
Ja, ich denke auch, dass sich die Schiffswege auf erprobte Wasserwege beschränken lassen. Genau diese solltest Du dann in einem Graphen nachbilden. Wenn Du das tust, brauchst Du nicht einmal die Landmassen extra zu berücksichtigen.
 
Ich habe ein wenig mit dem A*-Algorithmus experimentiert. Dazu habe ich mir eine Testkarte im Format 400x400 erstellt.

Im Anhang ist der errechnete Weg, funktioniert also.

Bei der Sache gibt es nur 2 Probleme. Das erste wäre, dass die Wege nicht wirklich optimal sind. Der Algorithmus geht immer nur zum nächstgelegenen Nachbarfeld (logisch). Bei einem Weg von 1/1 nach 2/4 wird nicht der direkte Weg gewählt, sonder es wird ein Umweg über 2/2 genommen.

Wie auch immer, das andere Problem ist viel gravierender. Für die Berechnung des Weges (nicht das Generieren der Grafik) im Anhang wurden 21 Sekunden lang bis zu 54 MB Speicher bei einer 100%igen Prozessorauslastung verbraten. Bei 250 Orten sind das ja Tage die der Rechner da heiss laufen würde. ;) Hinzu kommt dass die Testgrafik recht klein angesetzt war. Die echte Karte wird vermutlich mindestens 2000x1500 abmessen.

Durch solch ein virtuelles Fahrrinnensystem könnte man den Rechenaufwand sicher bedeutend vermindern, da man die Knoten deutlich reduziernen könnte. Leider fehlt mir der Ansatz.

Derzeit lese ich meine Karte aus einer Textdatei ein die im Prinzip so aufgebaut ist:
Code: 
000000000000000
000001100000000
000000111110000
000001111111000
000000111100000
000000001110000
000000000010000
000000000000000
0=Wasser 1=Land

Die Datei wird in ein zweidimensionales Array eingelesen womit ich dann den Algorithmus füttere.

Habe ich nun irgend eine Möglichkeit nur bestimmte Routenpunkte zu definieren?

Ich hoffe man konnte mich einigermassen verstehen. Ist mal wieder etwas spät geworden. :)
 

Anhänge

  • a-star.png
    a-star.png
    2,3 KB · Aufrufe: 90
Habe nun einen anderen Ansatz. PHP ist eindeutig zu langsam. Ich bin gerade daran eine eigene PHP-Extension in C zu schreiben. Angeblich soll die Berechnung in C ca. 280 mal schneller sein. Bin gespannt. :)
 
Ja, das ist eine gute Idee mit der Extension
 
Reine Neugier: Bist Du weitergekommen?
 
Nein, leider nicht. Ich habe es heute Mittag aufgegeben. In der Theorie würde es problemlos funktionieren, aber ich komme mit der Syntax nicht zurecht. Mit C alleine würde ich sicher weiter kommen, da gibt es ja genug Dokumentationsmaterial zu. Aber Zend ist die Hölle. Es gibt zwar ein paar echt schöne Tutorials zum Thema PHP-Extensions, aber die haben mich nur bis zu einem bestimmten Grad weitergebracht. Mit mehrdimensionalen Arrays über die Zend-Engine zu arbeiten ist nicht leicht. Wie man die Werte eines Arrays ausliest habe ich in stundenlangen ausprobieren und Sourcecode-durchwühlen selbst rausfinden müssen. Naja, das Ergebnis ist leider dass an einer Stelle im Code ein "Interner Server Fehler" verursacht wird. Im Logfile steht absolut nix. Das Merkwürdige ist dass der Fehler an einem Codeschnipsel auftritt der Zigfach im Quellcode vorkommt (Copy&Paste). An den anderen Stellen funktionierts problemlos.
Da ich keine Anlaufstelle für die Zend-Entwicklung gefunden habe und auch kein C-Guru bin, habe ich dieses Projekt erst mal als unlösbar (für mich) eingestuft. :(
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben Unten