|
|
| Строка 1: |
Строка 1: |
| − | Задача коммивояжера (В англоязычной литературе — [[Traveling Salesman Problem]], сокращенно TSP), заключается в следующем:
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | Заданы ''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:Задачи]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}}
| + | |
