Problém obchodního cestujícího: Python, C++ Algoritmus
Sarah Chen
Co je problém cestujícího prodejce (TSP)?
Problém cestovního obchodníka (TSP) je klasickým kombinatorikovým problémem teoretické informatiky. Problém vyžaduje najít nejkratší cestu v grafu s podmínkou navštívit všechny uzly pouze jednou a vrátit se do původního města.
Problém uvádí seznam měst spolu se vzdálenostmi mezi jednotlivými městy.
Cíl: Chcete-li začít z původního města, navštivte ostatní města pouze jednou a znovu se vraťte do původního města. Naším cílem je najít nejkratší možnou cestu k dokončení okružní trasy.
Příklad TSP
Zde je uveden graf, kde 1, 2, 3 a 4 představují města a váha spojená s každou hranou představuje vzdálenost mezi těmito městy.
Cílem je najít nejkratší možnou cestu pro prohlídku, která začíná z původního města, prochází grafem, zatímco ostatní města nebo uzly navštíví pouze jednou, a vrací se do výchozího města.
Pro výše uvedený graf je optimální cestou sledovat cestu minimálních nákladů: 1-2-4-3-1. A tato nejkratší cesta by stála 10+25+30+15 =80
Různá řešení problému cestujícího prodejce
Problém cestovního obchodníka (TSP) je klasifikován jako NP-těžký problém, protože nemá žádný polynomiální časový algoritmus. Složitost se exponenciálně zvyšuje s rostoucím počtem měst.
Existuje několik způsobů, jak vyřešit problém cestujícího prodejce (tsp). Některá populární řešení jsou:
Přístup hrubou silou je naivní metoda pro řešení problémů obchodního cestujícího. Při tomto přístupu nejprve vypočítáme všechny možné cesty a poté je porovnáme. Počet cest v grafu sestávajícím z n měst je n! Řešení problému obchodního cestujícího v tomto přístupu hrubou silou je výpočetně velmi nákladné.
Metoda větvení a vazby: V tomto přístupu je problém rozdělen na dílčí problémy. Řešení těchto jednotlivých dílčích problémů by poskytlo optimální řešení.
Tento tutoriál demonstruje přístup dynamického programování, rekurzivní verzi této metody větvení a vazby, k vyřešení problému obchodního cestujícího.
Dynamické programování je taková metoda pro hledání optimálních řešení analýzou všech možných cest. Je to jedna z exaktních metod řešení, která řeší problémy cestujících obchodníků s relativně vyššími náklady zištné metody které poskytují téměř optimální řešení.
Výpočetní náročnost tohoto přístupu je O(N^2 * 2^N) který je popsán dále v tomto článku.
Metoda nejbližšího souseda je heuristický přístup založený na chamtivosti, kdy vybíráme nejbližší sousední uzel. Tento přístup je výpočetně levnější než dynamický přístup. Neposkytuje však záruku optimálního řešení. Tato metoda se používá pro téměř optimální řešení.
Algoritmus pro problém cestujícího prodejce
Použijeme přístup dynamického programování k řešení problému Travelling Salesman (TSP).
Před spuštěním algoritmu se seznámíme s některými terminologiemi:
- Graf G=(V, E), což je množina vrcholů a hran.
- V je množina vrcholů.
- E je množina hran.
- Vrcholy jsou spojeny přes hrany.
- Dist(i,j) označuje nezápornou vzdálenost mezi dvěma vrcholy i a j.
Předpokládejme, že S je podmnožina měst a patří do {1, 2, 3, …, n}, kde 1, 2, 3…n jsou města a i, j jsou dvě města v této podmnožině. Nyní jsou náklady (i, S, j) definovány tak, jako délka nejkratší cesty navštěvující uzel v S, který má právě jednou počáteční a koncový bod jako i a j.
Například cena (1, {2, 3, 4}, 1) označuje délku nejkratší cesty, kde:
- Počáteční město je 1
- Města 2, 3 a 4 jsou navštívena pouze jednou
- Koncový bod je 1
Algoritmus dynamického programování by byl:
- Set cost(i, , i) = 0, což znamená, že začínáme a končíme v i a cena je 0.
- Když |S| > 1, definujeme náklady(i, S, 1) = ∝ kde i !=1 . Protože zpočátku neznáme přesné náklady na dosažení města i do města 1 přes jiná města.
- Nyní musíme začít v 1 a dokončit prohlídku. Musíme vybrat další město takovým způsobem-
cena(i, S, j)=min cena (i, S−{i}, j)+dist(i,j) kde i∈S a i≠j
Pro daný obrázek by matice sousedství byla následující:
| dist(i,j) | 1 | 2 | 3 | 4 |
| 1 | 0 | 10 | 15 | 20 |
| 2 | 10 | 0 | 35 | 25 |
| 3 | 15 | 35 | 0 | 30 |
| 4 | 20 | 25 | 30 | 0 |
Podívejme se, jak náš algoritmus funguje:
Krok 1) Zvažujeme, že naše cesta začne ve městě 1, jednou navštívíme další města a vrátíme se do města 1.
Krok 2) S je podmnožina měst. Podle našeho algoritmu pro všechny |S| > 1, nastavíme cenu vzdálenosti (i, S, 1) = ∝. Zde cost(i, S, j) znamená, že začínáme ve městě i, jednou navštívíme města S a nyní jsme ve městě j. Tuto cenu cesty jsme nastavili jako nekonečno, protože zatím neznáme vzdálenost. Hodnoty tedy budou následující:
Cena (2, {3, 4}, 1) = ∝ ; notace označuje, že začínáme ve městě 2, procházíme městy 3, 4 a dosahujeme 1. A cena cesty je nekonečná. Podobně-
cena(3, {2, 4}, 1) = ∝
cena(4, {2, 3}, 1) = ∝
Krok 3) Nyní pro všechny podmnožiny S musíme najít následující:
cena(i, S, j)=min cena (i, S−{i}, j)+dist(i,j), kde j∈S a i≠j
To znamená cestu minimálních nákladů pro začátek v i, procházení podmnožinou měst jednou a návrat do města j. Vzhledem k tomu, že cesta začíná ve městě 1, optimální cena trasy by byla = cena (1, {jiná města}, 1).
Pojďme zjistit, jak toho můžeme dosáhnout:
Nyní S = {1, 2, 3, 4}. Existují čtyři prvky. Počet podmnožin tedy bude 2^4 nebo 16. Tyto podmnožiny jsou-
1) |S| = Null:
{Φ}
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}}
Protože začínáme na 1, mohli bychom vyřadit podmnožiny obsahující město 1.
Výpočet algoritmu:
1) |S| = Φ:
náklady (2, Φ, 1) = dist(2, 1) = 10
náklady (3, Φ, 1) = dist(3, 1) = 15
náklady (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
cena (2, {3}, 1) = dist(2, 3) + cena (3, Φ, 1) = 35+15 = 50
cena (2, {4}, 1) = dist(2, 4) + cena (4, Φ, 1) = 25+20 = 45
cena (3, {2}, 1) = dist(3, 2) + cena (2, Φ, 1) = 35+10 = 45
cena (3, {4}, 1) = dist(3, 4) + cena (4, Φ, 1) = 30+20 = 50
cena (4, {2}, 1) = dist(4, 2) + cena (2, Φ, 1) = 25+10 = 35
cena (4, {3}, 1) = dist(4, 3) + cena (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
cena (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
cena (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
cena (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) |S| = 3:
cena (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
Takže optimální řešení by bylo 1-2-4-3-1
Pseudo kód
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 Є S and i ≠ 1
Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j}
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)
Implementace v C/C++
Zde je implementace v C++:
#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;
while(next_permutation(vertex.begin(), vertex.end()))
{
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);
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;
}
Výstup:
80
provádění Python
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
next_permutation=permutations(vertex)
for i in next_permutation:
current_cost = 0
k = s
for j in i:
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))
Výstup:
80
Akademická řešení TSP
Počítačoví vědci strávili roky hledáním vylepšeného polynomiálního časového algoritmu pro problém Traveling Salesman. Až dosud je problém stále NP-těžký.
Ačkoli některá z následujících řešení byla publikována v posledních letech, která do určité míry snížila složitost:
- Klasický symetrický TSP je řešen metodou Zero Suffix Method.
- Optimalizační algoritmus založený na biogeografii je založen na strategii migrace pro řešení optimalizačních problémů, které lze plánovat jako TSP.
- Multi-Objective Evolutionary Algorithm je navržen pro řešení více TSP založených na NSGA-II.
- Multi-Agent System řeší TSP N měst s pevnými zdroji.
Aplikace problému obchodního cestujícího
Travelling Salesman Problem (TSP) se v reálném světě uplatňuje ve své nejčistší i modifikované podobě. Některé z nich jsou:
- Plánování, logistika a výroba mikročipů: Problémy s vkládáním čipů přirozeně vznikají v průmyslu mikročipů. Tyto problémy lze naplánovat jako problémy cestujícího prodejce.
- DNA sekvenování: Mírná modifikace problému obchodního cestujícího může být použita při sekvenování DNA. Zde města představují fragmenty DNA a vzdálenost představuje míru podobnosti mezi dvěma fragmenty DNA.
- Astronomie: Problém cestujícího obchodníka používají astronomové, aby minimalizovali čas strávený pozorováním různých zdrojů.
- Problém optimálního ovládání: Travelling Salesman Formulaci problému lze aplikovat na problémy s optimální kontrolou. Může být přidáno několik dalších omezení.
Analýza složitosti TSP
- Časová složitost: Existuje celkem 2N dílčí problémy pro každý uzel. Celkový počet dílčích problémů by tedy byl N*2N. Řešení každého z dílčích problémů vyžaduje lineární čas. Pokud není uzel počátku zadán, musíme spustit smyčky pro N uzlů.
Celková časová složitost pro optimální řešení by tedy byla Počet uzlů * Počet dílčích problémů * čas na vyřešení každého dílčího problému. Časovou složitost lze definovat jako O(N2 * 2^N).
- Prostorová složitost: Přístup dynamického programování používá paměť k ukládání C(S, i), kde S je podmnožina množiny vrcholů. K dispozici jsou celkem 2N podmnožiny pro každý uzel. Prostorová složitost je tedy O(2^N).
Dále se dozvíte o Síto Eratosthenova algoritmu