DAA — проблема коммивояжера

Путешественник должен посетить все города из списка, где известны расстояния между всеми городами, и каждый город должен быть посещен только один раз. По какому кратчайшему маршруту он посещает каждый город ровно один раз и возвращается в исходный город?

Решение

Проблема коммивояжера — самая известная вычислительная проблема. Мы можем использовать метод грубой силы, чтобы оценить каждый возможный тур и выбрать лучший. Для n числа вершин в графе существует ( n — 1)! количество возможностей.

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

Рассмотрим граф G = (V, E) , где V — множество городов, а E — множество взвешенных ребер. Ребро e (u, v) обозначает, что вершины u и v связаны. Расстояние между вершиной u и v равно d (u, v) , что должно быть неотрицательным.

Предположим, мы начали с города 1 и, посетив некоторые города, теперь мы находимся в городе j . Следовательно, это частичный тур. Нам, безусловно, нужно знать j , так как это определит, какие города удобнее всего посетить в следующем. Нам также нужно знать все города, которые мы посетили, чтобы не повторять ни один из них. Следовательно, это соответствующая подзадача.

Для подмножества городов S Є {1, 2, 3, …, n}, которое включает 1 , и j Є S , пусть C (S, j) будет длина кратчайшего пути, посещающего каждый узел в S ровно один раз начиная с 1 и заканчивая j .

Когда | S | > 1, мы определяем C (S, 1) = ∝, поскольку путь не может начинаться и заканчиваться на 1 .

Теперь, давайте выразим C (S, j) в терминах меньших подзадач. Нам нужно начинать с 1 и заканчивать на j . Мы должны выбрать следующий город таким образом, чтобы

C(S,j)=minC(S− lbracej rbrace,i)+d(i,j)гдеi inSиi neqjc(S,j)=minC(s− lbracej rbrace,i)+d(i,j)гдеi inSиi neqj $$C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: где \: i \ in S \: и \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: где \: i \ in S \: и \: i \ neq j$$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i) 

Анализ

Существует не более $2 ^ nn$ подзадач, каждая из которых требует линейного времени для решения. Следовательно, общее время работы составляет $O (2 ^ nn ^ 2)$.

пример

В следующем примере мы проиллюстрируем шаги для решения проблемы коммивояжера.

Из приведенного выше графика подготовлена ​​следующая таблица.

S = Φ

$$\ small Cost (2, \ Phi, 1) = d (2,1) = 5 \ small Cost (2, \ Phi, 1) = d (2,1) = 5$$

$$\ small Cost (3, \ Phi, 1) = d (3,1) = 6 \ small Cost (3, \ Phi, 1) = d (3,1) = 6$$

$$\ small Cost (4, \ Phi, 1) = d (4,1) = 8 \ small Cost (4, \ Phi, 1) = d (4,1) = 8$$

S = 1

$$\ small Cost (i, s) = min \ lbrace Cost (j, s - (j)) + d [i, j] \ rbrace \ small Cost (i, s) = min \ lbrace Cost (j, s ) - (j)) + d [i, j] \ rbrace$$

$$\ small Cost (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15 стоимости (2, \ lbrace3 \ rbrace, 1) = d [2,3] + стоимость (3, \ Phi, 1) = 9 + 6 = 15$$

$$\ small Cost (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + Cost (4, \ Phi, 1) = 10 + 8 = 18 cost (2, \ lbrace4 \ rbrace, 1) = д [2,4] + стоимость (4, \ Фи, 1) = 10 + 8 = 18$$

$$\ small Cost (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + Cost (2, \ Phi, 1) = 13 + 5 = 18 ccost (3, \ lbrace2 \ rbrace, 1) = d [3,2] + стоимость (2, \ Фи, 1) = 13 + 5 = 18$$

$$\ small Cost (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + Cost (4, \ Phi, 1) = 12 + 8 = 20 стоимости (3, \ lbrace4 \ rbrace, 1) = д [3,4] + стоимость (4, \ Фи, 1) = 12 + 8 = 20$$

$$\ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15 стоимости (4, \ lbrace3 \ rbrace, 1) = д [4,3] + стоимость (3, \ Фи, 1) = 9 + 6 = 15$$

$$\ small Cost (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + Cost (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = д [4,2] + стоимость (2, \ Фи, 1) = 8 + 5 = 13$$

S = 2

 smallCost(2, lbrace3,4 rbrace,1)= begincased[2,3]+Стоимость(3, lbrace4 rbrace,1)=9+20=29  d[2,4]+Стоимость(4, lbrace3 rbrace,1)=10+15=25=25 smallСтоимость(2, lbrace3,4 rbrace,1) lbraced[2,3]+ smallcost(3, lbrace4 rbrace,1)=9+20=29d[2,4]+ smallCost(4, lbrace3 rbrace,1)=10+15=25 endcase=25 $$\ small Cost (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {case} d [2, 3] + Стоимость (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 = 29 \ \ d [2, 4] + Стоимость (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ small Стоимость (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ small cost (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ small Cost (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 \ end {case} = 25$$

 smallCost(3, lbrace2,4 rbrace,1)= begincased[3,2]+Cost(2, lbrace4 rbrace,1)=13+18=31  d[3,4]+Стоимость(4, lbrace2 rbrace,1)=12+13=25=25 smallСтоимость(3, lbrace2,4 rbrace,1) lbraced[3,2]+ smallcost(2, lbrace4 rbrace,1)=13+18=31d[3,4]+ smallCost(4, lbrace2 rbrace,1)=12+13=25 endcase=25 $$\ small Cost (3, \ lbrace 2, 4 \ rbrace, 1) = \ begin {case} d [3, 2] + Cost (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ \ d [3, 4] + Стоимость (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ small Стоимость (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ small cost (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ small Cost (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 \ end {case} = 25$$

 smallCost(4, lbrace2,3 rbrace,1)= begincased[4,2]+Cost(2, lbrace3 rbrace,1)=8+15=23  d[4,3]+Cost(3, lbrace2 rbrace,1)=9+18=27=23 smallСтоимость(4, lbrace2,3 rbrace,1) lbraced[4,2]+ smallcost(2, lbrace3 rbrace,1)=8+15=23d[4,3]+ smallCost(3, lbrace2 rbrace,1)=9+18=27 endcase=23 $$\ small Cost (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {case} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Cost (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ small Стоимость (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ small cost (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ small Cost (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 \ end {case} = 23$$

S = 3

 smallCost(1, lbrace2,3,4 rbrace,1)= begincased[1,2]+Стоимость(2, lbrace3,4 rbrace,1)=10+25=35 d[1,3]+Стоимость(3, lbrace2,4 rbrace,1)=15+25=40d[1,4]+Стоимость(4, lbrace2,31)=20+23=43=35затрат(1,2,3,4,4),1) 1,2[+]стоимости(23,4,4),1)=10+25=35 d[1,3]+стоимость(3,2,4фунта,1)=15+25=40 1,4[+]+стоимость(4, lbrace2,3 rbrace,1)=20+23=43=35 endcase $$\ small Cost (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ begin {case} d [1, 2] + Стоимость (2, \ lbrace 3, 4 \ rbrace, 1) = 10 + 25 = 35 \ d [1, 3] + Стоимость (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + Стоимость (4, \ lbrace 2, 3 1) = 20 + 23 = 43 = 35 затрат (1, 2,3,4,4), 1) \ 1,2 [+] стоимости (2 3,4,4) , 1) = 10 + 25 = 35 \ d [1,3] + стоимость (3, 2,4 фунта, 1) = 15 + 25 = 40 \ 1,4 [+] + стоимость (4 , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ end {case}$$

Минимальная стоимость пути составляет 35.

Начнем со стоимости {1, {2, 3, 4}, 1} , получим минимальное значение для d [1, 2] . Когда s = 3 , выберите путь от 1 до 2 (стоимость 10), затем вернитесь назад. Когда s = 2 , мы получаем минимальное значение для d [4, 2] . Выберите путь от 2 до 4 (стоимость 10), затем идите назад.

Когда s = 1 , мы получаем минимальное значение для d [4, 3] . Выбрав путь от 4 до 3 (стоимость 9), мы перейдем к шагу s = Φ . Получаем минимальное значение для d [3, 1] (стоимость 6).