我必须确定一个机器人走出迷宫的方法。问题是迷宫的布局是未知的，出口的位置也是未知的。机器人也从迷宫中一个未知的位置开始。我找到了3个解决方案，但我很难知道我应该使用哪一个，因为最终的解决方案似乎完全是随机的。我有三个解决方案:
1)基本的"人类"策略，即你将手放在墙上，并在必要时穿过所有迷宫。我还保留了一个变量"转弯计数器"，以避免机器人循环的情况。
2)深度优先搜索
3)使机器人随机选择方向
随机的那个似乎更糟，因为他可能永远找不到出口(但另一方面他也可能是最快的…)。但我不确定其他两个。
还有，有没有一种启发式的方法?同样，信息的缺乏让我认为这是不可能的，但也许我遗漏了什么。
最后一件事:当机器人找到出口时，他将不得不使用A*返回到他的起始位置。这意味着在第一部分中，当他寻找出口时，他将绘制迷宫地图，并将在第二部分中使用。也许这可以帮助我们选择第一部分的最佳算法，但是我不明白为什么一个会更好。
有人能帮我一下吗?谢谢(也很抱歉我的英语不好)。这样的问题被归类为实时搜索，也许最著名的例子是Learning real-time A*，其中你结合了你之前看到的信息(如果你不得不回溯或知道到达某个状态的更便宜的方法)，以及你可以采取的行动。与强化学习等领域一样，一定程度的随机性有助于平衡探索和利用。
假设你的图是无向的，时不变的，并且初始节点和退出节点存在于同一组件中，那么在每个顶点随机选择一个方向相当于在图上随机行走。无论图形最初是否已知，这是一个非常容易理解的数学领域，相当于吸收马尔可夫链，在这种情况下达到退出状态的时间具有离散相位型分布-通常相当缓慢，但也值得注意的是，在病理情况下，可以设计一个迷宫，其中随机行走将优于DFS。
@beaker是正确的，你建议的前两个应该导致相同的结果。然而，你可以通过跟踪你发现的任何循环来改进搜索。如果机器人发现自己在一个它已经去过的地方，并且一旦进入死胡同就需要往回走，那么如果它已经找到了一条捷径，那么它可能不需要往回走那么远。也可以使用在出口时已经映射的段，并应用Dijkstra算法或A*来找到最有效的返回方式。在未探索的路径上可能有更快的返回方法，但这将是获得快速结果的最安全方法。
显然，实现循环检查以防止不必要的反向跟踪将使实现变得更加复杂。虽然对于返回到开始使用Dijkstra的算法不应该那么复杂。
如果你现在觉得有野心，找到了出口，你可以利用这个信息，给机器人一个方向感，虽然在一个随机生成的迷宫，可能没有多大帮助。