Как решить задачу коммивояжёра: методы, алгоритмы и решение на Python

Задача коммивояжёра (Travelling Salesman Problem, TSP) — одна из самых известных и сложных задач комбинаторной оптимизации. Её суть заключается в следующем:

Коммивояжёр должен посетить несколько городов ровно по одному разу и вернуться в исходный пункт, при этом минимизировав суммарное расстояние или стоимость поездки.

Представьте, что у вас есть N городов, и коммивояжёр (торговый агент) должен посетить каждый город ровно один раз и вернуться в исходный пункт. Задача — найти оптимальный маршрут, при котором суммарное расстояние (или стоимость поездки) минимально.
Формальное представление:

Пусть у нас есть граф с N вершинами (города) и взвешенными рёбрами (пути между городами с определённой длиной или стоимостью).
Нужно найти гамильтонов цикл минимальной длины, то есть такой маршрут, который проходит через каждую вершину ровно один раз и возвращается в начальную точку, при этом минимизируя суммарный вес (расстояние).

Эта задача имеет множество практических приложений, включая логистику, планирование маршрутов, оптимизацию цепочек поставок и даже анализ ДНК.

История и сложность задачи

Задача коммивояжёра формулировалась ещё в XVIII веке, но активно изучаться начала в XX веке с развитием вычислительных методов. Она относится к классу NP-трудных задач, что означает, что для её решения в общем виде не существует алгоритма, работающего за полиномиальное время.

Количество возможных маршрутов в задаче коммивояжёра растёт факториально с увеличением числа городов: при n городах число перестановок равно (n-1)!. Это делает задачу вычислительно сложной даже при относительно небольшом числе городов.

Методы решения

Существует несколько подходов к решению задачи коммивояжёра:

1. Полный перебор (Brute Force)

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

from itertools import permutations

def calculate_distance(route, distance_matrix):
    return sum(distance_matrix[route[i]][route[i+1]] for i in range(len(route)-1)) + distance_matrix[route[-1]][route[0]]

def brute_force_tsp(distance_matrix):
    n = len(distance_matrix)
    cities = list(range(n))
    min_distance = float('inf')
    best_route = None

    for perm in permutations(cities):
        current_distance = calculate_distance(perm, distance_matrix)
        if current_distance < min_distance:
            min_distance = current_distance
            best_route = perm

    return best_route, min_distance

# Пример использования
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

route, distance = brute_force_tsp(distance_matrix)
print("Лучший маршрут:", route)
print("Кратчайшее расстояние:", distance)

Разбор кода:

Используется itertools.permutations для генерации всех возможных маршрутов.
Функция calculate_distance() вычисляет длину маршрута, включая возвращение в начальный город.
Перебираются все возможные перестановки городов, выбирается маршрут с минимальным расстоянием.

Сложность:

Полный перебор имеет факториальную сложность O(n!)O(n!)O(n!), так как рассматриваются все возможные маршруты.
Это делает алгоритм непрактичным для больших nnn, например, уже при n=10n = 10n=10 количество возможных маршрутов достигает 3,628,800.

✅ Достоинства решения: Гарантированно находит оптимальное решение. Простая реализация.

❌ Недостатки решения: Экспоненциальная сложность — не подходит для больших входных данных. Требует хранения всех возможных маршрутов, что потребляет много памяти.

2. Динамическое программирование (алгоритм Беллмана-Хелда-Карпа)

Этот метод уменьшает количество операций, запоминая промежуточные результаты, но остаётся экспоненциально сложным, O(n² * 2^n).

from functools import lru_cache

def tsp_dp(distance_matrix):
    n = len(distance_matrix)
    all_visited = (1 << n) - 1  # Все города посещены

    @lru_cache(None)
    def visit(city, visited):
        if visited == all_visited:
            return distance_matrix[city][0]  # Возвращаемся в начальный город

        min_cost = float('inf')
        for next_city in range(n):
            if not (visited & (1 << next_city)):  # Если город еще не посещен
                new_cost = distance_matrix[city][next_city] + visit(next_city, visited | (1 << next_city))
                min_cost = min(min_cost, new_cost)

        return min_cost

    return visit(0, 1 << 0)

# Пример использования
distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

print("Кратчайшее расстояние (DP):", tsp_dp(distance_matrix))

Если вы хотите углубить свои знания в области анализа данных, машинного обучения и решения задач, подобных задаче коммивояжёра, обратите внимание на тренажёр-практикум по Python и SQL для ML и анализа данных от проекта ИнженеркаТех.

Разбор кода:

Функция tsp_dp(distance_matrix)

n = len(distance_matrix): определяет количество городов.
all_visited = (1 << n) - 1: битовая маска, где все города посещены (например, при n=4 это 0b1111).

Функция visit(city, visited)

Использует @lru_cache(None), что позволяет запоминать ранее вычисленные значения и избегать повторных вычислений.
visited — битовая маска посещённых городов (например, 0b0101 означает, что посещены 1-й и 3-й города).
Базовый случай: если visited == all_visited, возвращаем расстояние distance_matrix[city][0], т.е. возвращаемся в начальный город.
Рекурсивный случай: ищем минимальную стоимость маршрута, добавляя города, которые ещё не посещены.

Пример работы

Для входной матрицы:

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

Граф с 4 городами.

Вызывается visit(0, 1 << 0), т.е. стартуем из 0-го города и считаем минимальное расстояние.

Временная сложность:

Рекурсия обрабатывает каждое подмножество городов (их 2^n), и для каждого города выполняется O(n).
Итоговая сложность O(n^2 * 2^n), что намного лучше полного перебора O(n!), но всё ещё экспоненциальная.

Пространственная сложность:

Используется O(n * 2^n) памяти для хранения мемоизированных результатов.
@lru_cache(None) оптимизирует хранение значений.

✅ Достоинства решения: Гарантированно находит оптимальный маршрут. Гораздо быстрее полного перебора O(n!). Мемоизация (@lru_cache) снижает число повторных вычислений.

❌ Недостатки решения: Всё ещё экспоненциальная сложность (O(n^2 * 2^n)). Не масштабируется для n > 20-25. Использует много памяти (O(n * 2^n)).

3. Жадные алгоритмы

Простые эвристики, такие как «ближайший сосед» (Nearest Neighbor), позволяют быстро находить приближённые решения, но не гарантируют их оптимальность.

def nearest_neighbor_tsp(distance_matrix):
    n = len(distance_matrix)
    visited = [False] * n
    route = [0]  # Начинаем с первого города
    visited[0] = True

    for _ in range(n - 1):
        last_city = route[-1]
        nearest_city = min(
            [(i, distance_matrix[last_city][i]) for i in range(n) if not visited[i]],
            key=lambda x: x[1]
        )[0]
        route.append(nearest_city)
        visited[nearest_city] = True

    route.append(0)  # Возвращаемся в начальный город
    total_distance = sum(distance_matrix[route[i]][route[i+1]] for i in range(n))
    return route, total_distance

# Пример использования
route, distance = nearest_neighbor_tsp(distance_matrix)
print("Жадный маршрут:", route)
print("Приближённое расстояние:", distance)

Разбор кода

Функция nearest_neighbor_tsp(distance_matrix)

Инициализация:

visited = [False] * n – массив отслеживает, какие города уже посещены.
route = [0] – начинаем маршрут с первого города.
visited[0] = True – помечаем его как посещённый.

Основной цикл (for _ in range(n - 1)):

Находим ближайший непосещённый город:

nearest_city = min(
    [(i, distance_matrix[last_city][i]) for i in range(n) if not visited[i]],
    key=lambda x: x[1]
)[0]

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

Завершение маршрута:

Возвращаемся в стартовый город route.append(0).
Вычисляем общее расстояние маршрута.

Возвращает:

route – полученный маршрут.
total_distance – длина маршрута.

Временная сложность: O(n2)O(n^2)O(n2), так как:

Каждую итерацию находим ближайший город (O(n))
Делаем n-1 итераций → O(n2)O(n^2)O(n2).

Пространственная сложность: O(n)O(n)O(n) из-за хранения visited и route.

✅ Достоинства решения:

Быстрый алгоритм – работает за O(n2)O(n^2)O(n2), что намного лучше полного перебора O(n!) и ДП O(n^2 * 2^n).
Простая реализация.
Подходит для больших n (до 1000+).

❌ Недостатки решения:

Не гарантирует оптимальный маршрут.
Эффект жадности: может привести к "локальному минимуму", когда хороший выбор на ранних этапах приводит к плохому конечному решению.
Зависит от стартового города: разные стартовые точки могут давать разные маршруты.

4. Муравьиный алгоритм (Эвристический)

Муравьиный алгоритм — один из мощных подходов к решению задачи TSP.

from ACO import ACO, Graph  # Установите ACO-библиотеку или используйте самописный вариант

distance_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

aco = ACO(ant_count=10, generations=50, alpha=1.0, beta=2.0, rho=0.5, q=100)
graph = Graph(distance_matrix)
path, cost = aco.solve(graph)

print("Муравьиный алгоритм:", path)
print("Приближённое расстояние:", cost)

Разбор кода

aco = ACO(ant_count=10, generations=50, alpha=1.0, beta=2.0, rho=0.5, q=100)
graph = Graph(distance_matrix)
path, cost = aco.solve(graph)

ant_count=10 – количество муравьёв в каждой итерации.

generations=50 – количество итераций, за которые муравьи улучшают маршрут.

alpha=1.0 – коэффициент влияния феромона (чем больше, тем сильнее учитывается предыдущий опыт).

beta=2.0 – коэффициент влияния расстояния (чем больше, тем сильнее муравьи тяготеют к ближайшим городам).

rho=0.5 – коэффициент испарения феромона (чем больше, тем быстрее забываются старые маршруты).

q=100 – количество феромона, выделяемого муравьём после прохождения маршрута

Как работает ACO для TSP?

Инициализация:

Каждому ребру графа присваивается начальное значение феромона.

Генерация решений:

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

Обновление феромонов:

После каждого поколения муравьи оставляют феромон на маршрутах (чем короче маршрут, тем больше феромона).
Феромоны испаряются на всех маршрутах (rho регулирует скорость испарения).

Поиск лучшего маршрута:

Процесс повторяется в течение generations итераций, постепенно оптимизируя маршрут.

Временная сложность:

Примерно O(n^2 * ant_count * generations).
В реальных сценариях часто используется O(n³), что быстрее полного перебора O(n!) и DP O(n² * 2^n).

Пространственная сложность:

O(n²), так как требуется хранить феромоны для всех рёбер.

✅ Достоинства решения:

Приближённое решение за разумное время, даже для больших n (100+ городов).
Лучше жадного алгоритма, так как использует "память" (феромоны) и случайность.
Гибкость – можно настраивать параметры (alpha, beta, rho) для разных типов задач.

❌ Недостатки решения:

Не гарантирует оптимальный маршрут (может застрять в локальном минимуме).
Зависимость от параметров – неправильный подбор параметров может привести к плохим результатам.
Может работать дольше, чем жадные алгоритмы, если generations и ant_count велики.

4. Методы ветвей и границ (Branch and Bound)

Этот подход использует частичный перебор с отбрасыванием невыгодных вариантов, что позволяет существенно сократить время поиска

import heapq

def branch_and_bound_tsp(distance_matrix):
    n = len(distance_matrix)
    min_distance = float('inf')
    best_route = None
    def tsp(node, visited, cost, path):
        nonlocal min_distance, best_route
        if len(path) == n:
            cost += distance_matrix[node][0]
            if cost < min_distance:
                min_distance = cost
                best_route = path + [0]
            return
        for next_node in range(n):
            if next_node not in visited:
                tsp(next_node, visited | {next_node}, cost + distance_matrix[node][next_node], path + [next_node])
    tsp(0, {0}, 0, [0])
    return best_route, min_distance

Разбор кода

Функция branch_and_bound_tsp(distance_matrix)

Переменные:

n = len(distance_matrix) – количество городов.
min_distance = float('inf') – минимально найденное расстояние.
best_route = None – лучший найденный маршрут.

Рекурсивная функция tsp(node, visited, cost, path):

Базовый случай:
Если len(path) == n, значит обошли все города.
Добавляем расстояние до стартового города cost += distance_matrix[node][0].
Если новый маршрут лучше найденного, обновляем min_distance и best_route.
Рекурсивный случай:
Перебираем все возможные города next_node, которые ещё не посещены.
Вызываем tsp() для следующего города с обновлённым cost и path.

Запускаем обход с города 0:

tsp(0, {0}, 0, [0])

Стартуем с нуля, посещён только первый город.

Возвращает:

best_route – лучший найденный маршрут.
min_distance – длина этого маршрута.

Временная сложность:

В худшем случае: O(n!)O(n!)O(n!) (как полный перебор).
В среднем случае: значительно быстрее, так как отсекает ненужные ветви.
Использует нижнюю границу (bound), что сокращает количество перебираемых маршрутов.

Пространственная сложность:

O(n)O(n)O(n) – из-за хранения visited и path.

✅ Достоинства решения:

Находит оптимальное решение (если не прерывать алгоритм).
Лучше, чем полный перебор (O(n!)), так как отсекает плохие маршруты.
Не требует большого объёма памяти, как динамическое программирование (O(n * 2^n)) или ACO.

❌ Недостатки решения:

Всё ещё экспоненциальная сложность в худшем случае.
Может работать долго при n > 20, если не удаётся отсечь много ветвей.
Зависит от порядка посещения городов – можно ускорить, если предварительно отсортировать рёбра.

Применение задачи коммивояжёра

Несмотря на свою теоретическую сложность, TSP широко используется в реальном мире:

Логистика и транспорт: оптимизация маршрутов доставки товаров и передвижения транспорта.
Робототехника: планирование передвижений автономных роботов, дронов и производственных механизмов.
Молекулярная биология: анализ последовательностей ДНК.
Производственные процессы: маршрутизация станков и оптимизация производства.
Коммуникационные сети: минимизация затрат на соединение узлов сети.

Заключение

Задача коммивояжёра — не только одна из наиболее сложных математических задач, но и важный инструмент для решения множества практических проблем. Современные методы, включая эвристики и машинное обучение, позволяют находить хорошие приближённые решения даже для очень больших задач, делая её областью активных исследований в математике, информатике и прикладных науках.

Хотите еще больше углубить свои знания в области анализа данных, машинного обучения и математических задач? Присмотритесь к нашему тренажеру!

Особенности тренажёра:

Обширный курс: Более 80 задач, охватывающих различные аспекты анализа данных и машинного обучения.
Практическая направленность: Решение реальных задач с использованием Python (Numpy, OpenCV) и SQL (PostgreSQL).
Интерактивное обучение: Встроенная IDE с поддержкой более 50 языков программирования и AI-помощником, доступная 24/7.
Поддержка: Закрытый чат с преподавателями и другими участниками курса для оперативного обмена знаниями и решения возникающих вопросов.

Курс подходит для начинающих инженеров и разработчиков, желающих освоить аналитику данных и подготовиться к более сложным задачам в области машинного обучения. Среднее время прохождения курса составляет около 2 месяцев, что позволяет глубоко погрузиться в материал и закрепить полученные знания на практике.

Получить демо-доступ