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) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: где \: i \ in S \: and \: 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) $.

пример

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

Анализ

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

1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0

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 ccost (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, стоимость (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

$$ \ 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 $$

$$ \ 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] + Cost (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 $$

$$ \ 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

$$ \ 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).

Ценности