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 \: и \: 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 = 15cost (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 = 18cost (2, \ lbrace4 \ rbrace, 1) = d [2,4] + стоимость (4, \ Phi, 1) = 10 + 8 = 18 $$

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

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

$$ \ small Cost (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + Cost (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = d [4,3] + стоимость (3, \ Phi, 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) = d [4,2] + стоимость (2, \ Phi, 1) = 8 + 5 = 13 $$

S = 2

$$ \ small Cost (2, \ lbrace 3, 4 \ rbrace, 1) = \ begin {cases} d [2, 3] + Cost (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 {cases} 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 $$

$$ \ small Cost (4, \ lbrace 2, 3 \ rbrace, 1) = \ begin {cases} d [4, 2] + Cost (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ \ d [4, 3] + Стоимость (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 {cases} d [1, 2] + Cost (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 \ rbrace, 1) = 20 + 23 = 43 = 35 cost (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + cost (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 \ 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).