经典优化算法解析：分支限界法与动态规划

分支限界法概述

分支限界法是一种用于解决组合优化问题的算法策略，主要用于求解 NP 难问题的最优解。该方法通过系统地遍历问题空间，结合剪枝策略避免无效搜索，从而在合理时间内找到最优解。与回溯法不同，分支限界法通常结合优先队列或队列来管理待处理的子问题，优先处理最有希望的节点。

核心思想是将问题分解为多个子问题（分支），并为每个子问题计算界限值（限界），通过比较界限值决定是否继续探索该分支。若某分支的界限值不优于当前已知的最优解，则该分支被剪枝。

算法流程与图文解析

1. 初始化：创建优先队列（或队列），将初始问题状态放入队列，并初始化当前最优解。
2. 循环处理：从队列中取出一个节点，生成其所有可能的子节点。
3. 界限计算：对每个子节点计算界限值。若子节点的界限优于当前最优解，则保留该节点并加入队列；否则剪枝。
4. 终止条件：队列为空或满足其他终止条件时结束。

Python 实现框架

import heapq

def branch_and_bound(initial_state):
    queue = []
    heapq.heappush(queue, initial_state)
    best_solution = None
    
    while queue:
        current = heapq.heappop(queue)
        if is_solution(current):
            if best_solution is None or current.cost < best_solution.cost:
                best_solution = current
        for child in generate_children(current):
            if child.bound < best_solution.cost:
                heapq.heappush(queue, child)
    return best_solution

C++ 实现框架

#include <queue>
#include <vector>
using namespace std;

struct State {
    int cost;
     bound;
     <( State& other)  {
         bound > other.bound; 
    }
};

{
    priority_queue<State> queue;
    queue.(initial);
    State best_solution;
    best_solution.cost = INT_MAX;
    
     (!queue.()) {
        State current = queue.();
        queue.();
         ((current)) {
             (current.cost < best_solution.cost) {
                best_solution = current;
            }
        }
         (State child : (current)) {
             (child.bound < best_solution.cost) {
                queue.(child);
            }
        }
    }
     best_solution;
}