如何修改TSP求解代码使其返回最优旅行路线而非仅计算成本

修改思路 #

• 调整函数返回结构：将原函数仅返回int类型最小成本的逻辑，改为返回pair<int, vector<int>>类型，同时返回最小成本值和完整闭环旅行路线；也可选择新增vector<int>&类型的引用参数作为路线输出入口，以下示例采用返回pair的实现方式，兼容性更强。
• 补全路线组装逻辑：原有代码中存储的solution_path仅包含除起点外的途经节点，最终输出前需要在首尾补充起点，形成符合TSP要求的闭环路线。
• 编号适配：代码默认使用0开头的节点编号，若需要匹配题目中1开头的节点标识，输出时给每个节点编号加1即可。

修改后完整代码 #

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <utility> // 用于pair类型

using namespace std;

pair<int, vector<int>> travllingSalesmanProblem(vector<vector<int>> graph, int s, int n)
{
    vector<int> vertex;
    for (int i = 0; i < n; i++)
        if (i != s)
            vertex.push_back(i);
    int min_path = INT_MAX;
    vector<int> solution_path;

    do {
        int current_pathweight = 0;
        int k = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        current_pathweight += graph[k][s];

        if(current_pathweight < min_path) {
            min_path = current_pathweight;
            solution_path = vertex;
        }

    } while (next_permutation(vertex.begin(), vertex.end()));

    // 组装完整闭环路线
    vector<int> full_path;
    full_path.push_back(s);
    for (int node : solution_path) {
        full_path.push_back(node);
    }
    full_path.push_back(s);

    return {min_path, full_path};
}

int main()
{
    int n =4;
    vector<vector<int>> graph =  { { 0, 10, 15, 20 },
                       { 10, 0, 35, 25 },
                       { 15, 35, 0, 30 },
                       { 20, 25, 30, 0 } };
    int s = 0;
    pair<int, vector<int>> res = travllingSalesmanProblem(graph, s, n);
    cout << "最小成本：" << res.first << endl;
    cout << "最优路线（1开头编号）：";
    for (int i = 0; i < res.second.size(); i++) {
        if (i > 0) cout << "->";
        cout << res.second[i] + 1;
    }
    cout << endl;
    return 0;
}

运行输出示例 #

最小成本：80
最优路线（1开头编号）：1->2->4->3->1

内容的提问来源于stack exchange，提问作者AMM