迷宫中遍历所有可能的区块的算法

4
我阅读了很多有关如何解决迷宫问题的问答,并熟悉在编程中使用递归。我的情况略有不同:
我正在尝试开发一台机器(使用Java语言)来解决一个二维竞技场,该竞技场只有一个入口,可以位于地图上的任何位置,而不仅仅是在边缘。目标不是找到出路(因为没有这样的出路,入口点就是出口),而是走遍所有地方,寻找收藏品并避开障碍物。
想象一下这是一个挖掘工在矿井里。黑暗中,你只能看到周围2、3、4个瓷砖,而你所能看到的范围内只有收藏品,因为它们会闪烁。直到挖掘工尝试并无法移动时,才会“看到”障碍物和地图的边缘。这意味着我们不知道地图的完整大小和形状。有时它是一系列长而窄的隧道,有时它是一组大房间(30x100块),或者两者的组合。
我曾经尝试过使用递归的简单迷宫解决方案,在房间式地图中进行操作,其中半个房间为空白(没有障碍物和收藏品)。从这部分房间开始,挖掘工要在这些空块中来回走动数十次,直到它最终玩尽所有可能的方法,最终到达房间的另一端。
显然,我需要针对这种地图采用不同的方法,而这种简单的迷宫解决方案非常适用于行走长隧道(好吧,几乎是)。
对于那些阅读到这里的人,以下是附加条件和特性列表:
1.虽然大多数收藏品在被“挖掘”时会消失并让路,但有些会变成障碍物,无法通过。
2.地图周围有门通往另一个地图。可以将其想象为电梯和楼层。
3.有拉杆、开门的钥匙、移动的石头以及放置在某些位置以解锁区域等。
嗯,这是一个相当棒的案例,当然,我的挖掘工只会做简单的工作(1.和2.很容易编码,而3.则是为艾萨克·阿西莫夫准备的)。
因此,如果不清楚我正在询问什么,请看这里:
如何改进我的算法,以便在已经清晰的区域中不要走那么多次,并且在查找收藏品时更加“聪明”,无论地图类型如何?

2
如何使用广度优先搜索,跟踪已经访问过的每个瓷砖,以便不再访问它们? - Bart van Nierop
是的,我正在考虑它并查看我在实现中漏掉了什么。 - Jeff Horowitz
听起来像是一个图问题,使用一个图库(我会说 boost::graph,但你正在使用 Java...) - kebs
仍在进行我的研究,发现了“回溯剪枝”背后的另一种方法。 - Jeff Horowitz
1
我想补充一下我的初始评论,为了回到起点,你可能应该从头开始进行另一次搜索。毕竟,你走过的路径去到某个瓷砖并收集所有东西,很可能比从那个瓷砖返回的最短路径要长得多。当然,你应该保留哪些瓷砖是无法通过的信息。 - Bart van Nierop
我很快就通过了BFS,这是我的失误。实际上,BFS比我实现的方法要好得多,也许我实现的是某种深度优先搜索。也许是BFS+回溯的混合体,如果我知道它更像是一个隧道地图,那么就是DFS+回溯。 - Jeff Horowitz
1个回答

1
我所知道的所有图搜索算法都假定从一开始就已知图形。如果您想尝试使用类似图搜索的东西,您需要为环境(超出传感器范围)制作某种概率模型,然后进行蒙特卡罗模拟:循环N次并:
- 根据模型随机化未知环境的实例,根据您已经拥有的信息。 - 使用通常的算法在“猜测”的环境上解决搜索问题。 - 对“最优路径”第一次移动投票。
得到最多投票的移动方向胜出。为了让这种方法有用,您需要调整N和您对环境建模的方式。无论如何,这是一个非常困难的问题。即使这种技术也不考虑每个选择的潜在信息收益(深入地前瞻这种计算作为状态评估是非常昂贵的)。

1
谢谢,@yonil!让我的机器具备学习能力真是太棒了。作为一个开始,我会选择一些简单的东西,比如在一组求解器之间进行选择或者/和给“挖掘”的方向优先级——你的投票系统的简化版本。有了你和@Bart的指导,接下来几天我将会很忙。再次感谢! - Jeff Horowitz

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接