分支限界法实验：步骤、C++ 代码和总结

分支限界法是一种用于解决组合优化问题的有效算法。它通过不断分支和剪枝，逐步缩小搜索空间，快速找到最优解。在本实验中，我们将通过实现分支限界法的框架代码，并根据具体问题设计计算上下界的函数，成功解决一个组合优化问题。

实验步骤

确定要解决的问题，例如解决一个组合优化问题。
设计问题的模型，定义目标函数和约束条件。
实现分支限界法的框架代码，包括定义节点数据结构、优先队列、计算上下界等函数。
在主函数中初始化初始节点，将其放入优先队列中。
在循环中，不断从优先队列中取出节点，计算其上下界，若上界小于当前最优解则剪枝，否则将其分支并加入优先队列。
重复步骤 5，直到优先队列为空或找到满足条件的解。
输出最优解或无解的信息。

C++ 代码示例

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

// 定义节点数据结构
struct Node {
    int level; // 当前节点所在的层数
    int value; // 当前节点的价值
    int weight; // 当前节点的重量
    float bound; // 当前节点的上界
};

// 优先队列按bound从大到小排序
struct CompareNodes {
    bool operator()(const Node& node1, const Node& node2) {
        return node1.bound < node2.bound;
    }
};

// 计算节点的上界
float calculateBound(Node node, int n, int* values, int* weights, int capacity) {
    int remainingWeight = capacity - node.weight; // 剩余容量
    float bound = node.value; // 初始上界为当前节点的价值
    int level = node.level + 1; // 下一层级
    int totalWeight = node.weight; // 当前节点的总重量
    while (level < n && remainingWeight >= weights[level]) {
        remainingWeight -= weights[level]; // 减去当前物品的重量
        bound += values[level]; // 加上当前物品的价值
        level++;
    }
    if (level < n) {
        bound += (float)remainingWeight * values[level] / weights[level]; // 加上部分物品的价值
    }
    return bound;
}

// 分支限界法求解组合优化问题
int branchAndBound(int n, int* values, int* weights, int capacity) {
    priority_queue<Node, vector<Node>, CompareNodes> pq; // 优先队列存储节点
    Node initialNode{ -1, 0, 0, 0 }; // 初始节点
    pq.push(initialNode); // 将初始节点放入优先队列
    int maxProfit = 0; // 当前最优解的价值
    while (!pq.empty()) {
        Node currentNode = pq.top(); // 取出优先队列中的节点
        pq.pop();
        if (currentNode.bound > maxProfit) { // 节点的上界大于当前最优解才进行计算
            Node leftNode{ currentNode.level + 1, currentNode.value + values[currentNode.level + 1], 
                           currentNode.weight + weights[currentNode.level + 1], 0 }; // 左子节点
            Node rightNode{ currentNode.level + 1, currentNode.value, currentNode.weight, 0 }; // 右子节点
            // 计算左子节点的上界
            leftNode.bound = calculateBound(leftNode, n, values, weights, capacity);
            // 计算右子节点的上界
            rightNode.bound = calculateBound(rightNode, n, values, weights, capacity);
            if (leftNode.weight <= capacity && leftNode.value > maxProfit) {
                maxProfit = leftNode.value; // 更新当前最优解
            }
            if (leftNode.bound > maxProfit) {
                pq.push(leftNode); // 加入优先队列进行下一次迭代
            }
            if (rightNode.bound > maxProfit) {
                pq.push(rightNode); // 加入优先队列进行下一次迭代
            }
        }
    }
    return maxProfit;
}

int main() {
    int n = 4; // 物品数量
    int values[] = { 5, 10, 15, 7 }; // 物品价值
    int weights[] = { 4, 7, 10, 5 }; // 物品重量
    int capacity = 15; // 背包容量

    int maxProfit = branchAndBound(n, values, weights, capacity);
    cout << "最优解的价值为：" << maxProfit << endl;

    return 0;
}

实验总结

分支限界法是一种用于解决组合优化问题的有效算法。通过不断分支和剪枝，可以逐步缩小搜索空间，快速找到最优解。实验中，我们通过实现分支限界法的框架代码，并根据具体问题设计计算上下界的函数，成功解决了一个组合优化问题。实验结果表明，分支限界法能够高效地找到最优解，并且在搜索过程中进行剪枝，减少了不必要的计算，提高了算法的效率。总而言之，分支限界法是一种强大的优化算法，可以应用于各种组合优化问题的求解。