所谓的最短路径问题有很多种意思，在这里启发式指的是在一个搜索树的节点上定义的函数
h
(
n
)
{\displaystyle h(n)}
，用于评估从此节点到目标节点成本最小的路径。启发式通常用于信息充份的搜索算法，例如最好优先贪心算法与A*。最好优先贪心算法会为启发式函数选择最低代价的节点；A*则会为
g
(
n
)
+
h
(
n
)
{\displaystyle g(n)+h(n)}
选择最低代价的节点，此
g
(
n
)
{\displaystyle g(n)}
是从起始节点到目前节点的路径的确实代价。如果
h
(
n
)
{\displaystyle h(n)}
是可接受的（admissible）意即
h
(
n
)
{\displaystyle h(n)}
未曾付出超过达到目标的代价，则A*一定会找出最佳解。
最能感受到启发式算法好处的经典问题是n-puzzle。此问题在计算错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。注意，上述两条件都必须在可接受的范围内。
启发式算法对运算性能的影响
编辑
任何的搜索问题中，每个节点都有
b
{\displaystyle b}
个选择以及到达目标的深度
d
{\displaystyle d}
，一个毫无技巧的算法通常都要搜索
b
d
{\displaystyle b^{d}}
个节点才能找到答案。启发式算法借由使用某种切割机制降低了分支因子（branching factor）以改进搜索效率，由
b
d
{\displaystyle b^{d}}
降到较低的
b
′
{\displaystyle b'}
。分叉率可以用来定义启发式算法的偏序关系，例如：若在一个
n
{\displaystyle n}
节点的搜索树上，
h
1
(
n
)
{\displaystyle h_{1}(n)}
的分叉率较
h
2
(
n
)
{\displaystyle h_{2}(n)}
低，则
h
1
(
n
)
<
h
2
(
n
)
{\displaystyle h_{1}(n) 。启发式为每个要解决特定问题的搜索树的每个节点提供了较低的分叉率，因此它们拥有较佳效率的计算能力。 找寻新的启发式算法 编辑 如何找到一个分叉率较少又通用的合理启发式算法，已被人工智能社群[哪个／哪些？]深入探究过。他们使用几种常见技术： 部分问题的解答的代价通常可以评估解决整个问题的代价，通常很合理。例如一个10-puzzle拼盘，解题的代价应该与将1到5的方块移回正确位置的代价差不多。通常解题者会先建立一个存储部分问题所需代价的模式数据库（pattern database）以评估问题。 解决较易的近似问题通常可以拿来合理评估原先问题。例如曼哈顿距离是一个简单版本的n-puzzle问题，因为我们假设可以独立移动一个方块到我们想要的位置，而暂不考虑会移到其他方块的问题。 给我们一群合理的启发式函数 h 1 ( n ) , h 2 ( n ) , . . . , h i ( n ) {\displaystyle h_{1}(n),h_{2}(n),...,h_{i}(n)} ，而函数 h ( n ) = max { h 1 ( n ) , h 2 ( n ) , . . . , h i ( n ) } {\displaystyle h(n)=\max\{h_{1}(n),h_{2}(n),...,h_{i}(n)\}} 则是个可预测这些函数的启发式函数。 一个在1993年由A.E. Prieditis写出的程序ABSOLVER就运用了这些技术，这程序可以自动为问题产生启发式算法。ABSOLVER为8-puzzle产生的启发式算法优于任何先前存在的！而且它也发现了第一个有用的解魔术方块的启发式程序。