分支限界法求图的最短回路c++实现

以下是使用分支限界法求解图的最短回路问题的C++实现示例：

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

using namespace std;

// 定义一个节点类，用于表示状态空间中的节点
class Node {
public:
    vector<int> path; // 当前路径
    int bound; // 当前路径的下界
    int length; // 当前路径已经走过的长度

    Node(vector<int> path, int bound, int length) {
        this->path = path;
        this->bound = bound;
        this->length = length;
    }
};

// 定义一个函数，用于计算两点之间的距离
double distance(int x1, int y1, int x2, int y2) {
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

// 定义一个函数，用于计算当前路径的下界
int lower_bound(vector<vector<double>>& graph, vector<int>& path) {
    int n = graph.size();
    vector<bool> visited(n, false);
    // 计算已经走过的长度
    int length = 0;
    for (int i = 0; i < path.size()-1; i++) {
        length += graph[path[i]][path[i+1]];
    }
    // 计算剩余路径的最小长度
    int bound = length;
    for (int i = 0; i < n; i++) {
        if (find(path.begin(), path.end(), i) == path.end()) {
            double min_dist = numeric_limits<double>::max();
            for (int j = 0; j < n; j++) {
                if (find(path.begin(), path.end(), j) != path.end()) {
                    double dist = graph[i][j];
                    if (dist < min_dist) {
                        min_dist = dist;
                    }
                }
            }
            bound += min_dist;
        }
    }
    return bound;
}

// 定义一个函数，用于求解图的最短回路问题
pair<vector<int>, int> tsp(vector<vector<double>>& graph) {
    int n = graph.size();
    // 初始化起始节点
    vector<int> start_path = {0};
    int start_bound = lower_bound(graph, start_path);
    Node start_node(start_path, start_bound, 0);
    // 初始化最优解
    vector<int> best_path;
    int best_length = numeric_limits<int>::max();
    // 定义一个优先队列，用于存放待扩展的节点
    priority_queue<Node, vector<Node>, function<bool(Node, Node)>> queue(
        [](Node a, Node b) { return a.bound > b.bound; }
    );
    queue.push(start_node);
    while (!queue.empty()) {
        // 从队列中取出一个节点
        Node curr_node = queue.top();
        queue.pop();
        // 如果当前节点的下界比当前最优解还要大，剪枝
        if (curr_node.bound >= best_length) {
            continue;
        }
        // 如果当前节点的路径已经包含了所有的节点，更新最优解
        if (curr_node.path.size() == n) {
            int curr_length = curr_node.length + graph[curr_node.path.back()][0];
            if (curr_length < best_length) {
                best_path = curr_node.path;
                best_length = curr_length;
            }
        }
        // 否则，扩展当前节点的子节点
        else {
            for (int i = 0; i < n; i++) {
                if (find(curr_node.path.begin(), curr_node.path.end(), i) == curr_node.path.end()) {
                    vector<int> new_path = curr_node.path;
                    new_path.push_back(i);
                    int new_bound = lower_bound(graph, new_path);
                    int new_length = curr_node.length + graph[curr_node.path.back()][i];
                    Node new_node(new_path, new_bound, new_length);
                    // 将子节点插入队列中，并按照下界从小到大的顺序排序
                    queue.push(new_node);
                }
            }
        }
    }
    best_path.push_back(0);
    return make_pair(best_path, best_length);
}

// 测试代码
int main() {
    vector<vector<double>> graph = {
        {0, 1, 2, 3},
        {1, 0, 4, 5},
        {2, 4, 0, 6},
        {3, 5, 6, 0}
    };
    auto res = tsp(graph);
    vector<int> best_path = res.first;
    int best_length = res.second;
    cout << "best path: ";
    for (int i : best_path) {
        cout << i << " ";
    }
    cout << endl;
    cout << "best length: " << best_length << endl;
    return 0;
}

在上述代码中，我们使用了STL中的`vector`、`queue`和`priority_queue`等容器，分别用于存放图的邻接矩阵、待扩展的节点和按照下界从小到大排序的节点。我们使用`numeric_limits`库来初始化最优解的长度和下界，这样可以保证它们的值为INT_MAX和DBL_MAX。在计算当前路径的下界时，我们使用了STL中的`find`函数来判断一个节点是否已经在当前路径中。在扩展节点时，我们使用了STL中的`find`函数来判断一个节点是否已经在当前路径中，以及使用了`make_pair`函数来构造返回值。