java - 带循环的深度优先搜索

Question

我正在用java制作一个机器人迷宫，其中机器人使用深度优先搜索算法来遍历迷宫并到达目标。这在没有循环的迷宫中可以正常工作，但是当引入这些时，算法会失败。有没有办法让深度优先搜索与循环迷宫一起工作？如果是这样，如何去做呢？

我有这个迷宫的两个单独的实现 - 一个记录每个连接并将其存储在一个数组中，而另一个使用堆栈来推送一个新的连接并在完成探索该连接时将其弹出。使用这些实现中的任何一种的解决方案都是可以接受的。

Answer 1

您需要标记访问过的节点并将它们视为“附加”墙壁。

这样，您可以避免搜索循环。不过，它将不再找到最短路径。

有关详细信息，请参阅 Dijkstra 算法。如需更高级的定向版本，请查看 A* 搜索。在困难的迷宫中，它不应该给你带来很多好处。A* 对于开放区域更有趣。