Задача коммивояжера — различия между версиями

Версия 12:55, 4 августа 2008

Задача коммивояжера (В англоязычной литературе — 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.

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

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

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

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