A *経路のヒューリスティックGPSを見つける

Question

私はGPSシステムを開発しており、これを行うにはA *アルゴリズムを使いたいと思います。頂点がソース/ターゲットであり、エッジが通りであるグラフがあります。そのために私は以下の情報を持つデータベースを持っています：

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

これらの各行はエッジを表しています。目的を使用している座標を使用して、経路探索アルゴリズムが最短かつ最速の経路を得る。私はすでにdjikstraアルゴリズムを開発しましたが、今は本当に良いヒューリスティックを見つけようとしています。

より正確で効率的なヒューリスティックがあるかどうかを知りたいと思います。私はマンハッタン、ユークリッドまたは対角線距離を使うことができると読んだ。私はユークリッドが良い選択だと思っていますが、gファンクションのコストはヒューリスティック関数hと同じではありません。私は最短経路を得るだろうが、それはもっと長くかかります。利益と利益を得る方法はありますか？

敬具最もベースの経路探索を調整するために

Answer 1

、*で使用される費用関数は、「距離」です。あなたの各vertexは、GPSは、通りに沿った座標であるので、各vertexとの間の距離は、半正矢式を用いthisように計算される：、最速パスを見つけるために

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) 
} 

コスト関数は「推定旅行時間」になります。これを計算するには、それぞれedgeの「速度制限」がvertices（通り）と上記で計算された距離の間にある必要があります。

コスト関数は非常に簡単です：cost in hours = distance/speed = km/(km/h)

のGoogleマップは、交通機関の多くの異なるモードのための最短/最速のパスを見つけるために、それはあなたに多くの労力を節約するAPIを持っています。また、あなたのプロジェクトでは考慮しにくい交通量、バススケジュール、その他の要因も考慮に入れています。

これが趣味のプロジェクトの場合は、続行して、経路探索について多くのことを学びます。 Amit Patelのwebsiteに関する私の好きなA *ガイドから自由に学んでください。パスファインディングに関するすべてのクールなオプションについて知りたい場合は、this answerについて書いた詳細なガイドがあります。アカデミアの人々は、一般的に重要なアルゴリズムに関するチュートリアルを作成し、Googleの検索では、これらのアルゴリズムのバリアントに関する研究論文を見つけることができます。