这段时间做了不少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值不可能再次改变了。