前言

作为大二刚接触算法的学生，旅行商问题（TSP）是入门贪心算法的经典案例。它核心是解决“从一个城市出发，遍历所有城市且仅一次，最后回到起点，求最短路径”的问题。

一、旅行商问题（TSP）核心理解

举个生活化例子：假设我要去3个陌生城市旅游，从家（城市A）出发，要去城市B、C、D，每个城市只去一次，最后回家，怎么规划路线能让总路程最短？这就是TSP的核心需求，而贪心算法的思路很直接——每次都选当前最优的下一步，一步步凑出最终路线。

二、贪心算法解决TSP的思路

1. 确定起点：任选一个城市作为出发起点（这里默认选第0个城市）。

2. 选择下一站：从当前所在城市出发，在还没去过的城市里，选距离最近的那个作为下一站。

3. 重复步骤2：直到所有城市都遍历完毕。

4. 返回起点：最后从最后一个遍历的城市，回到最初的起点，计算总路程。

注意：贪心算法是“局部最优凑全局最优”，不一定能得到TSP的绝对最优解，但胜在思路简单、计算快。

三、C++代码实现

1. 代码整体结构

 用二维数组存储城市间的距离（邻接矩阵）。

用布尔数组标记城市是否已访问。

按贪心思路遍历城市，记录路径和总路程。

 

2. 完整代码

#include <iostream>

#include <vector>

#include <climits> // 用于INT_MAX（表示无穷大）

using namespace std;

 

// 计算TSP贪心路径和总路程

void tspGreedy(const vector<vector<int>>& dist, int n) {

    vector<bool> visited(n, false); // 标记城市是否已访问，初始都未访问

    vector<int> path; // 存储最终的旅行路径

    int totalDist = 0; // 存储总路程

 

    // 1. 第一步：从第0个城市出发，标记为已访问，加入路径

    int currentCity = 0;

    visited[currentCity] = true;

    path.push_back(currentCity);

 

    // 2. 遍历剩余n-1个城市（因为起点已确定）

    for (int i = 1; i < n; i++) {

        int nextCity = -1; // 记录下一个要去的城市

        int minDist = INT_MAX; // 记录当前城市到未访问城市的最小距离

 

        // 3. 找当前城市到未访问城市的最短距离

        for (int j = 0; j < n; j++) {

            // 条件：j城市未访问，且当前城市到j的距离不是0（不是自己），且距离更小

            if (!visited[j] && dist[currentCity][j] != 0 && dist[currentCity][j] < minDist) {

                minDist = dist[currentCity][j];

                nextCity = j;

            }

        }

 

        // 4. 更新路径、总路程，标记下一个城市为已访问，切换当前城市

        path.push_back(nextCity);

        totalDist += minDist;

        visited[nextCity] = true;

        currentCity = nextCity;

    }

 

    // 5. 最后从最后一个城市回到起点，补充总路程

    totalDist += dist[currentCity][0];

    path.push_back(0); // 路径末尾加入起点，形成闭环

 

    // 6. 输出结果

    cout << "旅行商贪心算法路径：";

    for (int city : path) {

        cout << city << " -> ";

    }

    cout << "\b\b " << endl; // 去掉最后一个"->"

    cout << "总路程：" << totalDist << endl;

}

 

int main() {

    // 示例：4个城市（编号0-3），dist[i][j]表示城市i到城市j的距离

    int n = 4;

    vector<vector<int>> dist = {

        {0, 10, 15, 20}, // 城市0到其他城市的距离

        {10, 0, 35, 25}, // 城市1到其他城市的距离

        {15, 35, 0, 30}, // 城市2到其他城市的距离

        {20, 25, 30, 0} // 城市3到其他城市的距离

    };

 

    cout << "4个城市的距离矩阵：" << endl;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cout << dist[i][j] << "\t";

        }

        cout << endl;

    }

 

    // 调用贪心算法求解

    tspGreedy(dist, n);

 

    return 0;

}

3. 代码关键部分解释

距离矩阵dist： dist[i][j] 表示城市i到城市j的距离，自己到自己的距离为0，矩阵是对称的（实际场景中距离双向相等）。

 visited数组： visited[j] = true 表示城市j已去过，避免重复访问。

-找下一站逻辑：通过循环遍历所有未访问城市，筛选出距离当前城市最近的那个，这就是贪心的核心“局部最优”。

-闭环处理：遍历完所有城市后，必须回到起点，所以要补充最后一段路程。

四、运行结果

4个城市的距离矩阵：

0 10 15 20

10 0 35 25

15 35 0 30

20 25 30 0

旅行商贪心算法路径：0 -> 1 -> 3 -> 2 -> 0  

总路程：90

结果解读：路径是0→1→3→2→0，总路程10（0→1）+25（1→3）+30（3→2）+15（2→0）=90，符合贪心算法的局部最优选择逻辑。

五、注意事项

1. 代码中 INT_MAX 需要包含 <climits> 头文件，代表“无穷大”，用于初始化最小距离。

2. 城市编号从0开始，新手可以根据需求修改为从1开始（只需调整路径输出逻辑）。

3. 距离矩阵可以根据实际城市数量修改，比如改成5个、6个城市，代码逻辑完全通用。

4. 贪心算法的局限性：如果城市距离分布特殊，可能得不到最短路径，比如把示例中城市1到3的距离改成40，路径会变成0→1→2→3→0，总路程会变化，但仍是当前贪心思路下的最优解。