在计算机科学、人工智能和最优化领域，人们设计出启发式算法来解决那些用常规方法解决起来太慢的问题，或者找出一个对精确结果的近似。使用启发式算法是对最优性、完全性、准确度、精确度和计算速度之间的权衡。
启发式算法常常用于图搜索，称为启发式搜索算法。启发式搜索算法包含一个启发式方程，$h(n)$，它可以给出从一个给定节点到目标节点（即终点）所需要走的路径开销（长度、时间等）的一个估计。如果给定的节点就是目标节点，则$h(n)$必须等于0。
许多搜索问题都是NP完全问题，所以在最坏情况下，时间复杂度为指数级。然而一个好的启发式搜索算法可以：
- 在平均情况下，可以很高效地找到一个解
- 高效地找到一个相当好（但不一定是最优）的解
下面，我们研究三种启发式搜索算法：最佳优先搜索（Best-First Search）、集束搜索（Beam Search）和 A* 算法
最佳优先搜索
这是一张某地区的地图，图中每条边上的数字表示两地之间的实际距离。我们的目标地为Bucharest，下表是利用启发式函数$h(n)$计算出来的每个城市到Bucharest的距离估计，这里是通过计算两个城市之间的直线距离来估计它们
之间的路程。
| City | Straight-line distance |
|---|---|
| Arad | 366 |
| Bucharest | 0 |
| Craiova | 160 |
| Dobreta | 242 |
| Eforie | 161 |
| Fagaras | 178 |
| Giurgiu | 77 |
| Hirsova | 151 |
| Iasi | 226 |
| Lugoj | 244 |
| Mehadia | 241 |
| Neamt | 234 |
| Oradea | 380 |
| Pitesti | 98 |
| Rimnicu Vilcea | 193 |
| Sibiu | 253 |
| Timisoara | 329 |
| Urziceni | 80 |
| Vaslui | 199 |
| Zerind | 374 |
最佳优先搜索在广度优先搜索的基础上，用启发估价函数对将要被遍历到的点进行估价，选择代价小的进行遍历，直到找到目标节点或遍历完所有点，算法结束。
最佳优先搜索维持着一个优先队列open和一个队列closed。其中，open用来存储将要遍历的节点，closed存储已经遍历了的节点。最佳优先搜索的过程可以被描述为：
- 将根节点放入优先队列open中
- 从优先队列中取出优先级最高的节点X。
- 根据节点X生成子节点Y:
- 若X的子节点Y不在open队列或者closed中，由估价函数计算出估值，放入open队列中。
- 若X的子节点Y在open队列中，且估值优于open队列中的子节点Y，将open队列中的子节点Y的估值替换成新的估值并按优先值排序。
- X的子节点Y在closed集中，且估值优于closed集中的子节点Y，将closed集中的子节点Y移除，并将子节点Y加入open优先队列。
- 将节点X放入closed集中。
- 重复过程2,3,4直到目标节点找到，或者open为空，程序结束。
在这个例子中，我们从Arad出发，利用最佳优先搜索找出一条Arad-Bucharest的路径。第一步，可以走的三个城市为Sibiu，Timisoara和Zerind，它们三个到Bucharest的距离估计值分别
为253，329和374，所以我们选择Sibiu作为第一步走的城市。依次类推，如下图所示：
所以，我们利用最佳优先搜索选择出来的路径就是：Arad–Sibiu–Fagaras–Bucharest，然而它并不是最优的路径。最优的路径是Arad–Sibiu–Rimnicu Vilcea–Pitesti–Bucharest。这是因为最佳优先搜索算法只关心距终点的剩余距离而不关心距离总和的大小。
算法特点
- 不完全，可能会陷入一个环中无限循环（启发函数在这条环上都指出环上的下一个节点最优）。然而，大多数合理的启发函数可以避免这种问题。
- 最坏情况的时间复杂度仍为$O(b^m)$，其中$m$是最大深度。
- 由于必须将未展开的节点存储到优先队列中，所以空间复杂度为$O(b^m)$
- 然而对于大多数问题来说，一个好的启发式函数避免遇到最坏情况
集束搜索（Beam Search）
在最佳优先搜索中，优先队列可能变得很长。这样，一方面会占用很大空间，另一方面，每次插入和删除都要对整个优先队列排序，开销很大。集束搜索正是基于这一点进行了改进，它将优先队列限制在一定的长度$n$，这使得集束搜索变得可能找不到目标点，但可以很大程度提高算法的性能。
对刚才的例子，采用$n=2$，则集束搜索的过程如下图所示：
A*搜索算法：最小化全局路径开销
A*算法结合了常规方法（完备、最优、低效）和最佳优先搜索（不完备、非最优、高效）。
A*算法在进行优先队列排序时使用的全局评价函数$f(n)$，$f(n)=g(n)+h(n)$。其中，$g(n)$是对已走路程的测量，是实际值而非估计值。
记$h_0(n)$节点$n$到目标节点的实际距离，若$h(n)$总是小于等于$h_0(n)$，我们就说$h(n)$是可接纳的。如果$h(n)$是可接纳的，那么$f(n)$就不会高估任何经过节点$n$的最佳路径。
如果$h(n)$是可接纳的，那么A*算法总能找到一条到目标节点的最优路径(证明详见参考资料3)
对上面的例子，用A*算法的解决过程如下：
算法特点
- A*算法是完全的只要：
- 分支数目总是有限的
- 每一步增加的开销均大于0
- 最坏情况下的时空复杂度仍为$O(b^m)$
- 然而对大多数问题，一个好的启发式函数可以在合理时间内找到最优解
- 空间开销问题比时间开销问题更严重
性能评价
一般可以用在某个具体问题上的实验结果来进行评价：常用的评价指标有遍历的节点数、CPU时间等。
另一个有用的指标是有效分支数：如果一个方法展开了$N$个节点，找到了一个深度为$d$的解。若一个深度为$d$平衡树需要分支数为$b’$才能包含$N$个节点，那么这个方法的有效分支数就为$b’$。即
$$N=1+b’+(b’)^2+\cdots+(b’)^d$$
下图是对于8-Puzzle问题做的实验结果：
其他
由于A*算法遍历了所有$f$值比最优路径$f$值小的节点，所以选一个$h$值比较大的启发式函数总是更好的，只要它小于$h_0(n)$就行。
有两个启发式函数$h_1$和$h_2$，如果对每个节点都有$h_1(n) \le h_2(n)$，那么我们认为$h_2$比$h_1$具有更大的信息量，优于$h_1$
一个启发式函数应该易于计算