有障碍物的最短路径

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算法来解决。 首先删除所有到达节点的传入路径，然后以最短路径前往右下角节点。