我在編寫應用程序在OpenStreetMap數據受到一些限制（定向運動的問題）建議圓形路線的過程中來的。在算法的最內層循環中，我正在試圖找到兩個給定點之間的最低成本路徑。考慮到圖的佈局（基本上爲Euclidean），A star算法似乎很可能在給定圖的最快時間內產生結果。然而，除了我的邊緣距離（代表地圖上的實際距離），我還有一系列權重（目前從0.0，最不理想到1.0，最合意），指示特定邊緣（道路/路徑等） ）是根據我爲我的應用程序設計的一些指標計算得出的。修改星路由用於歐幾里德圖形與邊權以及距離
我想基於這些權重修改我的距離。我知道標準的A星啓發式依賴於路徑的真實成本至少和估計一樣大（基於點之間的歐氏距離）。所以我的第一個想法是想出一個方案，其中最小邊距是實際距離（對於權重1.0），並且距離隨着權重減小而增加（例如對於重量爲0.0的四倍距離）。這似乎是一個明智的方法，或者在這種情況下是否有更好的標準技術用於快速路由？
我相信你的方法是最健全的。顯然我正在研究類似的問題，我決定使用完全相同的策略。
A *算法並不一定靠「真正的距離」。它甚至不是距離，你實際上可能最小化其他物理量 - 啓發式功能應該有相同的物理單位。
例如，我的問題是最小化路徑時間，而任何給定點的速度取決於位置，時間和選定的方向。我的啓發函數是粗略距離（我的問題在地球表面上，計算大圓距離有點貴）除以最大允許速度。也就是說，它具有時間單位，並且將其解釋爲從給定位置到達終點的最樂觀時間。
這聽起來像是你在我的研究中距離我很遠。所以，聽到你用這種方法取得成功是令人欣慰的。當然，我並不關心我概述的方法的正確性（選擇了一種適合A *框架的方法） - 只要我選擇使用A *而不是Dijkstra的性能優勢距離修改。還有我是否錯過了文獻中的一個技巧。但這聽起來像我應該給我們共同的方法去。 –
@威爾遜：是的，A *肯定會比傳統的迪克斯特拉帶來性能優勢。你的啓發函數越接近給定點的（修改）距離 - 益處越大。然而，採取最樂觀的距離也是可以的。儘管如此，benfeit會更小，但它仍然比迪克斯特拉更好 – valdo
@威爾遜：P.S.訣竅是，雖然你的邊並不是單純的由幾何決定的，但你仍然可以使用A *，因爲一個事實：對於每兩個點之間的距離你有一個**最小邊界**。這使得可以將啓發式函數定義爲給定點與最終點之間的最小邊界距離。這又保證了「三角不等式」 - 即通過這樣的函數修改點得分不會影響最終路線。 – valdo
相關的問題是：「你有什麼真正希望儘量減少？」。您需要結束一個「修改距離」，以便您的尋路算法可以選擇最小的一個。
的A* algorithm的持續有效性取決於你到底如何「可取」融入到你的路由距離。 A *要求一個樂觀的「admissible heuristic」：對於「修改距離」的啓發式估計不得超過實際的「修改距離」（否則，它找到的路徑可能實際上並不是最優的......）。確保的一種方法是確保修改的距離總是大於任何給定步驟的原始歐幾里德距離;那麼，任何A *啓發式可允許最小化歐幾里得距離也是可接受的，以最小化修改的距離。
例如，如果你計算modified_distance = euclidean_distance/desirability_rating（爲0<desirability_rating<=1），您modified_distance絕不會比euclidean_distance小：無論你用你的加權路徑A *啓發式仍然是樂觀的，所以這將是一個可用* 。 （雖然，在每一個路徑是不可取的，高度過於樂觀A *啓發式可能不會提高性能，你想盡可能多...地區）
快速（ER）的路由可以用A *進行。在我自己的項目中，我看到了大約的提升。 dijkstra的compared快4倍 - 所以，甚至更快，然後bidirectional dijkstra。
但是還有更多的技術來提高查詢速度 - 例如，引入快捷方式並在該圖上運行A *。 Here是一個更詳細的答案。
你最終如何選擇你的道路？願望是如何影響的？你想要最快的最短路徑嗎？請注意，由於可以從[最長路徑問題]（http://en.wikipedia.org/wiki/Longest_path_problem）中減少[NP-Complete]（http ：//en.wikipedia.org/wiki/NP-complete） – amit