掌握分支限界算法：旅行商问题探索与设计

本实验报告旨在软件工程专业1班的宋行健（学号：222018321062006）学习算法分析与设计课程中，探索分支—限界算法在2021年1月5日进行的实践。分支—限界算法是该课程的重要部分，它是一种在求解问题时，类似回溯法但更高效地在解空间树上进行搜索的方法。 实验的核心目标是让学生掌握分支—限界的基本思想，理解这种算法如何通过结合约束条件和目标函数的限界，有效地剪掉不包含最优解的解，从而减少无效搜索。与回溯法仅依赖约束不同，分支—限界法同时利用了这两者，确保搜索过程更精确。搜索策略采取广度优先或最小耗费优先的方式，通过计算每个活结点的函数值（限界），选择最有希望找到最优解的方向。 实验要求学生预习相关文献，熟悉分支—限界算法的工作原理，并将其应用到实际问题，如旅行商问题。在实验过程中，强调算法设计和编程习惯的培养，以及独立思考和解决问题的能力。通过实验，学生能够分析问题复杂性，评估算法的效率。 实验原理部分深入讲解了算法的执行过程，包括活结点的选择策略和子节点的处理方式，即在扩展结点处生成所有儿子结点，然后根据限界函数值淘汰非最优或不可行的解。这种方法有助于快速逼近问题的最优解，避免无谓的搜索。 本实验不仅是对理论知识的巩固，更是对学生实际操作能力和问题解决能力的锻炼，对于理解和应用分支—限界算法在实际问题中的优化作用具有重要意义。