Heuristik für ein A * Pfad Finden von GPS

Question

Ich entwickle ein GPS-System und dazu möchte ich den A * -Algorithmus verwenden. Ich habe ein Diagramm, wo der Eckpunkt die Quelle/das Ziel und die Kanten die Straßen sind. Dafür habe ich eine Datenbank mit folgenden Informationen:

id;"Street Name";source;target;GeoCoordinateX1;GeoCoordinateY1;GeoCoordinateX2;GeoCoordinateY2 

Jede dieser Zeilen repräsentiert eine Kante. Unter Verwendung der Koordinaten wird das Ziel verwendet, einen Wegsuchalgorithmus den kürzesten und schnellsten Weg zu erhalten. Ich habe bereits den djikstra Algorithmus entwickelt, aber jetzt versuche ich eine wirklich gute Heuristik zu finden.

Ich würde gerne wissen, ob es eine Heuristik gibt, die genauer oder effizienter ist. Ich habe gelesen, dass ich Manhattan, Euklidische oder Diagonale Entfernung benutzen könnte. Ich denke, Euclidian wäre eine gute Wahl, aber dann wären die Kosten für die g-Funktion nicht die gleichen wie für die heuristische Funktion h. Ich würde den kürzesten Weg nehmen, aber es würde länger dauern. Gibt es einen Weg, das Gute und den Profit zu bekommen?

Mit freundlichen Grüßen

Answer 1

Für die meisten basierte Wegfindung Koordinate, die Kostenfunktion in A * verwendet wird, ist ‚Distanz‘. Jeder vertex in Ihrem ist ein GPS entlang einer Straße koordinieren, so dass der Abstand zwischen den einzelnen vertex berechnet wie this mit der Haversine Formel:

function getDistanceFromLatLonInKm(lat1,lon1,lat2,lon2) { 
    var R = 6371; // Radius of the earth in km 
    var dLat = deg2rad(lat2-lat1); // deg2rad below 
    var dLon = deg2rad(lon2-lon1); 
    var a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
      Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * 
      Math.sin(dLon/2) * Math.sin(dLon/2) 
    ; 
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    var d = R * c; // Distance in km 
    return d; 
} 

function deg2rad(deg) { 
    return deg * (Math.PI/180) 
} 

Um die schnellste Weg zu finden, die Kostenfunktion wird "geschätzte Reisezeit" sein. Um dies zu berechnen, benötigen Sie für jede edge zwischen vertices (Straße) sowie die oben berechnete Entfernung die "Geschwindigkeitsbegrenzung".

Die Kostenfunktion ist sehr einfach: cost in hours = distance/speed = km/(km/h)

Google Maps ein API hat die kürzesten/schnellsten Wege für viele verschiedenen Verkehrsträger zu finden, und es wird Ihnen viel Mühe sparen. Es berücksichtigt auch Verkehr, Busfahrpläne und andere Faktoren, die in Ihrem Projekt schwer zu berücksichtigen wären.

Wenn dies ein Hobbyprojekt ist, fahren Sie fort und Sie werden viel über Pfadfindung lernen. Fühlen Sie sich frei, von meinem Lieblings A * Führer auf Amit Patels website zu lernen. Wenn Sie mehr über all die coolen Optionen erfahren möchten, die Sie für die Pfadfindung haben, habe ich eine ausführliche Anleitung, die ich für this answer geschrieben habe. Menschen in der Wissenschaft schreiben häufig Tutorials zu den essentiellen Algorithmen und Google-Suchen finden Forschungsberichte über Varianten dieser Algorithmen.