讨论 / 这题单向BFS行不行?
Mato完整版 2012-01-31 22:58:00
点我顶贴 收藏 删除
我觉得单向BFS的空间不会出现问题,最多3M,足够了,

而时间问题,用哈希就行了。

#1 Jollwish@2008-08-24 06:51:00
回复 删除
A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索,但不同的是每生成一个子结点需要计算估价函数F,以估算起始结点到该结点的代价及它到达目标结点的代价的和;每当扩展结点时,总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象,以便使搜索尽量沿最有希望的方向进行。

因此,A*算法只要求产生问题的全部状态空间的部分结点,就可以求解问题了,搜索效率较高。

确定估价函数方法通常是:搜索到该结点的深度+ 距离目标最近的程度。

(摘自酷叶)

#2 Mato完整版@2008-08-24 07:09:00
回复 删除
反正我单向BFS+哈希AC了。
#3 Mato完整版@2008-08-24 07:15:00
回复 删除
这题是够难的,

我从今天下午就开始做,一直到现在才做完,程序100多行。

(要是双向BFS保证更恐怖)

#4 woshimishuo@2012-01-31 22:58:00
回复 删除
49行单向+hash就能AC

RT

查看更多回复
提交回复