java - 有障碍物的最短路径

Question

我们有 N x N 雷区(2d 数组)，地雷所在的坐标在另一个 M x 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 开始，然后再转向更高级的算法。

在伪代码中:

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()函数返回，基本上是遍历字典，直到找到“root”(也就是原来的源节点) ).

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