请教一个A*寻路算法的问题

如图，蓝色是起点，绿色是终点，红色是障碍物。
第一步根据A*算法肯定是向上走到（3,2），然后把（3,1）加入关闭列表。
这样的话（3,2）位置的四周都是障碍物和关闭列表中的格子，就把自己堵死了。
但是实际上从蓝色到绿色可以从下面绕过去。请问怎么解决这个问题？

从上方走失败后还原现场，回溯，重新尝试从下方走。
此题用DFS可能寻找的道路不一定最短，可以用双向广搜做

第一步把蓝色点放进closed表里，同时把蓝色相邻的点全放进open表里；第二步往上走不通的话，还会从open表里取出蓝色的下面那个点继续搜索。
其实A*可以看作一种宽度优先搜索。

我承认我和你对刚才那道题A*理解的不一样，我看到楼主问进入死胡同后有禁忌列表怎么办以为楼主用的是IDA*，因为BFS套A*是不会钻进死胡同的，于是我一直认为楼主和你说的A*都是启发式深度优先搜索，你说的A*如果是说是将花费加预期入堆后不断出堆扩展的话显然是可以的，只是理解方式有误会，并不代表什么。看清我第一句话说的什么，别在这个问题上找茬，看看你是不是有理。

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

11回复贴，共1页

<<返回算法吧

分享到:

日	一	二	三	四	五	六