启发式方法是一种利用简化规则、估计或选择性探索来获得有用结果的问题求解方法。在计算机科学中，启发式方法既可以是一套完整的算法，也可以是指导另一种算法的规则。当求得精确答案需要过多计算时，通常会采用启发式方法。启发式方法不一定保证结果的正确性或最优性，但有些启发式方法可以用于提供此类保证的算法之中。(xlinux.nist.gov)
适用范围与概念区分
启发式方法着眼于计算投入与解的质量之间的实际权衡。在数学优化中，一种方法可能旨在寻找足够好的可行解，而非确定最优解。例如，旅行商问题要求找到一条总长度最短的巡回路线，恰好访问每个地点一次并返回起点；当精确优化的代价过高时，启发式方法可以生成实用的巡回路线。(xlinux.nist.gov)
启发式方法不等同于近似算法。在理论计算机科学中，近似算法通常以多项式时间运行，并具有经过证明的性能保证，用以说明其结果与最优解之间的差距上限。启发式方法则未必具有这样的界限。这两类方法也可能重叠：一种实用方法可以被称为启发式方法，同时又具有形式化的近似保证。(xlinux.nist.gov)
同样，启发式并不意味着随机。有些启发式方法是确定性的，另一些则采用随机选择。元启发式方法是用于组织或指导启发式搜索的高层框架，而不是针对某个特定问题的规则。在具体实现时，必须明确候选解的表示方式、评估程序以及可采用的变换操作等与问题有关的要素。(xlinux.nist.gov)
启发式搜索
在人工智能中，启发式方法常用于指导对可能状态或部分解的探索。启发式评估函数为候选对象赋予一个估计值，使搜索过程能够优先探索更有希望的选项。对于最短路径问题，函数 (h(n)) 通常用于估计从节点 (n) 到目标的剩余代价。贪心最佳优先搜索根据这一估计值确定优先次序，而不计入已经产生的代价。(artint.info)
A* 搜索将估计的剩余代价与到达当前节点的已知代价相结合：
[ f(n)=g(n)+h(n), ]
其中，(g(n)) 是目前找到的路径的代价。搜索从搜索前沿中选择估计总代价最低的候选节点。因此，启发式信息改变的是探索顺序，而不是直接构成最终答案。(artint.info)
可采纳启发式从不高估真实的最小剩余代价。在适当条件下，包括分支数有限且边代价具有严格大于零的下界，可采纳性能够保证 A* 树搜索的最优性。对于不再考虑先前已扩展状态的图搜索实现，则需要额外注意：一致性启发式满足
[ h(n)\leq c(n,n')+h(n') ]
这一条件对从 (n) 到 (n') 的每条边都成立，并且目标节点的启发式值为零。一致性使标准 A* 图搜索能够在不重新打开已扩展状态的情况下保持最优性。对于可采纳但不一致的启发式，当发现代价更低的路径时，可能需要重新打开相应状态。(artint.info)
优化技术
贪心算法在构造解的过程中，每一步都做出局部看来最优的选择。当这种局部选择不能保证全局最优性时，这类规则就可以作为启发式方法。因此，它是否有用取决于问题的结构，而不只是每个单独选择看起来是否理想。(xlinux.nist.gov)
局部搜索则维护一个或多个完整的候选解，并通过转向邻近解来修改它们。爬山法依据目标函数反复选择能够带来改进的变换。即使其他位置存在更好的解，它也可能停在局部最优解处，而平台区域也可能使搜索难以推进。随机重启通过探索不同的初始候选解，减少对单一起点的依赖。(inst.eecs.berkeley.edu)
模拟退火有时会接受使解变差的变换，以帮助搜索跳出局部最优。随着名为“温度”的控制参数降低，接受此类变换的概率也会下降。遗传算法维护一个候选解种群，并通过选择、重组和变异生成新的候选解。这两种方法都不会自动保证在有限的计算预算内得到最优结果。(cs.ubc.ca)
性能与局限
评估启发式方法时，不能只记录它是否找到了答案。相关指标包括解的质量、运行时间、内存消耗、对初始化的敏感程度，以及多次运行之间的结果差异。对于局部搜索，邻域的定义和停止规则也会影响能够找到哪些结果。因此，比较结果既取决于问题实例，也取决于所允许使用的计算资源。(inst.eecs.berkeley.edu)
计算启发式估计值本身也有代价。信息更充分的估计可能减少需要探索的路径数量，却也可能增加每次评估所需的计算量。即使估计具有可采纳性，也不能仅凭这一点断定搜索会很快：A* 的性能可能在很大程度上取决于估计值相同时的处理规则，以及估计代价相近的候选对象数量。(artint.info)
人类判断
在心理学中，启发式方法是在不确定条件下做出判断的简化程序。阿莫斯·特沃斯基和丹尼尔·卡尼曼于 1974 年发表的研究描述了代表性启发式、可得性启发式以及锚定与调整。代表性启发式通过相似程度判断可能性；可得性启发式依据回忆或想象实例的容易程度做出判断；锚定则从一个初始值出发，再进行调整。这些程序可能很有用，但也可能在概率判断中造成系统性错误。启发式是判断程序，而偏差是使用该程序后可能产生的系统性错误模式。(cebma.org)
参考来源
- heuristicxlinux.nist.gov
- approximation algorithmxlinux.nist.gov
- metaheuristicxlinux.nist.gov
- 6 Informed (Heuristic) Search — Artificial Intelligence: Foundations of Computational Agents, 3rd Editionartint.info
- CS 188, Fall 2022, Note 2inst.eecs.berkeley.edu
- 5 Local Search — Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
- Local Searchcs.cmu.edu
- 6 Local Search — Artificial Intelligence: Foundations of Computational Agents, 3rd Editioncs.ubc.ca
- Judgment under Uncertainty: Heuristics and Biasescebma.org