寻求含双向平行边的有向图TSP变体算法（节点至少访问一次）

你描述的问题属于允许重复访问节点的有向旅行商问题变种，这类问题存在成熟的解决思路与算法，核心是通过转化为标准有向TSP问题来处理，具体步骤如下：

核心思路：转化为标准有向TSP #

由于要求每个节点至少被访问一次，我们可以先预计算节点间的最短路径，将原图转化为完全有向图，再求解标准有向TSP（每个节点恰好访问一次）——这个标准TSP的解对应原图中覆盖所有节点至少一次的最小成本路径。

步骤1：计算所有节点对的最短路径 #

针对原图中的每个节点对(u, v)，计算从u到v的最小成本路径（允许经过其他节点），记为d(u, v)：

• 若边权非负，可对每个节点单独运行Dijkstra算法，处理平行边时，只需在松弛操作中考虑所有从当前节点出发的边（包括平行边）。
• 若存在负权边（无负环），则使用Floyd-Warshall算法，在更新路径时同步考虑平行边的最小权值。

步骤2：构造完全有向图 #

基于第一步得到的最短路径矩阵，构造一个完全有向图G'：

• 节点集合与原图完全一致。
• 对于任意两个节点u和v，添加一条边(u, v)，其权值为d(u, v)。

步骤3：求解标准有向TSP #

在构造好的G'上求解标准有向TSP问题，得到的回路（或路径）对应原图的最优解：

• 精确算法（小规模节点）：使用动态规划，状态定义为dp[mask][u]，其中mask是二进制位表示的已访问节点集合，u是当前停留的节点，状态转移为dp[mask | (1<<v)][v] = min(dp[mask | (1<<v)][v], dp[mask][u] + d(u, v))。时间复杂度为O(n²2ⁿ)，适合节点数n≤20的场景。
• 启发式算法（大规模节点）：若节点数较多（n>30），可采用遗传算法、模拟退火、蚁群算法或改进的Lin-Kernighan算法，这类算法能在合理时间内给出近似最优解。

额外注意事项 #

• 如果问题允许路径不回到起点，只需在标准TSP的解中去掉最后返回起点的边即可。
• 平行边的处理关键在于计算最短路径时，要将所有同方向的平行边权值纳入考虑，确保取到最小的直接边权或间接路径权。

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