我需要确定一种让机器人走出迷宫的方法。问题在于迷宫的布局未知，出口的位置也未知。机器人也在迷宫中的未知位置开始。我找到了三种解决方案，但很难决定应该使用哪一种，因为最终这些解决方案似乎都将是随机的。我有以下三种解决方案：
1) 基本的“人类”策略（？），你将手放在墙上，如果必要的话穿过整个迷宫。我还保留了一个“转弯计数器”变量，以避免机器人陷入循环的情况。
2) 深度优先搜索
3) 让机器人随机选择方向

随机的那个似乎是最差的，因为他可能永远找不到出口（但另一方面，他也可能是最快的…）。不过，我对另外两个不是很确定。
另外，有没有可能使用某种启发式方法？同样，由于缺乏信息，我认为这是不可能的，但也许我错过了什么。

最后一点：当机器人找到出口时，他将不得不使用A*返回到他的起始位置。这意味着在第一部分，他寻找出口时，他将需要绘制迷宫的地图，以便在第二部分使用。也许这也可以帮助选择第一部分的最佳算法，但确实我不明白为什么一种会比另一种更好。

有人能帮帮我吗？谢谢（另外，对不起我的英语不好）。

回答：

像这样的问题被归类为实时搜索，也许最著名的例子是学习实时A*，你结合了之前看到的信息（如果你不得不回溯或知道到达某个状态的更便宜的方法），以及你可以采取的行动。正如在强化学习等领域那样，某种程度的随机性有助于平衡探索和利用。

假设你的图是无向的，时间不变的，并且初始节点和出口节点存在于同一组件中，那么在每个顶点随机选择方向相当于在图上的随机游走。无论图最初是否已知，这都是一个非常成熟的数学领域，相当于一个吸收马尔可夫链，在这种情况下到达出口状态的时间具有离散相位类型分布 – 通常相当慢，但也值得注意的是，在病态情况下，可以设计一个迷宫，使随机游走的表现超过DFS。