允许重复访问与途经非目标城市的TSP变种高效求解咨询

你需要求解的是Steiner旅行商问题（Steiner TSP），和常规允许重复访问顶点的TSP相比，它额外支持访问非目标城市顶点来缩短总路径，完全匹配你的需求场景。

因为总顶点规模达到百万级，核心思路是先做问题降维，把原问题的复杂度从和总顶点数绑定，转为和目标城市数量绑定（通常目标城市数量远小于总顶点数），再做贪心求解：

步骤1：预计算目标城市两两最短路径 #

假设你需要覆盖的目标城市集合为S，大小为k：

• 仅针对S中的顶点做最短路径计算，对于稀疏图（百万级顶点的工业场景几乎都是稀疏图，边数和顶点数同阶），对每个S中的顶点跑一次优先队列优化的Dijkstra算法，不需要存储全图所有顶点的路径，只需要保存S中任意两点的最短路径长度，以及对应的路径节点序列即可。
• 可选优化：跑Dijkstra时，一旦已经找到所有其他S中顶点的最短路径，直接终止当前计算，不需要遍历完整个百万顶点图，能节省大量计算资源。

步骤2：构造降维完全图 #

把原来的百万顶点有向带权图，转换为仅包含k个顶点的完全带权图，每个顶点对应一个目标城市，两点之间的边权就是步骤1中预计算的最短路径长度。这一步直接把后续计算的复杂度和百万级总顶点解耦，计算压力大幅降低。

步骤3：对降维图执行贪心TSP求解 #

现在问题已经转化为常规TSP问题，推荐两种高效的贪心实现方案：

• 最近邻算法
  1. 随机选择一个目标城市作为起点
  2. 每次从未访问的目标城市中，选择离当前所在城市距离最近的作为下一个访问点
  3. 重复第二步直到所有目标城市都被访问，得到目标城市的访问顺序
     时间复杂度为O(k²)，实现最简单，适合k较小的场景
• 插入式贪心算法
  1. 先选两个距离最近的目标城市构造初始路径
  2. 每次从未访问的目标城市中选一个，找到将其插入到当前路径的最优位置（插入后总路径增量最小），完成插入
  3. 重复第二步直到所有目标城市都被插入，得到目标城市的访问顺序
     时间复杂度同样为O(k²)，路径质量比最近邻算法高10%~20%，是工业场景更常用的方案

步骤4：还原完整路径 #

把步骤3得到的目标城市访问顺序中，每两个相邻目标城市之间的最短路径序列拼接起来，就得到了符合要求的完整路径，自然包含允许访问的非目标城市顶点。

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