我正在研究一个最短迷宫问题，有一个起点、一个终点和一些检查点，旅行者必须至少通过一次。 '#' 表示墙，'.'表示道路，“P”表示检查站。
我正在考虑从终点开始寻找最近的检查点，并从当前检查点开始继续寻找那些未访问过的检查点，直到访问完所有检查点。最后寻找到达起点的最短路径。
但这看起来不太好，我的意思是，它看起来只是一个贪婪算法，不能确保您获得最佳解决方案。判断走哪个检查点时应该使用Knapsack算法吗？
最佳答案
不确定它是否是最有效的，但以下应该有效:
- 使用 Dijkstra (ie breadth-first) path finding algorithm 计算每对检查点之间的距离.
- 现在问题已经减少到 Travelling Salesman problem给定起点和终点。
对于最多大约 11 或 12 个检查点，可以使用 GPU 相当快速地解决这个问题，如 Open Source tutorial 所示。 (根据您的真实情况)。
关于algorithm - 如何在有检查点的迷宫中找到最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26030046/