Задача коммивояжёра

Задача коммивояжёра (в англоязычной литературе называемая Traveling Salesman Problem, сокращённо TSP) заключается в следующем:

Заданы n городов $v_1,v_2,\ldots,v_n$ и попарные расстояния $d_{ij} \equiv d(v_i,v_j)$ между ними, являющиеся положительными целыми числами.

Чему равна наименьшая возможная длина кольцевого маршрута, проходящего по одному разу через все города? Иными словами, требуется найти минимально возможное значение суммы $\sum_{i=1}^{n-1} d_{\pi(i),\pi(i+1)} +d_{\pi(n),\pi(1)}$, где минимум берется по всем перестановкам $\pi(1),\ldots,\pi(n)$ чисел 1,…,n.

Приведенный ниже пример переборного алгоритма и его выполнения, демонстрирует его неэффективность, и невозможность нахождения точного решения для данных реальных объёмов:

<code-python>

1. Находит и возвращает гамильтонов цикл минимального веса
2. в графе G. Использует перебор по всем вершинам кроме первой.

def tsp_permutations(G):

   min_path_length=1e300   # устанавливаем минимальную длину в бесконечность
   min_path=[]
   start_node=G.nodes()[0] # Фиксируем начальный узел (сокращаем перебор).
   for path in xpermutations(G.nodes()[1:]): # перебор всех узлов кроме первого.
       path.insert(0,start_node)    # добавляем в начало пути стартовый узел
       path_length=0                # обнуляем длину текущего пути  
       path_is_ok=1                 # Сначала считаем, что путь проходим
       for i in range(0,len(path)):
           v1=path[i]   #выбираем ребро (v1,v2), для текущей вершины
           if i<len(path)-1:      
               v2=path[i+1]
           else:
               v2=path[0]           # Если нода-последняя, то замыкаем путь. 

           if G.has_edge(v1,v2):
               path_length=path_length+G.get_edge(v1,v2)        
           else:  
               path_is_ok=0  # нет ребра (v1,v2) - путь непроходим.
               break 
       if (path_is_ok):
               print path, path_length
               if min_path_length>path_length:
                   min_path_length=path_length        
                   min_path=path        
   print "Optimal path:",min_path, min_path_length
   return min_path	

</code-python>

['NY', 'Moscow', 'Minsk', 'Berlin', 'Kiev'] 205
['NY', 'Moscow', 'Minsk', 'Kiev', 'Berlin'] 170
['NY', 'Moscow', 'Berlin', 'Minsk', 'Kiev'] 225
['NY', 'Moscow', 'Kiev', 'Minsk', 'Berlin'] 155
['NY', 'Berlin', 'Moscow', 'Minsk', 'Kiev'] 210
['NY', 'Berlin', 'Minsk', 'Moscow', 'Kiev'] 175
['NY', 'Berlin', 'Minsk', 'Kiev', 'Moscow'] 155
['NY', 'Berlin', 'Kiev', 'Minsk', 'Moscow'] 170
['NY', 'Kiev', 'Moscow', 'Minsk', 'Berlin'] 175
['NY', 'Kiev', 'Minsk', 'Moscow', 'Berlin'] 210
['NY', 'Kiev', 'Minsk', 'Berlin', 'Moscow'] 225
['NY', 'Kiev', 'Berlin', 'Minsk', 'Moscow'] 205
Optimal path: ['NY', 'Moscow', 'Kiev', 'Minsk', 'Berlin'] 155

Конечно, разработаны различные методы сокращения перебора, кроме того, переборные задачи допускают эффективное распараллеливание на многопроцессорную технику или вычисление сетью обычных компьютеров (см. например, отчет), но это не отменяет невозможности точного решения этой задачи, с ростом размера входных данных. Отсутствие же алгоритма субэкспоненциальной сложности для точного решения этой задачи следует из того, что эта задача является NP-полной, и общепринятой гипотезы о несовпадении классов P и NP.

Существуют различные алгоритмы для приближенного решения этой задачи или её частных случаев.

Метрическая задача коммивояжёра

Задача коммивояжёра называется метрической, если для матрицы расстояний выполнено неравенство треугольника:

$\forall i,j,k \ \ d_{ik} \leq d_{ij} + d_{jk}$

Для метрической задачи коммивояжёра существует приближенный алгоритм Кристофидеса.

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.