启发式算法 启发式算法是一类通过经验、直观或探索性方法寻找复杂优化问题满意解的算法。它们不保证找到最优解，但能在合理时间内获得高质量解，尤其适用于NP难问题或大规模问题。 1. 基本概念与动机 问题背景 ：许多实际优化问题（如旅行商问题、调度问题）属于NP难问题，精确算法（如分支定界法）在问题规模较大时计算时间无法承受。 核心思想 ：放弃理论上的最优性保证，利用问题特征设计规则或策略，快速寻找近似最优解。例如，贪心策略每次选择当前最优步骤，模拟退火算法允许暂时接受较差解以跳出局部最优。 优势 ：计算效率高、易于实现，适用于实时决策或大规模场景。 2. 常见启发式算法分类 构造型启发式 ：从空解开始逐步构建可行解。例如： 最近邻算法 （旅行商问题）：从随机城市出发，每次选择距离最近的未访问城市。 调度问题中的优先规则 ：按处理时间最短优先安排任务。 改进型启发式 ：从初始解出发迭代优化。例如： 局部搜索 ：通过邻域操作（如交换两个元素）持续改进解，直到无法优化。 禁忌搜索 ：记录搜索历史以避免循环，允许暂时接受较差解。 元启发式算法 ：高级框架，可适配多种问题。例如： 遗传算法 ：模拟自然选择，通过交叉、变异操作进化解群体。 蚁群算法 ：模拟蚂蚁觅食行为，利用信息素引导搜索路径。 3. 算法设计关键要素 邻域结构 ：定义当前解的相邻解集合，如旅行商问题中交换两座城市的访问顺序。 评估函数 ：衡量解的质量，通常目标函数值结合惩罚项（针对不可行解）。 平衡探索与利用 ：避免过早陷入局部最优（如模拟退火中的温度参数控制随机性）。 4. 应用场景与局限性 典型应用 ：物流路径规划、生产调度、网络设计、机器学习超参数调优。 局限性 ：解质量依赖参数设置和问题特征；需通过实验调整策略（如初始解生成、邻域设计）。 5. 与精确算法的结合 启发式算法常与精确方法 hybrid 使用，例如： 用启发式生成初始解，加速分支定界法； 列生成算法中，启发式快速生成潜在列（变量）。 通过上述步骤，启发式算法为复杂优化问题提供了实用且灵活的求解途径。