路徑規劃 - >從目標到初始狀態的方式？

Question

問題：找到從目標到起點的路徑比找到從開始到目標的路徑更有效率嗎？ 如果這是真的，有人能幫我解釋一下原因嗎？

我的看法： 它不應該是不同的，因爲找到一個從目標到開始的方式就像重命名目標開始並開始目標一樣。

Answer 1

您的問題的答案都取決於您使用的路徑查找算法。

其中最知名的路徑尋找算法A-Star（或A *）通常以相反的意義使用。這一切都與啓發式有關。由於我們通常使用接近度作爲算法的啓發式，因此我們可能會陷入障礙。然而，這些障礙可能更容易面對相反的情況。例子的一個很好的解釋可以找到here。只是爲了清楚：如果對障礙物沒有一定的瞭解，那麼A *向前和向後路徑搜尋之間沒有可預測的差異。

爲什麼你可能想扭轉尋路的另一個原因是，如果你有多個演員試圖達到相同的目標。不必執行A *或其他路徑尋找算法，對於每個參與者，您都可以將它們組合爲圖形探索路徑搜索算法的單個執行程序。例如，Dijkstra算法的變體可以在一次圖形探索中找到到所有參與者的所有最短距離。