分支限界法与子集树：优化问题搜索策略

"厦门大学算法课件中的子集树与分支限界法" 分支限界法是一种在解决最优化问题时广泛使用的搜索策略，它源于广度优先搜索，并结合了剪枝技术以提高效率。该方法的主要目的是在解空间树中寻找最优解，而解空间树通常由子集树或排列树等形式表示。与回溯法不同，分支限界通常采用广度优先或最小耗费优先的方式进行搜索。 在分支限界法中，解空间树的每个节点代表问题的部分解决方案，通过扩展节点来探索更多的可能性。为了有效地剪枝，我们需要定义上下界，即当前已知的最好解的目标函数值。对于最小化问题，如果在某个节点处计算出的下界超过了已知的最优上界，那么这个节点及其子节点将不再被扩展，因为它们无法给出更优解。反之，对于最大化问题，如果上界小于或等于下界，该分支也会被剪掉。 实现分支限界法的关键步骤包括： 1. 定义解空间，确保其中包含问题的最优解。 2. 组织解空间，如构建图或树结构，便于搜索。 3. 使用广度优先搜索策略，配合限界函数排除无效分支。 在实际操作中，分支限界法会维护一个活节点表，每次从表中选择一个节点进行扩展。扩展节点时，会生成所有可能的子节点，删除无解的节点，并将剩余的节点加入活节点表。节点的选择方式可以是先进先出（FIFO）原则，也可以依据其他策略，如优先级队列，根据目标函数值选择最有希望的节点。 分支限界法是一种系统化的搜索策略，它在回溯法的基础上增加了对解空间的全局控制，通过上下界和限界函数进行剪枝，减少了不必要的计算，从而更高效地找到最优化问题的解。在厦门大学的算法课件中，这一概念被详细讲解，有助于学习者深入理解如何在实际问题中应用分支限界法。