Задача коммивояжера: Python, C++ Алгоритм

⚡ Умное резюме

Задача коммивояжера — это классическая NP-трудная задача оптимизации, которая заключается в поиске кратчайшего маршрута, включающего посещение каждого города ровно один раз и возвращение в начало координат, с использованием данных о расстояниях, предоставленных через граф.

  • 🗺️ Постановка задачи: Дан взвешенный граф городов и попарные расстояния. Необходимо найти гамильтонов цикл минимальной стоимости, начинающийся и заканчивающийся в одном и том же городе.
  • ⚙️ Семейства решений: Метод перебора перечисляет все n! маршрутов, метод ветвей и границ ограничивает поиск, динамическое программирование кэширует подзадачи, а метод ближайшего соседа предлагает быструю эвристику.
  • 📉 Динамическое программирование: Рекуррентная функция Хелда-Карпа cost(i, S, j) повторно использует кратчайшие пути между подмножествами вершин и дает точное решение со временем O(N² · 2^N).
  • 💻 Code Примеры: Учебное пособие поставляется в полностью рабочем состоянии. C++ и Python Реализации, вычисляющие оптимальную стоимость маршрута для матрицы смежности четырех городов.
  • 🌍 Области применения: Варианты TSP обеспечивают оптимизацию маршрутов доставки, сверление печатных плат, секвенирование ДНК, планирование телескопических операций и планирование траекторий комплектации заказов на складе.
  • 🤖 Под углом к ​​искусственному интеллекту: Современные методы обучения с подкреплением, графовые нейронные сети и эвристические алгоритмы, такие как алгоритм Лина-Кернигана и алгоритм Конкорда, позволяют решать крупномасштабные задачи коммивояжера, используемые в логистике.

Задача коммивояжера

Что такое задача коммивояжера (TSP)?

Задача коммивояжера (TSP) — это классическая задача комбинаторной оптимизации из теоретической информатики. Дана диаграмма городов, и задача TSP заключается в нахождении кратчайшего пути, который посещает каждую вершину ровно один раз и возвращается в исходный город.

В условии задачи приведен список городов, а также расстояния между каждой парой городов.

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

Пример ТСП

Рассмотрим граф ниже, где 1, 2, 3 и 4 обозначают города, а вес каждого ребра соответствует расстоянию между этими городами.

Пример ТСП

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

Для представленного выше графика оптимальный маршрут — это 1-2-4-3-1Стоимость самой короткой экскурсии составляет 10 + 25 + 30 + 15 = 80.

Различные решения проблемы коммивояжера

Различные решения проблемы коммивояжера

Задача коммивояжера классифицируется как NP-трудная, поскольку ни один известный полиномиальный алгоритм не решает её точно. Сложность экспоненциально возрастает с увеличением числа городов.

Существует несколько способов атаки на задачу коммивояжера (TSP). Наиболее распространенные подходы:

Метод грубой силы: Наивный метод вычисляет все возможные маршруты и сравнивает их. Количество маршрутов в графе с n городами равно... n!, что делает вычисления методом перебора очень затратными для всего, что находится за пределами примерно десяти городов.

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

В этом руководстве демонстрируется... подход динамического программирования, которая представляет собой мемоизированную версию метода ветвей и границ и соответствует алгоритму Беллмана-Хелда-Карпа.

Динамическое программирование: Это точный метод, который ищет оптимальное решение путем повторного использования перекрытий.ping Результаты решения подзадачи. Это медленнее, чем почти оптимальный вариант. жадные методыно он всегда возвращает глобально оптимальный маршрут.

Вычислительная сложность этого подхода составляет O(N² × 2^N), о чем мы поговорим позже в статье.

Метод ближайшего соседа: Эвристический жадный подход, который всегда переходит к ближайшему непосещенному городу. Он намного дешевле, чем динамическое программирование, но не гарантирует оптимального маршрута, поэтому используется для почти оптимальных решений, когда скорость важнее точного минимума.

Алгоритм решения задачи коммивояжера

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

  • График G = (V, E) представляет собой множество вершин и рёбер.
  • V — это множество вершин.
  • E — это множество ребер.
  • Вершины соединены ребрами.
  • Dist(i, j) обозначает неотрицательное расстояние между вершинами i и j.

Предположим, S — подмножество городов, взятых из множества {1, 2, 3, …, n}, где i и j — два города из этого подмножества. Тогда cost(i, S, j) — это длина кратчайшего пути, который начинается в точке i, посещает каждый город в S ровно один раз и заканчивается в точке j.

Например, cost(1, {2, 3, 4}, 1) обозначает кратчайший путь, где:

  • Стартовый город — 1.
  • Города 2, 3 и 4 посещаются только один раз.
  • Конечная точка - 1.

Рекуррентное соотношение динамического программирования выглядит следующим образом:

  • Поставьте cost(i, {}, i) = 0, что означает, что мы начинаем и заканчиваем в точке i с нулевыми затратами.
  • После появления |S| > 1определить cost(i, S, 1) = ∞ для i ≠ 1, поскольку реальная стоимость тура пока неизвестна.
  • Начиная с города 1, выберите следующий город таким образом, чтобы cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] для i ∈ S и i ≠ j.

Для представленного выше графа матрица смежности выглядит следующим образом:

Алгоритм решения задачи коммивояжера

dist(i, j)1234
10101520
21003525
31535030
42025300

Вот как работает алгоритм:

Шаг 1) Путешествие начинается в городе 1, включает посещение каждого второго города по одному разу и возвращается в город 1.

Шаг 2) S — подмножество городов. Для каждого |S| > 1 инициализируйте cost(i, S, 1) = ∞, Вот cost(i, S, j) обозначает маршрут, начинающийся в точке i, посещающий города в S один раз и достигающий точки j. Мы начинаем с бесконечности, поскольку расстояние в этой точке неизвестно. Таким образом, значения следующие:

cost(2, {3, 4}, 1) = ∞ Это означает, что мы начинаем в городе 2, проходим через города 3 и 4 и достигаем города 1 с неизвестной стоимостью. Аналогично:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

Шаг 3) Для каждого подмножества S вычислите:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ], Где j ∈ S и i ≠ j.

Это маршрут с минимальной стоимостью, который начинается в городе i, посещает подмножество городов один раз и возвращается в город j. Поскольку маршрут начинается в городе 1, оптимальная стоимость составляет cost(1, {other cities}, 1).

Пошаговая инструкция по устранению повторения проблемы

Теперь S = {1, 2, 3, 4}. В множестве четыре элемента, поэтому количество подмножеств равно 2^4 = 16Эти подмножества:

1) |С| = 0: {Φ}

2) |С| = 1: {{1}, {2}, {3}, {4}}

3) |С| = 2: {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |С| = 3: {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |С| = 4: {{1, 2, 3, 4}}

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

Алгоритм вычислений разворачивается следующим образом:

1) |С| = Ф:

  • cost(2, Φ, 1) = dist(2, 1) = 10
  • cost(3, Φ, 1) = dist(3, 1) = 15
  • cost(4, Φ, 1) = dist(4, 1) = 20

2) |С| = 1:

  • cost(2, {3}, 1) = dist(2, 3) + cost(3, Φ, 1) = 35 + 15 = 50
  • cost(2, {4}, 1) = dist(2, 4) + cost(4, Φ, 1) = 25 + 20 = 45
  • cost(3, {2}, 1) = dist(3, 2) + cost(2, Φ, 1) = 35 + 10 = 45
  • cost(3, {4}, 1) = dist(3, 4) + cost(4, Φ, 1) = 30 + 20 = 50
  • cost(4, {2}, 1) = dist(4, 2) + cost(2, Φ, 1) = 25 + 10 = 35
  • cost(4, {3}, 1) = dist(4, 3) + cost(3, Φ, 1) = 30 + 15 = 45

3) |С| = 2:

  • cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
  • cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
  • cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |С| = 3:

  • cost(1, {2, 3, 4}, 1) = min [ dist(1, 2) + cost(2, {3, 4}, 1) = 10 + 70 = 80, dist(1, 3) + cost(3, {2, 4}, 1) = 15 + 65 = 80, dist(1, 4) + cost(4, {2, 3}, 1) = 20 + 75 = 95 ] = 80

Таким образом, оптимальное решение — это 1-2-4-3-1.

Алгоритм решения задачи коммивояжера

Псевдо-код

Algorithm: Traveling-Salesman-Problem
Cost (1, {}, 1) = 0
for s = 2 to n do
    for all subsets S belongs to {1, 2, 3, ..., n} of size s
        Cost (s, S, 1) = Infinity
    for all i in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

Реализация на C/C++

Вот реализация в C++В приведенной ниже версии исправлена ​​ранняя ошибка в исходном коде. return Ошибка, которая возвращалась после первой же перестановки вместо того, чтобы перечислить все маршруты.

#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000

int tsp(int graph[][V], int s) {
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);

    int min_cost = MAX;
    do {
        int current_cost = 0;
        int j = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_cost += graph[j][vertex[i]];
            j = vertex[i];
        }
        current_cost += graph[j][s];
        min_cost = min(min_cost, current_cost);
    } while (next_permutation(vertex.begin(), vertex.end()));

    return min_cost;
}

int main() {
    int graph[][V] = {
        { 0, 10, 15, 20 },
        { 10, 0, 35, 25 },
        { 15, 35, 0, 30 },
        { 20, 25, 30, 0 }
    };
    int s = 0;
    cout << tsp(graph, s) << endl;
    return 0;
}

Выход:

80

Реализация в Python

Python реализация отражает C++ версия. Она исправляет ошибку в исходном тексте. from itertools, import опечатка в запятой, неправильно расставленное return внутри внутренней петли и случайная вмятина на s = 0.

from sys import maxsize
from itertools import permutations

V = 4

def tsp(graph, s):
    vertex = []
    for i in range(V):
        if i != s:
            vertex.append(i)

    min_cost = maxsize
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            current_cost += graph[k][j]
            k = j
        current_cost += graph[k][s]
        min_cost = min(min_cost, current_cost)
    return min_cost

graph = [[0, 10, 15, 20],
         [10, 0, 35, 25],
         [15, 35, 0, 30],
         [20, 25, 30, 0]]
s = 0
print(tsp(graph, s))

Выход:

80

Академические решения для TSP

Специалисты в области компьютерных наук десятилетиями искали улучшенные полиномиальные алгоритмы для решения задачи коммивояжера. До сих пор задача коммивояжера остается NP-трудной.

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

  • Классическая симметричная задача коммивояжера решается с помощью Метод нулевого суффикса.
  • Алгоритм оптимизации на основе биогеографии Использует стратегии миграции для решения задач оптимизации, которые соответствуют задаче коммивояжера.
  • Многоцелевой эволюционный алгоритм Он предназначен для решения многоцелевой задачи коммивояжера и основан на алгоритме NSGA-II.
  • Мультиагентная система Данный подход решает задачу коммивояжера для N городов при фиксированных вычислительных ресурсах.
  • Эвристика Лин-Кернигана и его преемник ЛКХ Проведение туров с точностью до 2-3% от оптимальной, особенно в случаях с миллионами городов.
  • Согласие Использует секущие плоскости и метод ветвей и отсечений для вычисления точных оптимумов для тестовых примеров, включающих десятки тысяч городов.

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

Задача коммивояжера встречается в реальном мире как в чистом, так и в модифицированном виде. Основные примеры её применения:

  • Планирование, логистика и производство микрочипов: В микрочиповой промышленности проблемы внедрения микросхем моделируются как варианты задачи коммивояжера (TSP) для минимизации времени перемещения роботизированной руки.
  • секвенирование ДНК: Модифицированный алгоритм TSP используется в секвенировании ДНК, где города представляют собой фрагменты ДНК, а расстояния — сходство между фрагментами.
  • Астрономия: Астрономы используют алгоритм TSP для минимизации времени, затрачиваемого на наведение телескопов между объектами наблюдения.
  • Оптимальное управление: В формулировках задачи коммивояжера моделируются задачи оптимального управления, в которых необходимо соблюдать множество ограничений, минимизируя при этом стоимость обхода.
  • Доставка последней мили: AmazonПриложения для доставки еды, такие как UPS, решают динамические варианты задачи коммивояжера для упорядочивания остановок водителей.
  • Комплектация на складе: Роботы и операторы-сборщики следуют оптимизированным маршрутам TSP, что сокращает время перемещения внутри распределительных центров.

Анализ сложности TSP

  • Сложность времени: Метод динамического программирования Хелда-Карпа решает 2 задачи.N подмножества для каждого начального узла, что дает N × 2^N подзадачи. Объединение каждой подзадачи занимает линейное время. Если исходный узел не указан, требуется внешний цикл по N узлам. Общая временная сложность составляет O(N² × 2^N).
  • Космическая сложность: В таблице DP хранятся C(S, i) для каждого подмножества S множества вершин. Существует 2N подмножества на узел, поэтому пространственная сложность составляет O(N × 2^N), который часто записывается как O(2^N) когда N рассматривается как фиксированное значение.

Далее, узнайте о Сито Эратосфена Алгоритм.

Часто задаваемые вопросы (FAQ)

Задача коммивояжера заключается в поиске кратчайшего маршрута, начинающегося в выбранном городе, посещающего каждый второй город ровно один раз и возвращающегося в начало координат. Это эталонная NP-трудная задача оптимизации в информатике.

Задача коммивояжера (TSP) является NP-трудной, поскольку не существует полиномиального алгоритма, который бы точно решал каждую задачу. Метод перебора работает за время O(n!), а наилучший точный подход динамического программирования все еще требует времени O(N² · 2^N), которое экспоненциально возрастает.

Динамическое программирование кэширует кратчайшие пути во всех подмножествах городов. Рекуррентная функция Хелда-Карпа cost(i, S, j) повторно использует меньшие подзадачи для построения оптимального маршрута, сокращая стоимость перебора с O(n!) до O(N² · 2^N).

Варианты TSP используются для маршрутизации доставки «последней мили», планирования маршрутов комплектации заказов на складе, сверления печатных плат, секвенирования ДНК, планирования телескопических перевозок и планирования загрузки грузовиков. Любая задача, которая включает посещение фиксированного набора остановок и возвращение на базу, является кандидатом на роль TSP.

Метод перебора проверяет все возможные перестановки городов и всегда возвращает точный оптимум со стоимостью O(n!). Метод ближайшего соседа жадно переходит к ближайшему непосещенному городу за время O(n²), обеспечивая быстрый, но неоптимальный маршрут, обычно на 25% превосходящий оптимум.

Алгоритмы Лин-Кернигана, LKH, Кристофидеса, имитация отжига, оптимизация с помощью муравьиной колонии и генетические алгоритмы позволяют получить почти оптимальные маршруты для больших задач коммивояжера. Concorde решает точную задачу коммивояжера для эталонных входных данных с десятками тысяч городов.

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

Да. GitHub Copilot и аналогичные ИИ-помощники помогают создавать решения для задачи коммивояжера. C++, Python или JavaПредлагается использовать мемоизацию по методу Хелда-Карпа и генерировать эвристические алгоритмы, такие как алгоритм ближайшего соседа или алгоритм 2-opt, для сравнительного анализа.

Подведем итог этой публикации следующим образом: