有障礙物的最短路徑

Question

我們給出N×N雷區（二維數組），在另一個M×2陣列中給出地雷的座標。尋找從左上角到右下角的最短路徑的最佳算法是什麼？

Answer 1

這是一個shortest path problem，並且可以通過減少問題的graph解決：

G=(V,E) 
V = { (x,y) | for all x,y such that (x,y) is not a mine } 
E = { ((x1,y1),(x2,y2)) | (x1,y1) is adjacent to (x2,y2) } 

現在，當你有圖表，你需要應用一些最短路徑算法。

• 最簡單的將是BFS（因爲你的圖是未加權的）。這個 實現起來相當簡單，並且如果存在 ，它總是找到最快的路徑。
• 更復雜一點的方法是bi-directional BFS。在這裏，你從開始節點（0,0）和結束節點（n，n）做一個BFS - 並在算法的兩個前端找到對方時結束。路徑是通過將第一個與第二個的相反連接而給出的。這種方法可能比常規BFS更快，但編程起來有點困難。
• 您可以使用知情算法，如A* search algrotihm，曼哈頓距離作爲啓發函數（假設您只能上/下/右/左，沒有對角線）。這可能會比兩種選擇都快，但編碼更難。

---

我就從BFS，如果你有它的經驗開始，後來轉移到更先進的algroithms。

在僞碼：

BFS(x_source,y_source, x_target,y_target): 
    queue = empty new queue 
    queue.add(Pair(x_source,y_source)) 
    parent= new dictionary 
    parent.add(source, None) 
    while (queue.empty() == false): 
     curr = queue.dequeue() 
     currX = curr.first 
     currY = curr.second 
     if (currX == x_target && currY == y_target) 
      return getPath(dict, curr) 
     for each neighbor u of curr: //u is a pair of (x,y) coordinates of adjacent cell 
      if u is not a key in parent: 
      parent[u] = curr 
      queue.add(u) 

上面BFS填充parent字典，並且該路徑是由以下的getPath（）函數，該函數基本上橫穿字典，直到找到「根」返回（其是原始的源節點）。

getPath(dict, target): 
    sol = [] //empty list 
    curr = target 
    while curr != None: 
     sol.addFirst(curr) 
     curr = dict.get(curr) 

Answer 2

這個問題可以用Dijkstra算法來解決。 首先刪除所有到達節點的傳入路徑，然後以最短路徑前往右下角節點。