SEARCH总结

这段时间做了不少seach。现在来总结一下。

1、关于dfs和dfs-id。

应当考虑到的剪枝有:上界,下界,可行性剪枝,最优性剪枝。

TIPS:也许给数据排下序会有更强大的剪枝。

2、bfs

hash很重要

3、双向bfs

动态调整搜索方向很重要,即取节点少的一边去扩展。

4、A*

这个是老大,这个是重点,传说中最快的搜索。

f(s)=g(s)+h(s)——h是估价函数。

再次来重点:

估价函数h(s)的条件:1、h(s)必须是从s到达目标点的下界。2、h(s1)<=h(s2)+c[s1,s2]。c是转移代价。

然后是A*的实现:

一个堆,一个hash list(没有删除操作)。然后每次取堆顶元素(注意,堆顶元素的f值不可能再次改变)

然后扩展,如果扩展出来的节点hash list里没有,那就加入堆,否则如果扩展出来的点的F值小于堆中的,就更新堆。然后当目标节点出现在堆顶的时候,就可以输出了。因为堆顶元素的f值不可能再次改变了。

留下评论

您的电子邮箱地址不会被公开。