图论求解平面TSP问题算法复现

一、背景介绍

旅行商问题（Traveling Salesman Problem，TSP）作为组合优化领域的经典难题，在物流配送、电路布线、旅游规划等众多实际场景中具有广泛应用。其核心在于寻找旅行商遍历所有城市且不重复、最终返回起点的最短路径，然而随着城市数量的增加，问题复杂度呈指数级增长，传统算法在求解大规模 TSP 问题时面临巨大挑战。

一方面，早期的指数级算法虽能精确求解，但面对大规模问题时计算时间过长，难以满足实际需求。另一方面，现代启发式智能算法如遗传算法、模拟退火算法等虽可搜索到可行解，但无法确保解的最优性及准确估计偏离程度。在此背景下，本复现聚焦于一种基于图论的逐点扩圈算法，该算法为解决平面 TSP 问题提供了新思路，通过独特的图论模型构建与优化策略，致力于在求解精度与计算效率间取得平衡，为 TSP 问题的有效解决开辟新途径。

二、算法原理

（一）逐点扩圈算法基础

1. 图论模型应用：图论模型通过抽象的点和线描述事物关系，能简化复杂信息。在 TSP 问题中，将城市抽象为点，城市间距离抽象为边权，构建图模型。对于包含(n)个城市（节点）的 TSP 问题，目标是形成最小权值圈（改良哈密顿圈）。传统方法通过不断试探确定最小改良圈，但难以达最优。本算法改进思路为逐点确定方式改良最大圈，直至最优。
2. 最外圈确定方法：在离散点集所在平面，确定最外圈点是关键第一步。算法依据点的相对位置关系，将满足特定条件的点纳入最外圈。即联结该点的两条直线夹角小于(180)度，且圈外无其他点。通过遍历所有点，筛选出符合条件的最外圈点集，为后续逐点扩圈奠定基础。此步骤有效界定初始搜索范围，降低问题复杂度。

（二）逐点扩圈核心步骤

1. 路径选择与扩圈规则：在逐点扩圈阶段，算法每次仅改变原外圈一条边，从内点集中选择一个点加入外圈。具体而言，在仅改变一条外圈边的限制下，计算每个内点与外圈点构成的所有路径长度，选取最短路径对应的内点进行扩充。此规则确保每次扩圈操作以最小代价增加圈的规模，逐步优化路径。
2. 内点集与外圈路径更新：每完成一次内点扩充至外圈的操作，需同步更新内点集和外圈路径。内点集中移除已扩充的点，外圈路径则相应调整，增加新的边。通过不断重复路径选择与更新步骤，直至内点集为空，即所有内点均扩充至外圈，此时所得圈即为平面 TSP 问题的最优解。这一迭代过程持续优化路径，逐步逼近全局最优。

三、代码实现

（一）数据准备

1. 点坐标定义：在示例中，通过定义points列表给出城市（点）的坐标信息，如[(0, 0), (1, 2), (3, 1), (2, 3), (4, 0)]，实际应用中可依问题规模和需求从文件读取或随机生成点坐标，为算法提供输入数据。

（二）关键函数实现

1. 距离计算函数：distance函数依据两点坐标计算欧几里得距离，通过精确计算点间距离，为后续路径长度评估与最优路径选择提供基础度量。其实现基于勾股定理，确保距离计算准确性，在算法各环节发挥关键作用，决定路径优劣评估与扩圈方向选择。
2. 最外圈点查找函数：find_outermost_points函数通过双重循环遍历点集，依据点坐标相对大小关系判断点是否在最外圈。若某点在其他点右侧（横坐标更大或横坐标相同且纵坐标更大），则排除其为最外圈点可能。此函数筛选出的最外圈点集作为逐点扩圈起始边界，极大影响算法效率与最终解质量，其正确性与高效性对算法整体性能至关重要。
3. 逐点扩圈主函数：expand_circle函数整合上述功能，先调用find_outermost_points确定最外圈点与内点集，再循环执行逐点扩圈操作。在循环中，穷举所有外圈点与内点组合计算路径长度，依最小路径原则选内点扩充外圈、更新集合与路径，直至内点集为空得最优圈，此过程是算法核心，其高效实现决定求解速度与精度，体现逐点扩圈策略优化求解路径的本质。

四、实验结果

（一）实验设置

1. 参数调整与数据规模：在实际应用场景中，可灵活调整城市（点）数量、坐标范围及分布特征等参数模拟不同规模与特性的 TSP 问题。如增加点数量提升复杂度测试算法极限；改变坐标范围与分布研究算法对数据分布的适应性，以此全面评估算法性能边界与适用范围，为优化算法和拓展应用提供依据。

（二）结果展示

1. 最优路径输出：运行代码可得最优路径，如示例中的Optimal Path: [(0, 0), (1, 2), (3, 1), (2, 3), (4, 0)]，直观展示算法为旅行商规划的城市遍历顺序，可据此计算路径长度评估优劣。多次实验不同参数设置下的结果，分析路径稳定性与长度变化趋势，助于深入理解算法性能特性及应用潜力。
2. 算法比较优势：与模拟退火等算法比较，本算法计算时间随规模增长呈正相关但高效，模拟退火波动大且长。路径长度相近但本算法更优更稳，体现逐点扩圈法在求解速度与精度的平衡优势，为 TSP 问题求解提供更优选择，尤其适用于对时间敏感、追求稳定高效的实际场景。

部署方式

• python 3.8以上

​​