Cosmos 仓库旅行商问题（TSP）求解器实战：基于模拟退火的 C++ 实现与源码解析

• 教程
• 示例工程

导读

本文围绕 cosmos 仓库code/artificial_intelligence/src/tsp目录下的旅行商问题（Traveling Salesman Problem, TSP）求解器展开，深入讲解其基于**模拟退火（Simulated Annealing）**的混合求解策略：以高温随机游走开局、低温爬山收敛，配合 2-opt 式边交换、基于三角不等式的局部优化以及禁忌（tabu）tenure 回退机制。读完本文，你将掌握该求解器的完整构建与运行流程（make编译、标准输入喂入欧氏/非欧氏距离矩阵）、核心算法每一步的源码级原理，以及仓库内置的 6 组基准测试数据的使用方法，可直接复制命令复现求解结果。

目录

1. 构建与运行：从源码到可执行文件
2. 输入数据格式：坐标与距离矩阵
3. 算法总览：模拟退火驱动的五步混合框架
4. 第 1 步：从高温随机游走平滑过渡到低温爬山
5. 第 2 步：随机边交换产生候选解与概率接受准则
6. 第 3 步：基于三角不等式的长边消除优化
7. 第 4 步：禁忌 tenure 计数器与最优路径回退
8. 第 5 步：终止条件与全程收敛控制
9. 关键参数速查表
10. 运行结果解读：标准输出中的迭代信息
11. 仓库中的测试数据与扩展

一、构建与运行：从源码到可执行文件

原文档给出了两条最核心的操作命令，对应目录下的 makefile 与源码 salesman.cpp：

1. 执行make得到可执行文件tsp

   makefile 内容如下：

   target: salesman.cpp g++ -o tsp salesman.cpp clean: rm -rf *.o

   可见构建过程本质上是调用g++ -o tsp salesman.cpp一次性编译链接，未引入额外第三方依赖，C++标准库即可满足（源码使用了<climits>、<vector>、<iostream>、<algorithm>、<cmath>）。若需清理中间产物可执行make clean。

2. 运行./tsp < input > output获取结果

   求解器从标准输入（stdin）读取实例数据，将求解过程与最终路径写入标准输出（stdout）。因此仓库采用 shell 重定向的经典用法：

   ./tsp < euc_100 > output_euc_100.txt

   这样既可以把数据文件（如 euc_100）作为输入喂入程序，又能把运行日志与最终路径保存到输出文件中。

二、输入数据格式：坐标与距离矩阵

在动手运行前，必须理解输入文件的结构，它由三部分顺序组成（见 processing_data 的实现）：

1. 第一行：一个字符串euclidean或noneuclidean，标注距离矩阵类型（欧氏距离矩阵 / 非欧氏距离矩阵）。源码会将其读入string type，但当前版本中并未参与后续计算，更多是数据集的元信息。
2. 第二行：城市数量num_cities（一个整数）。
3. 接下来num_cities行：每行两个浮点数x y，表示每个城市的坐标。这些坐标同样被读入location向量，但在当前实现中不直接参与路径代价计算。
4. 最后num_cities * num_cities行（或一行内的连续数值）：完整的距离矩阵，adjacency_matrix[i][j]表示城市 i 到城市 j 的距离。源码逐行读取并填充二维矩阵：

for (long long i = 0; i < num_cities; i++) { vector<long double> temp; for (long long j = 0; j < num_cities; j++) { cin >> x; temp.push_back(x); } adjacency_matrix.push_back(temp); }

实际文件样例（节选自 euc_100）：

euclidean 100 43.2178903964 14.0347372113 30.7007433235 -60.6295828691 ... 0.0 75.7062722891 112.930565536 ... <- 距离矩阵（100x100）

矩阵第 i 行第 j 列即dist(city_i, city_j)；对角线元素为 0.0。路径代价采用闭合环路定义：从城市 0 出发依次经过全部城市后回到起点，代价为相邻城市距离之和（见下文evaluation）。

三、算法总览：模拟退火驱动的五步混合框架

原文档将整个求解过程概括为 5 个步骤，其对应的源码主线位于 simulated_annealing。整体思路可归纳为：

初始化解时，三个路径向量（best_path、current_path、suggested_path）先按顺序初始化为0,1,2,...,n-1，再对current_path执行random_shuffle（initialize_vectors），并以srand(time(NULL))播种随机数，保证每次运行得到不同搜索轨迹。

四、第 1 步：从高温随机游走平滑过渡到低温爬山

原文档第 1 点指出：温度高时算法行为接近随机游走，温度低时行为接近爬山（hill climbing）。这是模拟退火的核心思想，在源码中由两个常量体现：

// Initial Temperature long double temperature = 10000000000000; // 1e13 ... // Cooling Rate temperature *= 0.999;

• 初始温度高达1e13。在高温阶段，即使候选解比当前解差很多，其接受概率也趋近于 1（见下一节概率公式），因此搜索过程表现为大范围随机游走，能有效探索解空间、跳出局部最优。
• 冷却率0.999意味着每一轮迭代温度衰减约 0.1%。温度缓慢下降，使得算法在迭代后期几乎只接受更优解，退化为确定性爬山，保证收敛质量。

这种"先广后精"的调度与经典模拟退火的 Metropolis 接受准则完全一致，是整个求解器平衡**探索（exploration）与开发（exploitation）**的基石。

五、第 2 步：随机边交换产生候选解与概率接受准则

原文档第 2 点描述的是标准的2-opt 思想：随机挑选两条边并交换以得到建议路径；若建议路径代价更低则采纳，若更差则在高温时以一定概率接受。

5.1 随机选边

random_edge 随机生成两个下标，并保证start_ind <= end_ind：

long long start_ind = rand() % num_cities; long long end_ind = (rand() % num_cities) + 1; if (start_ind > end_ind) swap(start_ind, end_ind); return make_pair(start_ind, end_ind);

5.2 生成建议路径

选定两条边后，对区间[start, end)执行区间反转（等价于 2-opt 中的边交叉重连）：

pair<long long, long long> edges = random_edge(); long long start = edges.first, end = edges.second; reverse(suggested_path.begin() + start, suggested_path.begin() + end);

5.3 代价评估

evaluation 按闭合环计算总代价：

for (long long i = 0; i < num_cities - 1; i++) cost += adjacency_matrix[vec[i]][vec[i + 1]]; cost += adjacency_matrix[vec[vec.size() - 1]][vec[0]];

即sum(dist(vec[i], vec[i+1])) + dist(vec[last], vec[0])，最终要回到起点城市。

5.4 概率接受准则

long double net_gain = suggested_path_cost - current_path_cost; long double rand_num = (double)(rand() / (double)RAND_MAX); long double probability = 1 / (1 + std::pow(M_E, (net_gain / temperature))); if (probability > rand_num) current_path = suggested_path;

这里使用了sigmoid 形式的概率函数：

• 当net_gain < 0（建议路径更优）时，probability > 0.5，几乎必然接受；
• 当net_gain > 0（建议路径更差）且温度很高时，net_gain / temperature很小，probability接近 0.5~1，算法仍以较大概率接受——这正是高温阶段的"随机游走"；
• 随着温度降低，差的候选解接受概率迅速下降，最终只接受更优解，进入"爬山"模式。

此外，若建议路径优于当前已知最优，会同步更新best_path与全局答案answer，并打印当前最优路径（输出为城市编号 +1，闭环首尾相同）。

六、第 3 步：基于三角不等式的长边消除优化

原文档第 3 点提到的"优化函数"，即 Optimization。其原理基于三角不等式：对于路径中连续的四座城市 A-B-C-D，若交叉边组合AC + BD比原有两条边AB + CD更短，就交换中间两个城市（B 与 C），从而"拉直"长边、缩短局部路径：

long double AB = adjacency_matrix[auxiliary_best[i]][auxiliary_best[i + 1]]; long double CD = adjacency_matrix[auxiliary_best[i + 2]][auxiliary_best[i + 3]]; long double AC = adjacency_matrix[auxiliary_best[i]][auxiliary_best[i + 2]]; long double BD = adjacency_matrix[auxiliary_best[i + 1]][auxiliary_best[i + 3]]; if (AB + CD > AC + BD) { swap(auxiliary_best[i + 1], auxiliary_best[i + 2]); i += 3; // 交换后跳过被修改的区间 } else { i++; }

这个局部优化器被用在两个地方：

1. 每次生成suggested_path后立即调用Optimization(suggested_path)（simulated_annealing），让候选解在进入评估前先被"整形"；
2. 当 tabu tenure 触发回退时，对best_path本身再做一次Optimization(best_path)（见下一节），进一步压低最优路径代价。

七、第 4 步：禁忌 tenure 计数器与最优路径回退

原文档第 4 点描述的tabu tenure counter在源码中体现为整型变量tabu_tenure。其工作逻辑如下：

• 每当产生的新建议路径优于当前最优（suggested_path_cost < best_path_cost）时，更新best_path、answer，并将tabu_tenure重置为 0、break_counter清零；
• 否则tabu_tenure++；
• 当tabu_tenure >= 500时，说明连续多轮没有突破，触发回退机制：

if (tabu_tenure >= 500) { Optimization(best_path); // 对最优路径再做一次长边消除 if (best_path_cost > evaluation(best_path)) { best_path_cost = evaluation(best_path); answer = best_path_cost; current_path = best_path; // 当前路径回退到最优路径 break_counter = 0; } tabu_tenure = 0; }

这一机制相当于"禁忌搜索（Tabu Search）"中的惩罚与重置思想：当搜索长期停滞、无法找到更优解时，将当前搜索位置重置回已知最优，重新开始一轮扰动与优化，从而避免在局部区域空转。若优化后best_path确有改善，还会再次打印最优路径并重置break_counter。

八、第 5 步：终止条件与全程收敛控制

原文档第 5 点强调"重复以上过程直到 best_path 长时间保持不变"。源码通过双重条件控制循环结束（simulated_annealing）：

int limit = 10000000; // 最大迭代轮数上限 long long tabu_tenure = 0, break_counter = 0; while (limit-- && break_counter <= 200000) { ... temperature *= 0.999; break_counter++; }

• limit = 10,000,000：绝对迭代上限，防止无限循环；
• break_counter <= 200,000：若连续 20 万轮内没有产生更优路径（break_counter会在每次刷新最优时归零），则判定best_path已长期稳定，提前终止。

退出循环后，程序打印Final Path:及最终路径，并在main中输出Minimum Path found so far <answer>，即整个搜索过程中找到的最小闭环代价。

九、关键参数速查表

以下参数均可直接在上述源码路径中找到，便于复现与调参实验：

十、运行结果解读：标准输出中的迭代信息

运行程序后，标准输出中包含两类信息：

1. 实时最优路径：每当找到比当前最优更短的路径，就会输出一行1 5 3 2 ... 1（城市编号 +1，且首尾一致表示闭环），方便观察求解过程中路径的逐步改善。
2. 每轮最优代价：每次迭代输出一行Best_Path_till now <cost>，用于监控收敛曲线。
3. 最终结果：循环结束后打印Final Path:与最终路径，随后main输出：

Minimum Path found so far 1203.45...

若配合./tsp < euc_100 > output.txt重定向，上述全部日志都会写入output.txt，便于离线分析。

十一、仓库中的测试数据与扩展

11.1 内置基准数据集

目录下共提供 6 组输入文件，覆盖"欧氏/非欧氏 × 100/250/500 城市"三种规模：

例如，在 500 城市规模上运行：

make ./tsp < euc_500 > result_euc_500.txt

需要说明的是：距离矩阵是直接给出的（第一行euclidean/noneuclidean仅作类型标注），即使是非欧氏矩阵，本求解器也可直接运行，因为它只依赖adjacency_matrix做代价评估与边交换，不要求距离满足三角不等式。

11.2 仓库中的其他 TSP 实现

• src/tsp.c：一份基于最近邻贪心（nearest neighbour）与递归回溯的 C 语言实现，输入为 1~N 的邻接矩阵形式（固定最大 10 城市），适合作为对比"近似算法误差"的基线（文件头注释即要求实现最优方案并用近似算法评估误差）。
• 算法分类目录下另有 greedy_algorithms/src/tsp 未收录于本目录，但 graph_algorithms/src/travelling_salesman_mst 等目录提供了基于 MST 的 TSP 近似实现，可与模拟退火方案对照学习。

通过对比本求解器输出的Minimum Path found so far与贪心/精确解，即可直观量化模拟退火混合策略在大规模实例上的求解质量与误差，这正是该模块在仓库中的典型研究用途。

参考资料

• 核心算法说明：code/artificial_intelligence/src/tsp/algo.md
• 完整实现：salesman.cpp
• 构建脚本：makefile
• 输入数据：euc_100 等 6 个数据文件
• 对照实现：tsp.c

• 教程
• 示例工程