Алгоритм вариации коммивояжера

Мне сложно найти противоречащий пример следующей вариации задачи 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).

Это будет сделано аналогично алгоритму Крускала (с использованием DS union-find).
Шаги 4.b.iii и 4.b.iv будут выполняться с использованием списка указателей.

Я очень сомневаюсь, что этот алгоритм верен, поэтому я сразу же понял, почему он неправильный. Любая помощь будет оценена.


algorithm traveling-salesman kruskals-algorithm
person Zionsof    schedule 13.07.2016    source источник
comment
Если я понимаю алгоритм, из-за условия If e does not close a cycle in S невозможно окончательно выбрать край, который закрывает желаемый цикл. Это правильно?   -  person Codor    schedule 13.07.2016
comment
Достаточно легко найти пример, в котором кромка с минимальным весом не является частью кратчайшего цикла.   -  person Henrik    schedule 13.07.2016

Ответы (3)


arrow_upward
0
arrow_downward

Допустим, у нас есть граф с 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-c-d-a (стоимость 34), когда лучший цикл будет a-b-d-c-a (стоимость 32).

person Abhishek Bansal    schedule 13.07.2016
comment
Ага. Большое спасибо! - person Zionsof; 13.07.2016

arrow_upward
0
arrow_downward

Ваша процедура не может быть прекращена. Рассмотрим граф с узлами {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)} и исключит другой, затем зацикливание навсегда.

Подобные нюансы - вот что делает задачу коммивояжера такой сложной.

person PMar    schedule 13.07.2016

arrow_upward
0
arrow_downward

Рассмотрим полный граф с 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

что больше минимально возможного веса. В целом это означает, что в целом хамитоновский цикл минимального веса не обязательно содержит самый светлый край, который выбирается алгоритмом в исходном вопросе. Кроме того, поскольку M стремится к бесконечности, алгоритм работает произвольно плохо с точки зрения отношения аппроксимации, поскольку

(5 + M) / 8

вырастает сколь угодно большим.

person Codor    schedule 13.07.2016
comment
Не думал об этом так. Спасибо - person Zionsof; 13.07.2016