求助：TSP虚拟节点法适配最短哈密顿路径的精度问题

我正在开发一套配送系统的路径规划算法，采用图模型求解：将每个配送地址表示为节点，节点间的距离作为边的权重。目前尝试用Christofides算法适配旅行商问题（TSP），该算法基于最小生成树（Minimum Spanning Tree）和欧拉回路（Eulerian Cycle）实现，但精度无法满足需求——TSP求解的是最短哈密顿回路，而我需要的是最短哈密顿路径。

我尝试过引入权重为0的虚拟节点（dummy node）来转换问题，但这会导致近似算法丢失上下文，生成的路径和最优解差距极大。请问有没有同行遇到过类似问题，能提供解决方案？

路径示例 #

• 算法生成的4条路径：
• 最优路径：

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