用 C plus plus 写分支限界算法

分支限界算法是一种常见的搜索算法，可以用于解决许多优化问题。下面是一个用C++实现分支限界算法的示例：

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

// 定义状态结构体
struct State {
    int x; // 当前节点的x坐标
    int y; // 当前节点的y坐标
    int cost; // 当前节点的代价
    State(int x, int y, int cost) : x(x), y(y), cost(cost) {}
};

// 定义比较器，用于优先队列中的节点排序
struct Compare {
    bool operator()(const State& s1, const State& s2) const {
        return s1.cost > s2.cost;
    }
};

// 定义分支限界算法
int branchAndBound(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    priority_queue<State, vector<State>, Compare> pq;
    pq.push(State(0, 0, grid[0][0]));
    while (!pq.empty()) {
        State s = pq.top();
        pq.pop();
        if (s.x == m - 1 && s.y == n - 1) {
            return s.cost;
        }
        if (s.x + 1 < m) {
            pq.push(State(s.x + 1, s.y, s.cost + grid[s.x + 1][s.y]));
        }
        if (s.y + 1 < n) {
            pq.push(State(s.x, s.y + 1, s.cost + grid[s.x][s.y + 1]));
        }
    }
    return -1;
}

// 测试
int main() {
    vector<vector<int>> grid{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    cout << branchAndBound(grid) << endl; // 输出15
    return 0;
}

在上面的代码中，我们首先定义了一个状态结构体，用于存储节点的坐标和代价。然后定义了一个比较器，用于优先队列中的节点排序。接着，我们定义了分支限界算法函数，使用优先队列维护搜索过程中的状态，并将当前状态的下一步状态加入到队列中，直到找到目标节点或队列为空为止。最后，我们进行了简单的测试，输出了结果。

需要注意的是，分支限界算法的实现方式有很多种，具体实现方式要根据问题的具体情况而定。在实际应用中，还需要考虑如何剪枝以提高算法效率。