我有一个类似加权迷宫的网格，需要找到一条通往目标实体的最短路径，但我没有任何先前了解迷宫的知识。像A*这样的算法需要先验知识并在寻找周围时“跳跃”，但是当我例如有一个机器人时，这是不可能的。
我的第一个想法是使用BFS来探索整个迷宫，然后在已探索的部分上应用A*来考虑权重并找到最短路径。但这似乎很天真。
有没有人可以指出一些适合此问题的算法？
我的第一个想法是使用BFS来探索整个迷宫，然后在已探索的部分上应用A*来考虑权重并找到最短路径。但这似乎很天真。
有没有人可以指出一些适合此问题的算法？
没有先前知识的情况下，在迷宫中寻找实体的算法
3
- rrebase
1
有人就基本上同样的问题在前几天问过：https://stackoverflow.com/q/53121908/238419 - BlueRaja - Danny Pflughoeft
1个回答
0
我认为对于这种问题最适用的算法是迪杰斯特拉(Dijkstra)算法。
简而言之，该算法从某个根节点开始，扫描所有相邻节点并选择从根到该节点的最短路径进行访问。
维护一个包含每个节点的以下信息的表格：
从根节点到该节点的最短路径
到达该节点的路径中最后一个节点
每当发现更短的路径时，表格中的最短路径将被更新。 当访问实体时，其最短路径将是从根节点到实体的最短路径，通过其父节点回溯将得到实际的节点路径。 （如果您感到困惑，请参考这里的视频。）
- Nolan R
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接