Dijkstra算法與切比雪夫距離

Question

我一直在使用Dijkstra算法來查找由普林斯頓大學算法第2部分給出的圖形API中的最短路徑，並且我已經找到了如何找到具有切比雪夫距離的路徑。

儘管切比雪夫可以移動到節點的任何一側，但成本只有1，但對總成本沒有影響，但根據圖表紅圈，路徑尋找線爲什麼沒有移動曲折而沒有直行？

如果我使用A *算法，同樣的事情會重複嗎？

Answer 1

如果你想優先「直線」你應該採取一個步驟中考慮的方向。一種可能的方法是創建一個圖G'(V', E')其中V'由所有相鄰頂點對組成。例如，頂點v = (v_prev, v_cur)將在路徑中定義頂點，其中v_cur是路徑的最後一個頂點，而v_prev是前一個頂點。然後在最短路徑算法的「更新距離」步驟中，您可以選擇具有最佳（不變）方向的最佳距離。

此外，我們可以添加附加屬性的距離等於改變方向的數量，並找到最小距離的方式與最小數量的方向改變。

Answer 2

根據Dijkstra或A *，它不應該是特別直的，如您所說的它對總成本沒有影響。順便說一下，我會假設你想特別防止無用的鋸齒形鋸齒，並且一般沒有特別的偏好，因爲它和前面的移動走向相同。 Dijkstra和A *沒有對「怪異路徑」的內置不喜歡，他們只是明確地關心成本，隱含地意味着他們也關心你如何處理同等成本。有一對夫婦的事情你可以做的：

1. 使用打破平局讓他們更喜歡直線移動，只要兩個節點具有相同的成本（G或F，這取決於你正在做的Dijkstra算法或A * ）。這給障礙帶來了一些麻煩，因爲最終導致等長路徑的兩個選擇不一定具有相同的F分數，所以它們可能不會打破平局。它永遠不會給你一個次優路徑。
2. 有點增加你的對角線成本，它不一定非常多，比如直線10和對角線11。這將避免任何不是捷徑的對角線移動。但顯然：如果這不符合實際成本，現在可以找到次優路徑。成本差異越大，發生的越多。在實踐中，這是相對罕見的，路徑必須足夠長（積累足夠的成本差異，以便在發生之前變得值得一整套額外的行動）。