Решение задачи коммивояжёра на Python: методы и реализация

Задача коммивояжёра (Traveling Salesman Problem, TSP) — одна из самых известных NP-сложных задач в комбинаторной оптимизации. Её суть заключается в поиске кратчайшего маршрута, проходящего через все заданные города ровно по одному разу с возвратом в исходную точку. В этой статье мы рассмотрим несколько подходов к решению TSP на Python, включая точные и эвристические методы.

---

1. Точное решение: полный перебор

Для небольшого числа городов (N ≤ 10) можно использовать метод полного перебора всех возможных маршрутов. Хотя алгоритм имеет факториальную сложность O(N!), он гарантирует нахождение оптимального решения.

Пример кода

import itertools

def tsp_brute_force(distances):
    n = len(distances)
    min_length = float('inf')
    best_path = []

    # Генерируем все возможные перестановки городов
    for permutation in itertools.permutations(range(1, n)):
        current_length = 0
        previous = 0  # Начинаем с города 0
        for city in permutation:
            current_length += distances[previous][city]
            previous = city
        current_length += distances[previous][0]  # Возвращаемся в начальный город

        if current_length < min_length:
            min_length = current_length
            best_path = [0] + list(permutation) + [0]

    return min_length, best_path

# Пример матрицы расстояний (4 города)
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

length, path = tsp_brute_force(distances)
print(f"Кратчайший маршрут: {path}, длина: {length}")

---

2. Жадный алгоритм “Ближайший сосед”

Для больших N применяют эвристики. Один из простейших методов — жадный алгоритм, который на каждом шаге выбирает ближайший непосещённый город. Решение может быть субоптимальным, но работает за O(N²).

Реализация

def tsp_greedy(distances):
    n = len(distances)
    unvisited = set(range(1, n))
    current = 0
    path = [0]
    total_length = 0

    while unvisited:
        next_city = min(unvisited, key=lambda x: distances[current][x])
        total_length += distances[current][next_city]
        path.append(next_city)
        unvisited.remove(next_city)
        current = next_city

    # Возвращаемся в начальный город
    total_length += distances[current][0]
    path.append(0)
    return total_length, path

length, path = tsp_greedy(distances)
print(f"Жадный алгоритм: {path}, длина: {length}")

---

3. Генетический алгоритм (используем библиотеку mlrose)

Для сложных случаев с десятками городов подходят метаэвристики. Установите библиотеку:

pip install mlrose

Пример кода

import mlrose
import numpy as np

# Создаем список координат городов (пример для 5 городов)
coords = [(0, 0), (1, 2), (3, 1), (5, 4), (2, 3)]

# Инициализируем задачу
problem = mlrose.TSPOpt(length=len(coords), coords=coords, 
                        maximize=False, source_dist=mlrose.distances.euclidean)

# Решаем генетическим алгоритмом
best_path, best_length = mlrose.genetic_alg(problem, mutation_prob=0.2, 
                                            max_attempts=100, random_state=2)

print(f"Генетический алгоритм: {best_path}, длина: {best_length}")

---

4. Визуализация маршрута

Используем matplotlib для отображения пути:

import matplotlib.pyplot as plt

def plot_path(coords, path):
    x = [coords[i][0] for i in path]
    y = [coords[i][1] for i in path]
    plt.plot(x, y, 'o-')
    plt.title(f"Длина маршрута: {best_length:.2f}")
    plt.show()

# Пример координат и пути
coords = [(0, 0), (1, 2), (3, 1), (5, 4), (2, 3)]
best_path = [0, 1, 2, 4, 3, 0]  # Пример результата
plot_path(coords, best_path)

---

Сравнение методов

Метод	Точность	Скорость	Рекомендуемый N
Полный перебор	Точный	O(N!)	≤ 10
Жадный алгоритм	Субоптимальн	O(N²)	Любой
Генетический алгоритм	Приближённый	Зависит от параметров	≥ 20

---

Заключение

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