非对称图中无需返回起点的旅行商问题（TSP）的名称及解决方法

标准名称 #

该场景下的问题标准名称是开放路径非对称旅行商问题（Open-route Asymmetric Traveling Salesman Problem），也可简称为开放路径ATSP。传统的非对称旅行商问题（ATSP）默认要求返回起点，而此版本仅需恰好访问所有节点一次、总距离最小，无需回到出发地，同时满足图的非对称性（A→B与B→A的距离/成本不同）。

解决方法 #

由于ATSP属于NP-hard问题，不存在多项式时间的精确解法，但针对不同规模的问题，有对应的有效处理方式：

• 小规模问题（节点数≤50）：可使用精确解法获得最优解
  • 分支定界法：通过剪枝减少搜索空间，逐步缩小最优解的范围；
  • 状态压缩动态规划：定义状态dp[mask][u]表示访问过mask标记的节点且当前位于节点u的最小成本，最终取所有dp[全节点mask][u]的最小值，时间复杂度为O(n²2ⁿ)。
• 大规模问题：依赖启发式或近似算法获取近似最优解
  • 贪心算法：从起点出发，每次选择当前节点到未访问节点中成本最低的路径，逐步构建完整路径；
  • 局部搜索算法：如2-opt、3-opt，通过交换路径中的边来迭代优化现有路径，降低总距离；
  • 元启发式算法：遗传算法、模拟退火、蚁群算法等，通过模拟自然过程在解空间中高效搜索较优解。
• 转化为闭合路径ATSP：引入一个虚拟节点，设置该节点与所有其他节点的双向成本为0，将开放路径问题转化为传统的闭合路径ATSP求解，最终路径去掉虚拟节点即可得到原问题的解。

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