Проблема комівояжера: Python, C++ Алгоритм

Що таке проблема комівояжера (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), про що ми поговоримо далі у статті.

Метод найближчого сусіда: Евристичний жадібний підхід, який завжди переходить до найближчого невідвіданого міста. Він набагато дешевший за динамічне програмування, але не гарантує оптимального маршруту, тому використовується для близьких до оптимальних рішень, коли швидкість важливіша за точні мінімуми.

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

Ми використовуємо підхід динамічного програмування для розв'язання TSP. Перш ніж розпочати алгоритм, давайте визначимося з деякими термінологіями:

• Графік 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.

Для наведеного вище графіка матриця суміжності має такий вигляд:

Ось як працює алгоритм:

Крок 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) |S| = 0: {Φ}

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

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

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

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

Оскільки тур починається в місті 1, ми можемо відкинути кожну підмножину, що містить місто 1, під час обчислення проміжних витрат.

Алгоритм розрахунку розгортається наступним чином:

1) |S| = Φ:

• вартість(2, Φ, 1) = відстань(2, 1) = 10
• вартість(3, Φ, 1) = відстань(3, 1) = 15
• вартість(4, Φ, 1) = відстань(4, 1) = 20

2) |S| = 1:

• вартість(2, {3}, 1) = відстань(2, 3) + вартість(3, Φ, 1) = 35 + 15 = 50
• вартість(2, {4}, 1) = відстань(2, 4) + вартість(4, Φ, 1) = 25 + 20 = 45
• вартість(3, {2}, 1) = відстань(3, 2) + вартість(2, Φ, 1) = 35 + 10 = 45
• вартість(3, {4}, 1) = відстань(3, 4) + вартість(4, Φ, 1) = 30 + 20 = 50
• вартість(4, {2}, 1) = відстань(4, 2) + вартість(2, Φ, 1) = 25 + 10 = 35
• вартість(4, {3}, 1) = відстань(4, 3) + вартість(3, Φ, 1) = 30 + 15 = 45

3) |S| = 2:

• вартість(2, {3, 4}, 1) = min [ відстань(2, 3) + вартість(3, {4}, 1) = 35 + 50 = 85, відстань(2, 4) + вартість(4, {3}, 1) = 25 + 45 = 70 ] = 70
• вартість(3, {2, 4}, 1) = min [ відстань(3, 2) + вартість(2, {4}, 1) = 35 + 45 = 80, відстань(3, 4) + вартість(4, {2}, 1) = 30 + 35 = 65 ] = 65
• вартість(4, {2, 3}, 1) = min [ відстань(4, 2) + вартість(2, {3}, 1) = 25 + 50 = 75, відстань(4, 3) + вартість(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |S| = 3:

• вартість(1, {2, 3, 4}, 1) = min [ відстань(1, 2) + вартість(2, {3, 4}, 1) = 10 + 70 = 80, відстань(1, 3) + вартість(3, {2, 4}, 1) = 15 + 65 = 80, відстань(1, 4) + вартість(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

Комп'ютерні науковці витратили десятиліття на пошуки покращених поліноміальних алгоритмів для задачі комівояжера. Поки що TSP залишається NP-складною.

Кілька опублікованих методів зменшують практичну складність для конкретних сімейств екземплярів TSP:

• Класична симетрична TSP розв'язується за допомогою Метод нульового суфікса.
• Команда Алгоритм оптимізації на основі біогеографії використовує стратегії міграції для вирішення задач оптимізації, що відповідають TSP.
• Команда Багатоцільовий еволюційний алгоритм розроблений для багатоцільового TSP та базується на NSGA-II.
• Команда Мультиагентна система підхід вирішує задачу TSP для N міст з фіксованими обчислювальними ресурсами.
• Команда Евристика Ліна-Кернігана та її наступник ЛКХ проводити тури в межах 2-3% від оптимального значення для випадків з мільйонами міст.
• Згода використовує площини сікання та метод розгалуження та розрізання для обчислення точних оптимумів для контрольних прикладів з десятками тисяч міст.

Застосування задачі комівояжера

Задача комівояжера проявляється в реальному світі як у чистому, так і в модифікованому вигляді. Деякі з основних застосувань:

• Планування, логістика та виробництво мікрочіпів: Проблеми вставки чіпів у мікрочіповій промисловості моделюються як варіанти TSP, щоб мінімізувати час переміщення роботизованої руки.
• Секвенування ДНК: Модифікований TSP використовується в секвенуванні ДНК, де міста представляють фрагменти ДНК, а відстані представляють подібність між фрагментами.
• астрономія: Астрономи використовують TSP, щоб мінімізувати час, витрачений на переміщення телескопів між цілями спостереження.
• Оптимальне керування: Формулювання TSP моделюють задачі оптимального керування, де необхідно дотримуватися кількох обмежень, мінімізуючи витрати на обхід.
• Доставка на останню милю: Amazon, UPS та додатки для доставки їжі вирішують динамічні варіанти TSP для упорядкування зупинок для водіїв.
• Комплектація зі складу: Роботизовані та людські збирачі дотримуються маршрутів, оптимізованих TSP, що скорочує час подорожі всередині розподільчих центрів.

Аналіз складності TSP

• Складність часу: Підхід динамічного програмування Хелда-Карпа вирішує задачу 2^N підмножини для кожного початкового вузла, що дає N × 2^N підзадачі. Кожна підзадача об'єднується за лінійний час. Якщо початковий вузол не визначено, потрібен зовнішній цикл через N вузлів. Загальна часова складність становить O(N² × 2^N).
• Складність простору: Таблиця DP зберігає C(S, i) для кожної підмножини S множини вершин. Існує 2^N підмножин на вузол, тому складність простору дорівнює O(N × 2^N), що часто записується як O(2^N) коли N вважається фіксованим.

Далі дізнайтеся про Алгоритм «Решето Ератосфена»..

Поширені запитання