如何使用A *算法查找所有最短路徑？

Question

我知道A *算法可以找到最短路徑。但我工作中的問題是我需要找到所有最短的路徑。更確切地說，可能存在幾條最短路徑，但我需要選擇順時針優先級最短的路徑。

如果我可以得到所有最短路徑，我可以得到我想要的一個（順時針優先）。

Answer 1

Dijkstra算法爲您提供了所有最短路徑。 A *是作爲改進的Dijkstra製造的，具有額外的限制。改進之處在於您不需要訪問所有節點。如果你想探索的所有節點（這是強制性的，以確保你已經檢查了所有的最短路徑），那麼就用A *是沒有意義的，只是堅持通用祖先

Answer 2

與事情A *算法是它是完成和最優。這意味着，如果存在路徑，它將找到解決方案的路徑，但是，它也保證首先找到最短路徑。

這是因爲啓發函數A *用途必須是admissible heuristic; that is, it must not overestimate the distance to the goal.

這反過來又保證了只要你找到解決的路徑，你知道有短於沒有路徑那個在搜索空間的其餘部分。

讓我們假設到您的第一個解決方案的距離是d（問題）。現在，我的最後一句話實際上意味着，如果你只是一味地去找到第一個解決方案d（問題）後，找到另一種解決方案，D2（問題）有兩種可能：

• D2 （問題） = d（問題）：你想保留那個，因爲你想所有最佳路徑。此外，所有的新路徑可以等於或大於D2 = d
• D2（問題）>d（問題）：現在，我上面寫的相同的事情是有效的：沒有路徑更短比d2了。而且，d2已經比您正在尋找的解決方案長。所以，你可以拋棄D2並完成搜索
• 注有沒有第三個選項，D2（問題）永遠不能比的最佳d（問題）短你已經發現，由於這是該算法的基本屬性之一。

因此，要總結：你剛纔繼續下去你找到第一最優的解決方案後，你接受一切在相同距離的解決方案。距離較遠（較長）的第一條路徑，您放棄並停止搜索。

---

我只是看到了問題的「順時針」的一部分。您可以避免搜索全部最佳解決方案通過以某種方式插入順時針-您的啓發式或您的成本函數。例如。我一直在使用的一個技巧是：你的成本是一個整數，從0到inf。然後，添加順時針方向的組件，該組件可以具有來自間隔[0,1]的實數值。這樣，無論在哪裏a > b之前都是如此，它將保持如此，但如果順時針內容組件不同，則可能會更改關係a == b。

如果您不明確要使用數字值，則可以比較的另一種方法是使成本爲對的值。如果這兩個對中的第一個成分在兩個路徑成本上不同，那麼您只需比較這兩個成本。如果第一個組件是相同的，那麼只有比較這些對中的第二個值。

這就是說，我不知道我是否會建議您修改您的成本或啓發式功能（或兩者兼而有之）。另外，我不確定這個精確的技巧是否適用於您的問題，但是我相信您應該能夠將算法推向最順時針的解決方案，只需通過修改其中一個函數即可，如果您只是稍微玩一下。

Answer 3

要澄清@penelope的意思是：「......只是繼續前進找到第一最佳的解決方案之後......」

從*弄一套相當於成本最優路徑：

一旦A *找到最短路徑（cost = C *），您可以通過繼續從OPEN列表中彈出解決方案，直到遇到費用超過C *的解決方案，從而獲得等效長度的其他路徑。 （有一個警告，如果你的啓發式不完美，你可能需要做一些額外的工作。）請注意，這會給你一組最佳路徑，但不一定是所有最佳路徑的集合 - 這取決於你如何設置重複檢測。

要想從A *順時針路徑：

至於寧願順時針路徑，考慮用於排序的開放列表的比較方法使用的仲裁策略。如果兩個候選人具有相同的F成本，則最好選擇最順時針的成本。 （我認爲你可以通過查看你的候選人相對於​​開始/目標節點來得到一個順時針方向的概念。）如果你用這種方式解決問題，順時針方案將被推到OPEN列表的前面，你會從A *獲得最順時針的解決方案。