Wie berechnet man den heuristischen Sternschnuppenalgorithmus?

8

Ich habe ein Problem mit dem Shooting Star-Algorithmus. Es ist mein letztes Projekt und ich brauche Hilfe.

Meine Frage ist, wie ich den heuristischen Sternschnuppenalgorithmus berechnen kann. Ich kann den pgrouting Sternschnuppen verwenden , aber ich verstehe nicht, wie man den heuristischen Sternschnuppen berechnet.

Ich habe den berechnenden heuristischen Shooting Star im Internetbuch gesucht, kann ihn aber jetzt nicht finden.

Können Sie mir etwas über den Shooting-Star-Algorithmus erzählen, nicht nur über den Quellcode, Mr. Mario?

pgrouting routing shooting-star donni
quelle

Antworten:

2

Wenn ich Sie richtig verstehe und kein Experte bin, können Sie vielleicht etwas im Quellcode der heuristischen Funktion für Sternschnuppen finden und es auch an Ihre Bedürfnisse anpassen. Natürlich müssten Sie pgrouting wieder aufbauen.

Mario Miler
quelle
Vielen Dank, Mr.Mario Miler. Ihr Quellcode ist identisch mit pgrouting oder library in Postgresql, Postgis.Right?
Donni
Dies ist der Quellcode aus dem pgrouting-Repository. Sie müssen das gesamte Repository herunterladen, die heuristische Funktion Ihrer Wahl ändern und erstellen. Einige Anweisungen finden Sie hier pgrouting.org/docs/1.x/install_ubuntu.html .. klein, alt, sollte aber funktionieren. Ich habe seit einiger Zeit kein Pgrouting mehr aufgebaut, kann Ihnen also nicht sagen, ob es irgendwelche Probleme gibt.
Mario Miler
Können Sie mir etwas über den Shooting-Star-Algorithmus erzählen, Mr. Mario?
Donni
Können Sie mir etwas über den Shooting-Star-Algorithmus erzählen, nicht nur über den Quellcode, Mr. Mario?
Donni
Der Start der Dreharbeiten ist nur ein ausgefallener Name für das, was im Wesentlichen noch A * ist. Es werden nur Routen anstelle von Knoten weitergeleitet. Siehe diese Diskussion: download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/…
Uffe Kousgaard
1

Ich bekomme dieses von der Mailingliste. Das Aufnehmen * ist kantenbasiert, geht also von Kante zu Kante, während A * und Dijkstra von Scheitelpunkt zu Scheitelpunkt gehen. Daher benötigen Sie eine Datenstruktur, die alle benachbarten Kanten für jede Kante Ihres Diagramms beibehält. Sie können dies auch tun, indem Sie ein Liniendiagramm (http://en.wikipedia.org/wiki/Line_graph) aus Ihrem ursprünglichen Straßennetz erstellen. Und dann können Sie Durchgangskosten von Kante zu Kante zuweisen (als spezielles Attribut Ihrer benachbarten Kantenstruktur oder als Kosten des Liniendiagramms), die tatsächlich jede Art von Einschränkungen oder Strafen für den Übergang von einer Kante zur anderen darstellen - wie z als Abbiegebeschränkungen bei Abbiegungen oder anderen Einschränkungen wie Ampeln. In diesem Fall können Sie A * oder einen anderen Algorithmus für kürzeste Pfade verwenden, wobei Kanten als Eckpunkte verwendet werden.

Das ist also eine Idee hinter dem Shooting *.

Und ich bekomme diesen einen Agaian von Anton Patrushev: http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/276.html . Sie schreiben folgendermaßen: In A * verwenden wir etwas Ähnliches wie die Manhattan-Funktion (| Dx | + | Dy |) / 2 http://pgrouting.postlbs.org/browser/trunk/core/src/astar_boost_wrapper.cpp#L75 Dort sehen Sie andere auskommentierte Versuche. Wir haben versucht, andere Funktion ist OK. Wahrscheinlich war es ein historischer Grund. heuristische Funktion und aus irgendeinem Grund (ich erinnere mich jetzt nicht) entschieden, dass für ein gemeinsames Straßennetz dieses In Shooting * wir die euklidische Entfernung verwenden. http://pgrouting.postlbs.org/browser/trunk/core/src/shooting_star_boost_wrapper.cpp#L100 .

Die andere Formel: - Euklidischer Abstand> Sqrt (Dx² + Dy² + Dz²); - Manhattan Entfernung> | Dx | + | Dy | + | Dz | ;; - Maximaler Abstand> Max (| Dx |, | Dy |, | Dz |).

Ich verstehe immer noch nicht alles. Freund, kannst du mir kurz und detailliert den Shooting Star des Prozessalgorithmus erzählen?

donni
quelle