algorithm - 在二维数组中找到最短路线

Question

我正在寻找一种算法，使我能够找到点“T”和“C”之间的最短路线。

##############################
#.....T........###############
#.......................#.#..#
#.#######################.#..#
#.....##......##......#....###
#...####..##..##..##..#..#...#
#.........##......##.....#.C.#
##############################

我最近遇到了这类问题。我在这里发现了一个与此问题几乎相似的问题，该问题已通过 Lee 算法解决，但无法将其应用于我的案例。

其他一些 friend 推荐我使用递归算法，但我仍然不熟悉。

你能给我一个大概的思路，应该如何解决这个问题，应该应用什么样的算法？

Answer 1

您要解决的问题称为 path finding .

---

推荐的算法之一是 A* .

在 A* 中，单元格的值是两部分的总和 - 到达该单元格的实际成本，以及从该单元格到达目的地的预期成本(称为“启发式”)。对于启发式，我们可以简单地使用一个叫做 the Manhattan distance 的东西。 ，即 x 与 y 之差之和。

然后我们的想法是保留一个 priority queue可能的候选者(我们可以保留一个单元格的坐标，以及到达那里所采取的路径，以表示一个候选者)，允许我们在每一步中选择我们期望在最短路径中的那个。然后我们从这个优先级队列中的源单元开始，然后我们删除最小值，检查它是否是目的地，然后将所有未探索的邻居添加回优先级队列，并继续这种方式直到我们到达目的地。

为了跟踪未探索的邻居，我们可以保持相同大小的 bool 矩阵，初始化为所有 false 值，并在每个值被探索时将其设置为 true(然后显然检查相应的单元格是否设置为 true 到检查一个单元格是否被探索过)。

---

另一个推荐的方法是 Dijkstra's algorithm ，但这实际上适用于加权图(其中两个步骤可能具有不同的成本)，尽管它也适用于此。我们实际上更喜欢 breadth-first search (BFS) ，可以认为是 Dijkstra 算法的一个特例。

在 BFS 中，我们保留一个 queue由所有可能的候选者组成，然后从队列中取出一个元素，检查它是否是目的地，并将其所有未探索的邻居入队，并继续这种方式直到我们到达目的地。

---

Dijkstra 算法/BFS 是更简单的方法，但也需要更长的时间才能找到最短路径。

不过，您必须小心使用 A*，因为选择的启发式算法不是 'admissible' (这意味着它可能会高估到目的地的成本)会有问题 - 但上面提到的曼哈顿距离没有这个问题。

_{(动画由维基百科提供)}