旅行售货员问题要求用分支限界法实现算法c++

旅行售货员问题是NP完全问题中的一个经典问题，其目的是在给定一组城市和它们之间的距离矩阵的情况下，求出一条经过每个城市恰好一次的最短路径。而分支限界法是一种搜索算法，它可以通过剪枝来减少搜索空间，从而提高搜索效率。下面是使用C++实现旅行售货员问题的分支限界算法的代码：

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

using namespace std;

// 旅行售货员问题结构体
struct TSP {
    vector<vector<int>> dist; // 城市之间的距离矩阵
    int n; // 城市数量
    int min_cost; // 最小花费
    vector<int> path; // 最小花费下的路径
};

// 结点结构体
struct Node {
    int level; // 结点所在层数（当前访问的城市编号）
    int cost; // 到达当前城市的花费
    vector<int> path; // 到达当前城市的路径
    bool visited[20]; // 标记已经访问过的城市
    double bound; // 当前结点的花费下界
    bool operator<(const Node& other) const { // 重载小于号，用于STL最小堆排序
        return bound < other.bound;
    }
};

// 计算结点的花费下界
double calc_bound(const TSP& tsp, Node& node) {
    double bound = node.cost;
    int level = node.level;
    // 计算已经访问过的城市到未访问过的城市的最小距离和
    for (int i = 0; i < tsp.n; i++) {
        if (!node.visited[i]) {
            int min_dist = numeric_limits<int>::max();
            for (int j = 0; j < tsp.n; j++) {
                if (i != j && node.visited[j]) {
                    min_dist = min(min_dist, tsp.dist[j][i]);
                }
            }
            bound += min_dist;
        }
    }
    return bound;
}

// 分支限界法求解旅行售货员问题
void tsp(TSP& tsp) {
    // 初始化根结点
    Node root = {0, 0, vector<int>(1, 0), {true}, 0};
    root.bound = calc_bound(tsp, root);

    // 初始化最小堆
    priority_queue<Node> Q;
    Q.push(root);

    // 开始搜索
    while (!Q.empty()) {
        Node cur = Q.top();
        Q.pop();
        if (cur.bound >= tsp.min_cost) { // 当前结点的花费下界大于等于已经找到的最小花费，剪枝
            continue;
        }
        if (cur.level == tsp.n - 1) { // 已经访问了所有城市
            cur.cost += tsp.dist[cur.path.back()][0];
            if (cur.cost < tsp.min_cost) { // 更新最小花费
                tsp.min_cost = cur.cost;
                tsp.path = cur.path;
            }
            continue;
        }
        // 分别考虑从当前城市出发访问所有未访问过的城市的情况
        for (int i = 1; i < tsp.n; i++) {
            if (!cur.visited[i]) {
                Node child = cur;
                child.level++;
                child.cost += tsp.dist[child.path.back()][i];
                child.path.push_back(i);
                child.visited[i] = true;
                child.bound = calc_bound(tsp, child);
                if (child.bound < tsp.min_cost) { // 只将花费下界小于最小花费的子结点加入最小堆中
                    Q.push(child);
                }
            }
        }
    }
}

int main() {
    TSP tsp = {{ {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0} }, 4, numeric_limits<int>::max(), {0}};
    tsp(tsp);
    cout << "Min Cost: " << tsp.min_cost << endl;
    cout << "Path: ";
    for (int i : tsp.path) {
        cout << i << "->";
    }
    cout << "0" << endl;
    return 0;
}

在这个代码中，我们定义了一个`TSP`结构体来存储旅行售货员问题的信息，包括城市之间的距离矩阵、城市数量、最小花费和最小花费下的路径。在`Node`结构体中，我们使用一个布尔数组来标记已经访问过的城市，还重载了小于号运算符，这是为了让我们可以使用STL的最小堆来维护搜索结点的优先级。

在`calc_bound`函数中，我们计算了当前结点的花费下界，这是通过贪心的思路来计算的。具体来说，我们首先计算已经访问过的城市到未访问过的城市的最小距离和，然后将当前花费加上这个最小距离和，从而得到当前结点的花费下界。

在`tsp`函数中，我们使用了一个最小堆来维护搜索结点的优先级。在每一次循环中，我们取出最小堆中的顶部结点，然后根据当前结点的状态进行分支限界搜索。具体来说，我们分别考虑从当前城市出发访问所有未访问过的城市的情况，然后计算子结点的花费下界，并将符合条件的子结点压入最小堆中。如果当前结点的花费下界大于等于已经找到的最小花费，则可以剪枝，继续搜索下一个结点。如果已经访问了所有城市，则更新最小花费和最小花费下的路径。

最后，在`main`函数中，我们定义了一个简单的旅行售货员问题实例，然后调用`tsp`函数求解，最终输出结果。

希望这个解答能够帮助到您！