algorithm - 多次访问的 TSP

Question

您能否为以下问题提出可能的方法：找到一条通过图顶点的路径，以便两个顶点 i 出现之间的距离（边权重之和）不超过 Di。它显然是无限的，所以我想为这条路径有一个生成器。

Answer 1

当您的图表满足三角不等式时，christofides 算法保证您在最佳值的 2/3 以内。