有信息搜索(Informed Search)：

1. 又称为启发式搜索(Heuristic Search)

2. 搜索过程中利用与问题有关的经验信息

3. 引入估计函数(evaluation function)来估计节点位于解路径上的“希望”，函数值越小“希望”越大

4. 搜索过程中按照估价函数的大小对OPEN表进行排序，每次选择估价函数值最小的节点作为下一步考察的节点

5. At the heart of such algorithms is the concept of a heuristic function(启发函数)

6. 与前面将搜索策略同一到"图一般搜索策略"的框架下类似，将一般策略稍作修改，可建立有信息搜索的一般搜索策略-----“最佳优先搜索”，也称为有序搜索.

 

启发函数(Heuristic Function)

用来描述经验信息;描述从当前这个节点到目标节点的最优路径代价的估计.

一般用h(n)来表示.

 

A算法：

f(x) = g(x) +h(x)

1. g(x)：从起始状态到当前状态x的代价

2. h(x)：从当前状态x到目标状态的估计代价(启发函数)

 

A*算法：

仅仅只是加了一定的限制条件;

g(x)必须大于0，其次h(x)的要求是必须是不大于x到目标的实际代价.

注意：A算法并不能保证一定找到最优解，然后A*算法可以保证一定找到最优解.

 

一致性：

能够满足一个不等式，h(n) <= c(n, a, n’) + h(n’)

if h is consistent, we have f(n’) = g(n’) + h(n’)

列子八数码：

估价函数的定义：

f(x) = g(x) + h(x);

h(x)：从初始状态到x需要进行的移动操作次数.

g(x)：

1. 当前放错位置的棋子的个数

2. 所有棋子和目标位置的曼哈顿距离之和

曼哈顿距离：两点之间水平距离和垂直距离之和

仍满足估价函数的限制条件.

 

如果h2(n) >= h1(n)；纳闷我们就说h2(n)与h1(n)相比是占优的.