我正在用java制作一个机器人迷宫,其中机器人使用深度优先搜索算法遍历迷宫并到达目标。这在没有循环的迷宫中工作正常,但当引入这些时算法失败。有什么方法可以使深度优先搜索与循环迷宫一起工作?如果是这样,人们该怎么做呢?
我有这个迷宫的两个独立实现 - 一个记录每个连接点并将其存储在一个数组中,而另一个使用堆栈来推送一个新连接点并在完成探索该连接点时将其弹出。使用这些实现中的任何一个的解决方案都是可以接受的。
最佳答案
您需要标记访问过的节点并将它们视为“附加”墙。
这样,您就可以避免搜索循环。不过,它将不再找到最短路径。
有关详细信息,请参阅 Dijkstra 算法。要获得更高级的定向版本,请查看 A* 搜索。不过,在困难的迷宫中,它不会给你带来太多好处。 A* 对于开放区域更有趣。
关于java - 带循环的深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13680167/