障碍物最短路径

Question

我们有一个 N x N 的雷区（二维数组），地雷的坐标以另一个 M x 2 的数组给出。如何找到从左上角到右下角的最短路径，而不踩在雷上？请提供最佳算法。

- LiquideX

---

欢迎来到本站！有一件事需要注意：您应该始终首先展示您的算法，并指出不起作用的部分，以期望在这里获得帮助。 - ZygD

这是作业吗？如果是的话，应该标明。我会使用 A* 算法，请看这里：https://dev59.com/XX_aa4cB1Zd3GeqP7cTT 如果你想要最好的算法，那么你应该根据哪些方面/条件来指定（性能、空间/时间复杂度、行数等）。 - Spektre

你所说的“最佳算法”是什么意思？是指速度最快、代码最少、可维护性最高、易于理解吗？ - Paul Hankin

Answer 1

这是一个最短路径问题，可以通过将问题转化为图形来解决：

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（因为你的图表没有权重）。这很容易实现并且总是找到最快的路径，如果存在的话。
• 稍微复杂一点的方法是双向BFS。在此，您从起始节点（0,0）和结束节点（n,n）进行BFS，并在两个算法的前端相遇时完成。路径由第一个与第二个的反转连接而成。此方法可能比常规BFS更快，但编程稍微困难。
• 您可以使用启发式函数为曼哈顿距离（假设您只能向上/下/右/左移动，不能对角线移动）的A*搜索算法等通知算法。这可能比其他两种选择更快，但编码较难。

---

我会从广度优先搜索算法开始，如果你没有相关经验的话，然后逐渐转向更高级的算法。

伪代码如下：

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)

- amit

Answer 2

这个问题可以使用Dijkstra算法解决。首先删除所有指向我的节点的入站路径，然后继续寻找到右下角节点的最短路径。

- Himanshu Goel

---

Dijkstra算法在这里有些过度，因为图是无权的。它比BFS更难实现且效率更低，而BFS在这里也是最优的选择。 - amit