6.5 分支限界法

文档摘要

6.5 分支限界法 6.5 分支限界法分支限界法（Branch and Bound）是一种用于求解最优化问题的算法设计范式。它是一种在问题的解空间树上进行搜索的算法，与回溯法类似，但采用广度优先或启发式搜索方式，并且使用限界函数来剪枝，从而避免搜索不必要的子树，提高搜索效率。 6.5.1 基本思想分支限界法的核心思想是：解空间树：将问题的解空间组织成一棵树，树的每个节点代表问题解的一个部分解。根节点代表问题的初始状态，叶子节点代表问题的完整解。广度优先或启发式搜索：从根节点开始，按照广度优先或启发式的方式搜索解空间树。限界函数：对每个节点计算一个限界函数，用于评估该节点所代表的部分解的优劣程度。