C++利用分支界限法求有向带权图

分支界限法（Branch and Bound）是一种解决优化问题的算法，可以应用在许多领域。在有向带权图中，我们可以使用分支界限法来求解最短路径或者最小费用路径。

以下是使用C++实现分支界限法求有向带权图的步骤：

1. 定义数据结构

我们需要定义一个数据结构来存储有向带权图，包括顶点数量、边数量、每条边的起点、终点和权值。可以使用邻接矩阵或邻接表来表示有向带权图。

struct Edge {
int from;
int to;
int weight;
};

struct Graph {
int V; // 顶点数量
int E; // 边数量
vector<Edge> edges; // 存储每条边的信息
};

2. 定义状态

我们需要定义状态来表示每个可能的路径，包括起点、终点、已经走过的路径和当前路径的权值。定义一个状态类来存储这些信息。

class State {
public:
int start;
int end;
vector<int> path;
int weight;
};

3. 定义优先队列

我们需要定义一个优先队列来存储状态，每次选择权值最小的状态进行扩展。可以使用STL中的优先队列来实现。

priority_queue<State, vector<State>, function<bool(State, State)>> pq([](State a, State b) { return a.weight > b.weight; });

4. 初始化状态

我们需要将起点加入优先队列中，然后开始循环。在循环的过程中，我们从优先队列中取出权值最小的状态进行扩展，直到找到终点或者队列为空。

State initial;
initial.start = start; // 起点
initial.end = end; // 终点
initial.path.push_back(start); // 已经走过的路径
initial.weight = 0; // 路径的权值
pq.push(initial);

5. 扩展状态

我们需要扩展每个状态，生成新的状态加入优先队列中。在扩展状态的过程中，需要判断当前路径是否已经超过当前最优解，如果是，则剪枝。

while (!pq.empty()) {
State curr = pq.top();
pq.pop();

// 判断是否到达终点
if (curr.end == end) {
// 更新最优解
bestPath = curr.path;
bestWeight = curr.weight;
break;
}

// 扩展状态
for (auto edge : graph.edges) {
if (edge.from == curr.end && find(curr.path.begin(), curr.path.end(), edge.to) == curr.path.end()) {
State next = curr;
next.end = edge.to;
next.path.push_back(edge.to);
next.weight += edge.weight;

// 剪枝
if (next.weight >= bestWeight) {
continue;
}

pq.push(next);
}
}
}

6. 输出结果

最后，我们可以输出最优路径以及路径的权值。

cout << "Best path: ";
for (auto v : bestPath) {
cout << v << " ";
}
cout << endl;

cout << "Best weight: " << bestWeight << endl;

完整代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Edge {
    int from;
    int to;
    int weight;
};

struct Graph {
    int V;
    int E;
    vector<Edge> edges;
};

class State {
public:
    int start;
    int end;
    vector<int> path;
    int weight;
};

int branchAndBound(Graph graph, int start, int end) {
    int bestWeight = INT_MAX;
    vector<int> bestPath;

    priority_queue<State, vector<State>, function<bool(State, State)>> pq([](State a, State b) { return a.weight > b.weight; });

    State initial;
    initial.start = start;
    initial.end = start;
    initial.path.push_back(start);
    initial.weight = 0;
    pq.push(initial);

    while (!pq.empty()) {
        State curr = pq.top();
        pq.pop();

        if (curr.end == end) {
            bestPath = curr.path;
            bestWeight = curr.weight;
            break;
        }

        for (auto edge : graph.edges) {
            if (edge.from == curr.end && find(curr.path.begin(), curr.path.end(), edge.to) == curr.path.end()) {
                State next = curr;
                next.end = edge.to;
                next.path.push_back(edge.to);
                next.weight += edge.weight;

                if (next.weight >= bestWeight) {
                    continue;
                }

                pq.push(next);
            }
        }
    }

    cout << "Best path: ";
    for (auto v : bestPath) {
        cout << v << " ";
    }
    cout << endl;

    cout << "Best weight: " << bestWeight << endl;

    return bestWeight;
}

int main() {
    Graph graph;
    graph.V = 5;
    graph.E = 7;
    graph.edges = {
        {0, 1, 2},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 4},
        {2, 3, 2},
        {2, 4, 5},
        {3, 4, 3}
    };

    int start = 0;
    int end = 4;

    int bestWeight = branchAndBound(graph, start, end);

    return 0;
}