在没有先验知识的情况下在迷宫中寻找实体的算法

Question

我有一个类似加权迷宫的网格，我需要在没有任何迷宫知识的情况下找到到实体的最短路径。

像 A* 这样的算法需要先验知识并在环顾四周时“跳跃”，但是当我有一个机器人时这是不可能的。

我的第一个想法是首先使用 BFS 探索整个迷宫，然后在探索的迷宫上应用 A* 以找到最短的同时考虑权重的迷宫。但这似乎很幼稚。

谁能指出一些适合解决这个问题的算法？

Answer 1

我认为最适用于此类问题的算法是 Dijkstra's algorithm.

简而言之，该算法从某个根节点开始，扫描所有邻居并选择距离根路径最短的节点进行访问。

保留一个包含每个节点的表

• 到根的最短路径

• 到达该节点的路径中的最后一个节点

  只要发现更短的路径，就会在表中更新到节点的最短路径。当您的实体被访问时，它的最短路径将是从 root->entity 的最短路径，通过其父节点回溯将产生实际的节点路径。(这里是另一个 video 如果你感到困惑)。