我有一个类似加权迷宫的网格，我需要在没有任何迷宫知识的情况下找到到实体的最短路径。
像 A* 这样的算法需要先验知识并在环顾四周时“跳跃”，但是当我有一个机器人时这是不可能的。
我的第一个想法是首先使用 BFS 探索整个迷宫，然后在探索的迷宫上应用 A* 以找到最短的同时考虑权重的迷宫。但这似乎很幼稚。
谁能指出一些适合解决这个问题的算法？
最佳答案
我认为最适用于此类问题的算法是 Dijkstra's algorithm.
简而言之，该算法从某个根节点开始，扫描所有邻居并选择距离根路径最短的节点进行访问。
保留一个包含每个节点的表
到根的最短路径
到达该节点的路径中的最后一个节点
只要发现更短的路径，就会在表中更新到节点的最短路径。 当您的实体被访问时，它的最短路径将是从 root->entity 的最短路径，通过其父节点回溯将产生实际的节点路径。 (这里是另一个 video 如果你感到困惑)。
关于在没有先验知识的情况下在迷宫中寻找实体的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53696067/