TSP问题

问题描述

旅行商问题（Travelling Saleman Problem，TSP），也称为货郎担问题，是一个看似简单，但时间复杂度落在指数时间范围内的难题之一。经典的TSP问题可描述为：一个旅行商在n个城市之间推销商品，从某一个城市A出发，经过其它n-1个城市且仅经过一次，最终回到出发地城市A。现要求给出这样一条路径，且这条路径最短。
算法设计：最小哈密尔顿环
数据输入：第1行输入地点数n，第2行输入地点之间的连线数e，在依次输入两个地点u和v之间的距离w，格式：地点u 地点v 距离w。
数据输出：第一行最短路径，第二行最短路径长度。

数据结构

集合，优先权队列，归约矩阵

算法

LC分支限界法

代码

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

using namespace std;
const int N = 20, INF = 0x3f3f3f3f;
int path[N],cnt;
set<int> visited;   // 标记数组
int n, m;

class node {
public:
    int a[N][N];
    int r;  // 归约矩阵的约数
    int u;  // 当前节点的序号
    node() {
        // 无参构造函数
    }
    node(int array[N][N], int u) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = array[i][j];
        this->u = u;
    }
    node(const node& x) {
        r = x.r;
        u = x.u;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = x.a[i][j];
    }
    node operator=(const node& t){
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = t.a[i][j];
        this->u = t.u;
        this->r = t.r;
        return *this;
    }
    void reduce() {
        this->r = 0;    // 矩阵归约，并计算约数的值
        for (int i = 0; i < n; i++) {
            int res = INF;
            for (int j = 0; j < n; j++) {
                res = min(res, a[i][j]);
            }
            if (res > INF / 2) continue;
            this->r += res;
            for (int j = 0; j < n; j++) {
                if (a[i][j] != INF) a[i][j] -= res;
            }
        }
        for (int i = 0; i < n; i++) {
            int res = INF;
            for (int j = 0; j < n; j++) {
                res = min(res, a[j][i]);
            }
            if (res > INF / 2) continue;
            this->r += res;
            for (int j = 0; j < n; j++) {
                if (a[j][i] != INF) a[j][i] -= res;
            }
        }
    }
};
class PLL {
public:
    int first;
    node second;
    PLL(int first, node second) :first(first), second(second){
        // 普通构造函数
    }
    PLL(const PLL& x) {
        this->first = x.first;
        this->second = x.second;
    }
    PLL operator=(const PLL& t) {
        this->first = t.first;
        this->second = t.second;
        return *this;
    }
};
bool cmp(PLL& a, PLL& b) {
    return a.first > b.first;
}
priority_queue<PLL, vector<PLL>, decltype(&cmp)> q(cmp);    // 定义一个小根堆

void bfs() {
    while (!q.empty()) {
        auto t = q.top();
        q.pop();    
        int plcost = t.first;
        node pnode(t.second);
        int current = pnode.u;
        path[cnt++] = current;
        if (cnt == n) {
            cout << plcost << endl;
            for (int i = 0; i < n ; i++)
                cout << path[i] << " -> ";
            cout << path[0] << endl;
            return; // 找到答案节点，直接返回
        }
        // 节点出队后进行标记
        visited.insert(current);
        int tarray[N][N];   // 定义一个临时数组
        for (int i = 0; i < n; i++) {
            if (!visited.count(i) ) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++)
                        tarray[j][k] = pnode.a[j][k];
                }
                for (int j = 0; j < n; j++)
                    tarray[current][j] = tarray[j][i] = INF;
                tarray[i][0] = INF; // 重置规约矩阵
                node sn(tarray, i);
                sn.reduce();
                int clcost = plcost + pnode.a[current][i] + sn.r;
                PLL spll(clcost, sn);
                q.push(spll);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    node start;
    start.u = 0;    // 存储当前节点的序号
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            start.a[i][j] = INF;    // 初始化矩阵
    }
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        // 针对无向图的TSP问题
        start.a[u][v] = start.a[v][u] = w;
    }
    start.reduce();
    //cout << start.r << endl;
    PLL startpll(start.r, start);
    q.push(startpll);   // 初始化优先权队列
    bfs();
    return 0;
}

运行样例

4 6
0 1 15
0 2 30
0 3 5
1 2 6
1 3 12
2 3 3

无向图节点编号从0开始

输出