启发式

启发式一词源于希腊语“heuriskein”，意为“发现”或“探索”。在计算机科学和数学中，启发式方法（Heuristic Method）是指一种利用经验法则和直觉来解决问题的策略，特别适用于那些无法通过标准算法在合理时间内找到精确解的复杂问题。与精确算法不同，启发式方法不保证最优解，而是旨在快速找到足够好的近似解。

启发式方法的核心在于通过简化问题空间、利用领域知识或模仿自然过程，从而在搜索解空间时避免穷举。其基本机制包括：

• 局部搜索：从初始解出发，逐步改进直到达到局部最优。
• 随机化：引入随机因素以跳出局部最优，如模拟退火中的概率接受较差解。
• 记忆机制：如禁忌搜索使用禁忌表记录已访问解，防止循环。

启发式方法可分为构造型、改进型和混合型三类。分类及特点见下表：

启发式方法在多个学科中广泛应用，以下列举主要领域：

• 人工智能：在路径规划中，A*算法使用启发函数估算成本，提高搜索效率。
• 数据挖掘：聚类分析中的K-means算法采用启发式迭代优化。
• 运筹学：用于解决旅行商问题、背包问题等NP难题。
• 搜索引擎：排名算法利用启发式评分相关性，如PageRank。

贪心算法

贪心算法在每一步选择当前最优策略，期望通过局部最优达到全局最优。例如硬币找零问题，优先用大面额硬币。缺点：可能陷入局部最优。

模拟退火

模拟固体退火过程，从高温开始缓慢降温，以概率接受较差解，从而避免局部最优。广泛应用于组合优化。

禁忌搜索

通过禁忌表阻止近期访问的解，允许接受劣解以探索新区域。适用于调度和布局问题。

• 不确定性：解的质量波动大，无理论保障。
• 领域依赖：需针对具体问题设计启发式规则。
• 参数敏感：如模拟退火的初始温度和降温速率影响结果。

尽管如此，启发式方法在处理大规模、非线性或动态问题上仍不可或缺。

• 王小平，曹立明. 遗传算法——理论、应用与软件实现. 西安交通大学出版社，2002.
• 张立材，谢伟. 智能算法与机器学习. 清华大学出版社，2018.
• Russell, S., Norvig, P. Artificial Intelligence: A Modern Approach. 3rd ed. Prentice Hall, 2010.
• Michalewicz, Z., Fogel, D. B. How to Solve It: Modern Heuristics. Springer, 2004.