我读过很多关于如何解迷宫的问答，而且我熟悉在编程中使用递归。我的情况略有不同:
我正在尝试开发一台机器(用 Java)来解决具有一个入口点的 2D 竞技场，入口点可以在 map 的任何地方，而不仅仅是在边缘。目标不是找到出路(没有出路。入口点就是导出)。任务是走所有地方并寻找收藏品，避开障碍物。
假设它是矿井中的挖掘机。天黑了，你可以看到周围有 2、3、4 个瓷砖，你在这个范围内只能看到收藏品，因为它们有点闪烁。在挖掘机尝试并无法移动之前，都不会“看到”障碍物或 map 的边缘。这意味着我们不知道 map 的完整大小和形状。有时它是一系列细长的隧道，有时它是一组大房间(30x100 block )，或两者的组合。
我已经在半空房间(没有障碍物和收藏品)的类似房间的 map 中尝试了一个简单的迷宫解决方案，递归。从房间的这一部分开始，挖掘机在这些空 block 中来回走了几十次，直到最后玩完所有可能的路，最终到达房间的另一端。
显然，对于此类 map ，我需要一种不同的方法，而这个简单的迷宫解算器非常适合(好吧，几乎)用于走长隧道。
对于那些已经走到这一步的人，这里有一个附加条件和特征的列表:
- 虽然大多数收藏品在“挖掘”时会消失并让路，但有些会变成障碍物而无法通过。
- map 周围有通往另一张 map 的大门。将其想象成电梯和地板。
- 有可以打开门的杠杆、收集 key 、移动石头以开路或放置在某些地方以解锁区域等。
好吧，非常棒的案例，当然，我的挖掘机将只做简单的工作(1. 和 2. 很容易编码，而 3. 是 Isaac Asimov)
因此，如果不清楚我到底在问什么，请看这里:
如何改进我的算法，避免在一个已经很清楚的区域走太多次，并在寻找收藏品时“更聪明”，无论 map 类型如何？
最佳答案
我所知道的所有图形搜索算法都假设图形从一开始就已知。如果你想尝试使用类似于图形搜索的东西，你需要为环境(传感器范围之外)制作某种概率模型，然后进行蒙特卡洛模拟:
循环N次并:
- 根据您已有的信息，根据模型将环境中未知部分的实例随机化。
- 在“猜测”的环境下用常用算法解决搜索问题
- 对“最佳路径”将采用的第一个 Action 投票
得票最多的运动方向获胜。
您必须调整 N 和您为环境建模的方式，此方法才能发挥作用。无论如何，这是一个非常困难的问题。甚至这种技术也没有考虑从它的每个选择中获得的潜在信息(深入展望这种计算，因为状态评估非常昂贵)
关于在迷宫中走完所有可能 block 的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34593233/