具有對角線移動的加權城市街區距離算法

Question

測量網格中允許對角線移動的兩個節點之間的距離的正確算法是什麼？

我想過使用歐幾里德距離，但被告知它是錯的。我搜索瞭解決方案，並且此代碼出現了，但我不確定它是否正確：

D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) 

其中D2是對角線移動的代價。如果這個方程是正確的，我怎樣才能把重量納入它？

Answer 1

如果你還沒有圖表，你可能會想要一個。一旦你建立了一個圖表，以便每個節點知道它連接的其他節點以及移動到這些節點的權重（爲此創建一個邊緣類），你應該能夠使用Dijkstra的算法或者A *算法來找到最短的路徑。 現在，您擁有最短的路徑，計算與路徑相稱的重量/距離並不困難。

如果你不清楚圖表（互聯節點）讓我知道，我會進一步解釋。

有很多教程可以在線製作圖形和加權圖形。就像Dijkstra算法的智慧一樣（我發現它比較容易理解，但通常運行速度稍慢）