无信息迷宫出口的优化算法 [英] Optimal algorithm to find exit of a maze with no information

问题描述

我必须确定一种让机器人走出迷宫的方法。问题是，迷宫的布局未知，出口位置也未知。机器人还会从迷宫中一个未知的位置开始。 我找到了3个解决方案，但我很难知道我应该使用哪一个，因为最终似乎这些解决方案都是纯粹随机的。 我有三个解决方案：
1)基本的"人"策略(？)，你把手放在墙上，如果需要的话，穿过所有的迷宫。我还保留了一个变量"Turn Counter"，以避免机器人循环的情况。
2)深度优先搜索
3)让机器人随机选择方向

随机的似乎更糟糕，因为他可能要花很长时间才能找到出口(但另一方面，他也可能是最快的……)。不过，其他两个我不太确定。
还有，有没有办法进行某种启发式的学习呢？再一次，信息的缺乏让我认为这是不可能的，但也许我错过了什么。

最后一件事：当机器人找到出口时，它必须使用A*返回到开始位置。这意味着在他寻找出口的第一部分，他将画出他将在第二部分使用的迷宫地图。也许这也有助于为第一部分选择最好的算法，但我看不出为什么会有更好的算法。

有人能帮帮我吗？谢谢(另外，对不起我的英语)。

推荐答案

这样的问题被归类为实时搜索，也许最著名的例子是学习实时A*，其中你结合了关于你以前看到的信息(如果你不得不回溯或知道更便宜的方法来到达一个状态)，以及你可以采取的行动。就像reinforcement learning这样的地区一样，一定程度的随机性有助于平衡勘探和开发。

假设您的图是无向的、时间不变的，并且初始结点和退出结点存在于同一组件中，则在每个顶点随机选择一个方向相当于random walk on a graph。 不管图最初是已知的还是未知的，这是一个非常好理解的数学领域，相当于absorbing Markov chain，在这种情况下到达退出状态的时间有Discrete phase-type distribution--通常相当慢，但也值得注意的是，在病理情况下，可以设计一个迷宫，在这个迷宫中，随机行走的性能将超过DFS。

这篇关于无信息迷宫出口的优化算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！