如何能让搜索更“聪明”？
• 通用搜索策略在搜索过程中，不对状态优劣进行判断，仅按照固定方式搜索。

• 但很多时候我们对两个状态的优劣是有判断的。

启发函数
• 启发函数：
– 估计当前状态与目标状态的接近程度。
– 表示为一个可以量化的函数 h(x) 。
• 是启发式搜索的关键，通常可以是：
– 当前节点到目标的某种距离或者差异的度量；
– 当前节点处于最佳路径的概率；
– 某种条件下的主观 if-then 规则；

Method A：
– 当前棋局与目标棋局之间错位的牌的数量，错数最少者最优。
– 然而，这个启发方法没有考虑到距离因素，棋局中“1”“2”颠倒，与“1”“5”颠倒，虽然错数是一样的，但是移动难度显然不同。
Method B 改进：
– 更好的启发方法是“错位的牌距离目标位置的距离和最小”。
– Method B 仍然存在很大的问题：没有考虑到牌移动的难度。两张牌即使相差一格，如“1”“2”颠倒，将其移动至目标状态依然不容易。

• Method C 改进：
– 在遇到需要颠倒两张相邻牌的时候，认为其需要的步数为一个固定的数字。
• Method D 改进：
– 将 B 与 C 的组合，考虑距离，同时再加上需要颠倒的数量。

单纯依靠启发函数搜索是否可行？
• 对于一个具体问题，我们可以定义最优路线：“从初始节点出发，以最优路线经过当前节点，并以最优路线达到终止节点”。
– 通用搜索，只考虑了前半部分，能计算出从初始节点走到当前节点的优劣。
– 启发函数则只“估计”了当前节点到 终节点的优劣。
• 两者相结合，就是启发式搜索策略。

启发函数的优劣
• 不同的启发函数之间有优劣吗？——有
– 八格游戏中，4 种启发函数逐渐添加更多“知识”，从而变得越来越“合理”。
– 启发知识是否可以无限添加？
– 过大的启发值将淹没实际代价 g(n)，使得搜索脱离实际。
– 因此启发函数应该有上限。

语音词图中的启发式搜索
在统计语音识别过程中，计算机将用户的每个发音转化成若干可能的词，构建如下的词图，语音识别的任务就是要在这样的词图中寻找最有可能组成合理句子的组合。