Heuristic Search

启发式搜索

译 by 陈雪(QQ:53352894)

必要条件

• 递归算法

主要概念

启发式搜索的主要目标是使用一个估价函数去判断所有状态的“好坏”，以提高搜索找到解的效率。

通常，估价函数表示成一个函数或是一个状态，这个函数叫做“估价函数”例如：

• 迷宫寻找出路的时候，到出口的欧几里德距离

D=[(xI-xj)^2+(yI-yj)^2]1/2。 式中，D是点i和点j之间的距离； xI xj是第i个点的坐标；yI yj是第j个点的坐标。（译者注）

• 当尝试在一场跳棋比赛中获胜时，能吃掉对手的最多棋子子

设计估价函数

直观地看，估价函数越优秀，搜索就更好（快）。问题是：怎么评价估价函数的好坏呢？

估价函数的好坏，取决于它评估一个状态好坏的能力。例如，迷宫的例子，怎么计算到出口的距离？欧几里德距离也许非常的坏，甚至是非常小的迷宫，它也可能绕很多的路：

一般来说，估价函数越好，搜索就越快。一般来说，搜索时间和估价函数的准确性如下图：

注意！一个似乎很“傻”的估价函数可以大大地提高程序的效率！（如果它非常完美地被使用）

另一个重要概念是“可接受”，一个可接受的估价函数表示对于每个点都不存在“低估”的情况。例如，迷宫的欧几里德距离启发函数是“低估”的，刚才的图例很清楚地说明了这一点。

方法1：启发式剪枝

最简单也是最常用的启发式搜索是利用估价函数来剪枝。假设我们的问题是要求找最小总花费。对于一个可接受的估价函数，当前花费是A，启发函数返回了B，当前子问的最优解是A+B。如果找到的一个解一个花费是C，C<A+B，这个状态就不必要搜索了。

这样编写和调试也比较简单（假设一个状态需要长时间而被剪掉……），且可以极大地提高程序效率。它对DFS尤其有效。

方法2：最佳优先搜索

这种方法好比就是贪心算法。

每次不扩展所有子结点，而是按“好坏程度”来扩展。与贪心不同的是，贪心只尝试“最优”路径，但是BFS首先扩展“希望大”的，再扩展“希望小”的，如果结合上述描述，搜索会得到很好的结果。

Idea #3: A* Search

方法3：A*法

A*法是类似贪心BFS的。

BFS一般扩展最小耗费的点。A*算法在另一方面，扩展最有希望的点（估价函数返回值最优）。

状态被保存在一个优先队列中，按照Cost*价值排列。每一次，程序处理最低优先的点，且把它的孩子按照适当顺序处理。

对于一个可容许的估价函数，第一个找到的状态保证是最优的。

例题

骑士覆盖[传统问题]

一个n*n的棋盘，问最少放多少骑士，使整个棋盘被攻击（骑士所在点不被攻击）

分析：可行的：启发函数总共被攻击的点/8（每个骑士最多攻击8个方各）这可以用上面任何方法实现，经管A*存在一点小问题。

8数码问题[传统问题]

大家熟悉的8数码~~~ 3*3的方格，有一个空格，可以把四个方向数移动到空格里，最后到目标状态~
5 _ 4    5 1 4
6 1 8    6 _ 8 
7 3 2    7 3 2

要求步数最少

1 2 3
4 5 6
7 8 _

启发函数：距离每个数字和最终状态位置。

分析：因为状态很小（一共只有3628800），A*会有很好效果，如果你确定没有点被扩展了两次。