1

我有一个带有无向加权边的完整图，需要通过图节点的子集找到最低成本循环。与Traveling Salesman不同，任何节点都可以被访问不止一次，而不是所有节点都需要访问，我的意思是路径应该具有最小的遍历边权重之和。

例如，这是一个邻接矩阵形式的图：

  a b c d
a 0 3 4 5
b 3 0 2 4
c 4 2 0 1
d 5 4 1 0

其中每条边的权重用于每个元素。开始和结束于a并包括的周期[b,d]看起来像

[a,b,d,a] -> 3+4+5 = 12
[a,b,d,b,a] -> 3+4+4+3 = 14
[a,b,c,d,c,a] -> 3+2+1+1+4 = 11

是否有一个最佳算法，或者一个非常好的启发式算法？

4

1 回答 1

3

循环开始和结束于a并包括[b,d]简单地意味着循环必须访问节点a，b，d。[a,b,d,a] = [b,d,a,b]（循环正确）。您的问题称为 k-TSP。见这里。但这很难实现，可能不是您想要的。

所以我只会给你一个更简单的方法。首先构造仅通过这些节点的最短循环。然后用两个节点之间的最小路径替换每条边。我认为这是合理的，我忽略了最优性。以下是步骤：

  • V=nodes E=edges 和 M=must-visit 节点。
  • C通过在 M 上运行TSP （不使用其他节点）创建循环，添加额外的边来制作循环。
  • 现在使用所有节点 V。对于uv中的每条边，C请执行以下操作：
  • 查找和使用Dijsktra 算法w之间的最短路径（图中应该没有负循环）。uv
  • 替换uv为w。
于 2013-03-02T12:42:38.797 回答