StasFomin в 17:52, 30 ноября 2011

2011-11-30T17:52:38Z

Новая страница

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

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

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

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

<code-python>
# Находит и возвращает гамильтонов цикл минимального веса
# в графе 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

<graph>
graph G{ rankdir=LR;
NY -- Berlin[fontcolor="blue",label="$50",style="bold"];
NY -- Moscow[fontcolor="blue",label="$60",style="bold"];
NY -- Kiev[fontcolor="blue",label="$80",style="solid"];
Moscow -- Berlin[fontcolor="blue",label="$50",style="solid"];
Moscow -- Minsk[fontcolor="blue",label="$15",style="solid"];
Moscow -- Kiev[fontcolor="blue",label="$10",style="bold"];
Minsk -- Berlin[fontcolor="blue",label="$20",style="bold"];
Minsk -- Kiev[fontcolor="blue",label="$15",style="bold"];
Berlin -- Kiev[fontcolor="blue",label="$30",style="solid"];
}
</graph>

Конечно, разработаны различные методы сокращения перебора, кроме того, переборные задачи допускают эффективное распараллеливание на многопроцессорную технику или вычисление сетью обычных компьютеров (см. например, [http://www.tsp.gatech.edu/d15sol/ отчет]), но это не отменяет невозможности точного решения этой задачи, с ростом размера входных данных. Отсутствие же алгоритма субэкспоненциальной сложности для точного решения этой задачи следует из того, что эта задача является NP-полной, и общепринятой гипотезы о несовпадении классов '''P''' и '''NP'''.

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

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

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

<m>
\forall i,j,k \ \ d_{ik} \leq d_{ij} + d_{jk}
</m>

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

[[Category:Задачи]]

Задача коммивояжера - История изменений

StasFomin в 17:52, 30 ноября 2011