哈工大计算机科学与工程系的骆吉洲老师的《算法导论》PPT写得很不错，摘录如下
Hill
Climbing算法
1. 构造由根组成的单元素栈S;
2. If Top(S)是目标节点
Then 停止;
3. Pop(S);
4.
S的子节点按照其启发测度由大到小的顺序压入S;
5. If
S空 Then
失败 Else goto
2.
Best-First Search算法
1. 使用评价函数构造一个堆H, 首先构造由根组成的单元素堆;
2. If H 的根 r
是目标节点Then停止;
3. 从 H 中删除 r, 把
r 的子节点插入H;
4. If H 空 Then
失败 Else goto 2.
BBS(分支界限策略)的原理
一边搜索一边记录以前搜索过的最大（最小）界，以及时剪除不必要的搜索
产生分支的机制(使用前面的任意一种策略)
产生一个界限(可以通过发现可能解)
进行分支界限搜索, 即剪除不可能产生优化解的分支.
A*算法与分支界限策略的比较
分支界限策略是为了剪掉不能达到优化解的分支
分支界限策略的关键是“界限”
A*算法的核心是告诉我们在某些情况下,
我们得
到的解一定是优化解, 于是算法可以停止
A*算法试图尽早地发现优化解
A*算法经常使用Best-first策略求解优化问题
A*算法关键—代价函数
对于任意节点n
g(n)＝从树根到n的代价
h*(n)＝从n到目标节点的优化路径的代价
f*(n)＝g(n) + h*(n)是节点n的代价
What is the value of h*(n)?
不知道！
于是, f*(n)也不知道
估计h*(n)
使用任何方法去估计h*(n), 用h(n)表示h*(n)的估计
h(n)<=h*(n)总为真
f(n)=g(n)+h(n)<=g(n)+h*(n)=f*(n)定义为n的代价
A*算法
(1). 使用Best-first策略搜索树;
(2). 节点n的代价函数为f(n)=g(n)+h(n), g(n)是
从根到n的路径代价, h(n)是从n到某个目
标节点的优化路径代价;
(3). 对于所有n, h(n)h*(n);
(4). 当选择到的节点是目标节点时, 算法停止, 返回一个优化解.
附注：STL里面进行堆操作可用下面函数。
make_heap 建大顶堆
sort_heap 利用堆进行堆排序
push_heap 和 make_heap 插入元素到堆里
pop_heap 删除堆顶元素
