分支限界法：扩展节点与最优解搜索

分支限界法是一种在搜索问题解空间树时使用的高效算法，它在求解最优化问题中尤其重要，如单源最短路径问题、装载问题、布线问题、背包问题、最大团问题、旅行售货员问题等。与回溯法相比，分支限界法的目标更为明确，即寻找满足约束条件的最优解或者在特定意义上最好的解。 在分支限界法的执行过程中，搜索策略通常采用广度优先或最小耗费（最大效益）优先的方式。每个活结点在成为扩展结点后，会一次性产生其所有儿子结点，其中不满足条件的结点会被放弃，其余结点则加入活结点表。这一过程确保了算法在尽可能减少无效探索的同时，朝着最优解方向前进。 分支限界法的关键区别在于扩展结点的选择策略。例如，队列式分支限界法按结点进入队列的顺序决定扩展，而优先队列式分支限界法则依据优先级规则，可能是最大优先（体现最大效益），也可能是最小优先（体现最小费用）。在举例中，背包问题（队列式分支限界）展示了如何通过限制物品的容量和价值，逐步筛选出最优解的过程。 在背包问题的示例中，A状态表示初始状态，随着物品1、2和3依次加入考虑范围，算法不断评估每个组合的可行性，比如节点J和K因剩余容量不足而判定为不可行。当找到一个满足条件的解，如节点L，虽然总价值超过限制，但它是当前最佳选择，因为没有其他儿子结点能提供更高的价值。随着搜索的深入，算法最终到达最优解节点N，选择(0,1,0)，这代表选择了价值25的第二个物品，达到最大效益且不超过容量限制。 分支限界法通过控制扩展结点的策略，有效地减少了搜索空间，使得在复杂问题中能够找到最佳解或最优解，是解决优化问题的重要算法手段。理解并掌握分支限界法对于IT专业人员在解决实际问题中具有很高的实用价值。