尋找最短距離覆蓋最小單元數的算法

Question

我正在設計一個系統來尋找覆蓋最少單元數的最短路由。假設該平面被分成矩形單元。什麼將是最適合這個的算法。我只是尋找先機，而不是正確的代碼或實施。

Answer 1

您正在處理shortest path problem，在加權圖（頂點在網格單元格，和邊緣是從一個細胞可能移動到其他）

• 最簡單的方法是一個簡單的BFS - 即找到從源到所有目標（在未加權圖中）的最短路徑 。
  這個算法相當簡單，並且迭代地「發現」最近的節點，距離1的所有節點，然後是距離2的所有節點....
• 優化使用bi-directional search。在這裏，您可以通過從雙方進行BFS獲得單一來源和單個目標的優勢，從而有效減少您需要以不尋常方式開發的節點數量。
• 一個更多的優化可能是使用A* Search Algorithm與 啓發的功能，如manhattan distances。
  在A * Search中，您充分利用該圖不是一些任意的圖 - 而是一個網格，並且您可以根據它們在網格上的位置估計從一個節點到另一個節點的距離。該算法將使用這些估計來更快地找到最佳路徑。

注 - 我建議的所有算法找到最短路徑，不同之處在於他們需要找到它的時間。