点这里查看
讨论 / 这题单向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

查看更多回复
提交回复