寻找无信息迷宫出口的最佳算法
Optimal algorithm to find exit of a maze with no information
我必须确定机器人走出迷宫的方法。问题是迷宫的布局不明，出口的位置也不明。机器人也从迷宫中的一个未知位置开始。
我找到了 3 个解决方案，但我很难知道我应该使用哪一个，因为最终似乎这些解决方案将完全是随机的。
我有这 3 个解决方案：
1) 基本的 "human" 策略(?)，你把手放在墙上，必要时穿过所有的迷宫。我还保留了一个变量 "turn counter" 以避免机器人循环的情况。
2) 深度优先搜索
3）让机器人随机选择方向
随机的似乎更糟，因为他可能要花很长时间才能找到出口（但另一方面他也可能是最快的...）。不过我不确定其他两个。
另外，有没有办法进行某种启发式？再次缺乏信息让我认为这是不可能的，但也许我遗漏了一些东西。
最后一件事：当机器人找到出口时，他将不得不使用 A* 回到他的起始位置。这意味着在他寻找出口的第一部分中，他将绘制一张他将在第二部分中使用的迷宫地图。也许这也有助于为第一部分选择最佳算法，但是是的，我不明白为什么一个会更好。
有人可以帮我吗？谢谢（另外，对不起我的英语）。
@beaker 是正确的，因为您建议的前两个应该导致相同的结果。但是，您可以通过跟踪找到的任何循环来稍微改进搜索。如果机器人发现自己在一个它已经去过的地方并且一旦走到死胡同需要原路返回，那么如果它找到了一条捷径，那么可能不需要原路返回那么远。还使用在出路时已映射的段，并在其上应用 Dijkstra 算法或 A* 以找到最有效的返回方式。在未探索的路径上可能有更快的返回方式，但这是快速获得结果的最安全方式。
显然，这种实现循环检查以防止不必要的回溯会使实现起来更加复杂。虽然对于 return 开始使用 Dijkstra 算法应该不会那么复杂。
如果您在找到出口后感到雄心勃勃，您可以使用此信息并为机器人提供方向感，尽管在随机生成的迷宫中可能没有多大帮助。
像这样的问题被归类为实时搜索，也许最著名的例子是 Learning Real-Time A*，您可以在其中结合您之前看到的信息（如果您不得不回溯或知道到达一个州的更便宜的方式），以及你可以采取的行动。与 reinforcement learning 等领域的情况一样，一定程度的随机性有助于平衡探索和开发。
假设你的图是无向的、时不变的，并且初始节点和出口节点存在于同一个组件中，那么在每个顶点随机选择一个方向相当于random walk on a graph。
不管该图最初是否已知，这是一个非常容易理解的数学领域，相当于 absorbing Markov chain, the time to reach the exit state in such cases has a Discrete phase-type distribution - 通常很慢，但同样值得注意的是，在病理情况下，可以设计一个迷宫，其中随机游走将胜过 DFS。
我必须确定机器人走出迷宫的方法。问题是迷宫的布局不明，出口的位置也不明。机器人也从迷宫中的一个未知位置开始。
我找到了 3 个解决方案，但我很难知道我应该使用哪一个，因为最终似乎这些解决方案将完全是随机的。
我有这 3 个解决方案：
1) 基本的 "human" 策略(?)，你把手放在墙上，必要时穿过所有的迷宫。我还保留了一个变量 "turn counter" 以避免机器人循环的情况。
2) 深度优先搜索
3）让机器人随机选择方向
随机的似乎更糟，因为他可能要花很长时间才能找到出口（但另一方面他也可能是最快的...）。不过我不确定其他两个。
另外，有没有办法进行某种启发式？再次缺乏信息让我认为这是不可能的，但也许我遗漏了一些东西。
最后一件事：当机器人找到出口时，他将不得不使用 A* 回到他的起始位置。这意味着在他寻找出口的第一部分中，他将绘制一张他将在第二部分中使用的迷宫地图。也许这也有助于为第一部分选择最佳算法，但是是的，我不明白为什么一个会更好。
有人可以帮我吗？谢谢（另外，对不起我的英语）。
@beaker 是正确的，因为您建议的前两个应该导致相同的结果。但是，您可以通过跟踪找到的任何循环来稍微改进搜索。如果机器人发现自己在一个它已经去过的地方并且一旦走到死胡同需要原路返回，那么如果它找到了一条捷径，那么可能不需要原路返回那么远。还使用在出路时已映射的段，并在其上应用 Dijkstra 算法或 A* 以找到最有效的返回方式。在未探索的路径上可能有更快的返回方式，但这是快速获得结果的最安全方式。
显然，这种实现循环检查以防止不必要的回溯会使实现起来更加复杂。虽然对于 return 开始使用 Dijkstra 算法应该不会那么复杂。
如果您在找到出口后感到雄心勃勃，您可以使用此信息并为机器人提供方向感，尽管在随机生成的迷宫中可能没有多大帮助。
像这样的问题被归类为实时搜索，也许最著名的例子是 Learning Real-Time A*，您可以在其中结合您之前看到的信息（如果您不得不回溯或知道到达一个州的更便宜的方式），以及你可以采取的行动。与 reinforcement learning 等领域的情况一样，一定程度的随机性有助于平衡探索和开发。
假设你的图是无向的、时不变的，并且初始节点和出口节点存在于同一个组件中，那么在每个顶点随机选择一个方向相当于random walk on a graph。 不管该图最初是否已知，这是一个非常容易理解的数学领域，相当于 absorbing Markov chain, the time to reach the exit state in such cases has a Discrete phase-type distribution - 通常很慢，但同样值得注意的是，在病理情况下，可以设计一个迷宫，其中随机游走将胜过 DFS。