|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Задача коммивояжераМатериал из CustisWikiВерсия от 19:19, 19 апреля 2006; StasFomin (обсуждение | вклад) Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Задача коммивояжера (В англоязычной литературе — Traveling Salesman Problem, сокращенно TSP), заключается в следующем: Заданы n городов и попарные расстояния между ними, являющиеся положительными целыми числами. Чему равна наименьшая возможная длина кольцевого маршрута, проходящего по одному разу через все города? Иными словами, требуется найти минимально возможное значение суммы , где минимум берется по всем перестановкам чисел 1,…,n. Приведенный ниже пример переборного алгоритма и его выполнения, демонстрирует его неэффективность, и невозможность нахождения точного решения для данных реальных объемов: # Находит и возвращает гамильтонов цикл минимального веса # в графе 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 ['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. Существуют различные алгоритмы для приближенного решения этой задачи или ее частных случаев. Метрическая задача коммивояжераЗадача коммивояжера называется метрической, если для матрицы расстояний выполнено неравенство треугольника:
Для метрической задачи коммивояжера существует приближенный алгоритм Кристофидеса. Репликация: База Знаний «Заказных Информ Систем» → «Задача коммивояжера» Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
![]() |
![]() |
![]() |