Проблем с пътуващия търговец: Python, C++ алгоритъм

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

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

Алгоритъм за задача на пътуващия търговец

Използваме подхода на динамично програмиране за решаване на 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) = мин [ разстояние(2, 3) + цена(3, {4}, 1) = 35 + 50 = 85, разстояние(2, 4) + цена(4, {3}, 1) = 25 + 45 = 70 ] = 70
• цена(3, {2, 4}, 1) = мин [ разстояние(3, 2) + цена(2, {4}, 1) = 35 + 45 = 80, разстояние(3, 4) + цена(4, {2}, 1) = 30 + 35 = 65 ] = 65
• цена(4, {2, 3}, 1) = мин [ разстояние(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) = мин [ разстояние(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 се третира като фиксирано.

След това научете за Алгоритъмът Сито на Ератостен.

Въпроси и Отговори