旅行推销员变化算法

Question

我很难找到TSP问题的下一个变体的矛盾示例。

输入：G=（V，E） 无向完整图，其中包含三角形不等式、w：E->R+ 权重函数和源顶点 s。

输出：简单的汉密尔顿循环，以 s 开始和结束，具有最小权重。

算法：

1. S=Empty-Set   
2. B=Sort E by weights.   
3. Initialized array M of size |V|, 
   where each cell in the array holds a counter (Initialized to 0)
   and a list of pointers to all the edges of that vertex (In B).    
4. While |S|!=|V|-1  
    a. e(u,v)=removeHead(B).  
    b. If e does not close a cycle in S then     
          i.    s=s union {e}   
         ii.    Increase degree counter for u,v.  
        iii.    If M[u].deg=2 then remove all e' from B s.t e'=(u,x).   
         iv.    If M[v].deg=2 then remove all e' from B s.t e'=(v,x).
5. S=S union removeHead(B).

这将类似于 Kruskal 算法（使用 union-find DS）.
步骤 4.b.iii 和 4.b.iv 将使用指针列表完成。

我非常怀疑这个算法是否真实，所以我立即转向寻找它为什么是错误的。任何帮助将不胜感激。

Answer 1

假设我们有一个包含 4 个顶点(a, b, c, d)边权重的图形，如下所示：

w_ab = 5
w_bc = 6
w_bd = 7
w_ac = 8
w_da = 11
w_dc = 12
             7
       |--------------|
   5   |   6      12  |
a ---- b ---- c ----- d
|______________|      |
|      8              |
|_____________________|
      11

三角形

不等式适用于此图中的每个三角形。

当a-b-d-c-a更好的周期（成本 32）时，您的算法将选择周期a-b-c-d-a（成本 34）。

Answer 2

您的程序可能不会终止。 考虑一个包含节点 { 1， 2， 3， 4 } 和边 { （1,2）、（1,3）、（2,3）、（2,4）、（3,4） } 的图形。 此图中唯一的哈密顿循环是 { （1,2）， （1,3）， （2,4）， （3,4） }。 假设最低权重边是 （2,3）。 然后你的过程将选择 （2,3），选择 { （1,2）， （1,3） } 中的一个并消除另一个，选择 { （2,4）， （3,4） } 中的一个并消除另一个，然后永远循环。

像这样的细微差别使旅行推销员问题如此困难。

Answer 3

考虑 4 个顶点上的完整图形，其中 {a,b,c,d} 个是节点，想象为正方形顺时针排列的角。让边缘权重如下所示。

w({a,b}) := 2, // "edges"
w({b,c}) := 2,
w({c,d}) := 2,
w({d,a}) := 2,
w({a,c}) := 1, // "diagnoals"
w({b,d}) := M

其中M是大于 2 的整数。一方面，由"边"组成的哈密顿循环的权重为 8。另一方面，包含{a,c}的哈密顿循环是最轻的边，必须包含{b,d}并且具有总重量

1 + M + 2 + 2 = 5 + M > 8

大于最小可能重量。总的来说，这意味着一般来说，最小权重的哈米顿循环不一定包含由原始问题中的算法选择的 lightest 边缘。此外，由于M趋于无穷大，该算法在近似比方面表现得很差，因为

(5 + M) / 8

任意变大。