Reisiva müügimehe probleem: Python, C++ Algoritm
Sarah Chen
Mis on reisiva müügimehe probleem (TSP)?
Travelling Salesman Problem (TSP) on teoreetilise arvutiteaduse klassikaline kombinatoorika probleem. Ülesanne palub leida graafikul lühim tee tingimusega, et külastada kõiki sõlme ainult üks kord ja naasta lähtelinna.
Probleemi püstitus annab linnade loendi koos iga linna vaheliste kaugustega.
Eesmärk: Lähtelinnast alustamiseks külastage teisi linnu ainult üks kord ja naaske uuesti algsesse linna. Meie eesmärk on leida edasi-tagasi marsruudi läbimiseks võimalikult lühike tee.
TSP näide
Siin on antud graafik, kus 1, 2, 3 ja 4 tähistavad linnu ning iga servaga seotud kaal tähistab nende linnade vahelist kaugust.
Eesmärk on leida ringkäigu jaoks lühim võimalik tee, mis algab lähtelinnast, läbib graafiku, külastades samal ajal teisi linnu või sõlmpunkte ainult ühe korra ja jõuab tagasi lähtelinna.
Ülaltoodud graafiku jaoks on optimaalne marsruut järgida minimaalset kuluteed: 1-2-4-3-1. Ja see lühim tee maksaks 10+25+30+15 =80
Erinevad lahendused reisiva müügimehe probleemile
Reisiva müügimehe probleem (TSP) on klassifitseeritud NP-raskete probleemide hulka, kuna sellel pole polünoomilise aja algoritmi. Keerulisus suureneb plahvatuslikult, suurendades linnade arvu.
Reisiva müügimehe probleemi (tsp) lahendamiseks on mitu võimalust. Mõned populaarsed lahendused on järgmised:
Toorest jõust lähtuv lähenemine on naiivne meetod rändmüüja probleemide lahendamiseks. Selle lähenemisviisi puhul arvutame esmalt kõik võimalikud teed ja seejärel võrdleme neid. N linnast koosneva graafiku radade arv on n! Rändmüüja probleemi lahendamine sellise jõhkra jõu meetodiga on arvutuslikult väga kallis.
Harutatud ja seotud meetod: Selle lähenemisviisi puhul on probleem jaotatud alamprobleemideks. Nende üksikute alamprobleemide lahendamine annaks optimaalse lahenduse.
See õpetus tutvustab dünaamilise programmeerimise lähenemisviisi, selle hargneva ja seotud meetodi rekursiivset versiooni, et lahendada reisiva müügimehe probleem.
Dünaamiline programmeerimine on selline meetod optimaalsete lahenduste otsimiseks, analüüsides kõiki võimalikke marsruute. See on üks täpseid lahendusmeetodeid, mis lahendavad reisiva müügimehe probleemid suhteliselt kõrgemate kuludega kui ahned meetodid mis pakuvad peaaegu optimaalset lahendust.
Selle lähenemisviisi arvutuslik keerukus on O(N^2 * 2^N) mida arutatakse käesolevas artiklis hiljem.
Lähima naabri meetod on heuristiline ahne lähenemine, kus valime lähima naabersõlme. See lähenemisviis on arvutuslikult odavam kui dünaamiline lähenemine. Kuid see ei taga optimaalset lahendust. Seda meetodit kasutatakse peaaegu optimaalsete lahenduste jaoks.
Algoritm reisiva müügimehe probleemi lahendamiseks
Kasutame reisiva müügimehe probleemi (TSP) lahendamiseks dünaamilise programmeerimise lähenemisviisi.
Enne algoritmi käivitamist tutvume mõne terminoloogiaga:
- Graaf G=(V, E), mis on tippude ja servade hulk.
- V on tippude hulk.
- E on servade hulk.
- Tipud on ühendatud servade kaudu.
- Dist(i,j) tähistab mittenegatiivset kaugust kahe tipu, i ja j, vahel.
Oletame, et S on linnade alamhulk ja kuulub hulka {1, 2, 3, …, n}, kus 1, 2, 3…n on linnad ja i, j on selle alamhulga kaks linna. Nüüd on kulu(i, S, j) defineeritud nii, et S-i lühima teekonda külastava sõlme pikkus on täpselt üks kord, mille algus- ja lõpp-punkt on vastavalt i ja j.
Näiteks kulu (1, {2, 3, 4}, 1) tähistab lühima tee pikkust, kus:
- Alguslinn on 1
- Linnasid 2, 3 ja 4 külastatakse ainult üks kord
- Lõpppunkt on 1
Dünaamilise programmeerimise algoritm oleks järgmine:
- Määra maksumus (i, , i) = 0, mis tähendab, et me alustame ja lõpetame punktiga i ning maksumus on 0.
- Millal |S| > 1, defineerime kulu(i, S, 1) = ∝ kus i !=1 . Sest esialgu me ei tea täpset maksumust, et jõuda linna i linna 1 läbi teiste linnade.
- Nüüd peame alustama kell 1 ja lõpetama ringkäigu. Peame valima järgmise linna nii-
kulu(i, S, j)=min kulu (i, S−{i}, j)+dist(i,j) kus i∈S ja i≠j
Antud joonise puhul oleks naabrusmaatriks järgmine:
| 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 |
Vaatame, kuidas meie algoritm töötab:
Step 1) Kaalume oma reisi algust linnast 1, külastame korra teisi linnu ja naaseme linna 1.
Step 2) S on linnade alamhulk. Meie algoritmi järgi kõigi |S| jaoks > 1, määrame vahemaa maksumuse(i, S, 1) = ∝. Siin cost(i, S, j) tähendab, et alustame linnast i, külastame korra S linnu ja nüüd oleme linnas j. Selle teekulu määrasime lõpmatuseks, kuna me ei tea veel kaugust. Seega on väärtused järgmised:
Maksumus (2, {3, 4}, 1) = ∝ ; tähistus näitab, et alustame linnast 2, läbime linnad 3, 4 ja jõuame 1-ni. Ja tee maksumus on lõpmatus. Samamoodi-
maksumus(3, {2, 4}, 1) = ∝
maksumus(4, {2, 3}, 1) = ∝
Step 3) Nüüd peame kõigi S alamhulkade jaoks leidma järgmise:
kulu(i, S, j)=min kulu (i, S−{i}, j)+dist(i,j), kus j∈S ja i≠j
See tähendab minimaalset kuluteekonda, kui alustada i-st, läbida üks kord linnade alamhulk ja naasta linna j. Arvestades, et teekond algab linnast 1, oleks optimaalne teekulu = kulu(1, {teised linnad}, 1).
Uurime välja, kuidas saaksime seda saavutada:
Nüüd S = {1, 2, 3, 4}. Seal on neli elementi. Seega on alamhulkade arv 2^4 või 16. Need alamhulgad on-
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}}
Kuna alustame 1.-st, võiksime linna 1 sisaldavad alamhulgad ära jätta.
Algoritmi arvutamine:
1) |S| = Φ:
maksumus (2, Φ, 1) = dist(2, 1) = 10
maksumus (3, Φ, 1) = dist(3, 1) = 15
maksumus (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
maksumus (2, {3}, 1) = dist(2, 3) + kulu (3, Φ, 1) = 35+15 = 50
maksumus (2, {4}, 1) = dist(2, 4) + kulu (4, Φ, 1) = 25+20 = 45
maksumus (3, {2}, 1) = dist(3, 2) + kulu (2, Φ, 1) = 35+10 = 45
maksumus (3, {4}, 1) = dist(3, 4) + kulu (4, Φ, 1) = 30+20 = 50
maksumus (4, {2}, 1) = dist(4, 2) + kulu (2, Φ, 1) = 25+10 = 35
maksumus (4, {3}, 1) = dist(4, 3) + kulu (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
maksumus (2, {3, 4}, 1) = min [ dist[2,3]+Kulu (3,{4},1) = 35 + 50 = 85,
dist[2,4]+Kulu(4,{3},1) = 25+45 = 70] = 70
kulu (3, {2, 4}, 1) = min [ dist[3,2]+Kulu(2,{4},1) = 35+45 = 80,
dist[3,4]+Kulu(4,{2},1) = 30+35 = 65] = 65
kulu (4, {2, 3}, 1) = min [ dist[4,2]+Kulu(2,{3},1) = 25+50 = 75
dist[4,3]+Kulu(3,{2},1) = 30+45 = 75] = 75
4) |S| = 3:
maksumus (1, {2, 3, 4}, 1) = min [ dist[1,2]+Kulu (2, {3,4},1) = 10+70 = 80
dist[1,3]+Kulu(3,{2,4},1) = 15+65 = 80
dist[1,4]+Kulu(4,{2,3},1) = 20+75 = 95] = 80
Nii et optimaalne lahendus oleks 1-2-4-3-1
Pseudokood
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)
Rakendamine C/C++
Siin on rakendamine 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äljund:
80
Rakendamine sisse 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äljund:
80
Akadeemilised lahendused TSP-le
Arvutiteadlased on aastaid otsinud täiustatud polünoomilise aja algoritmi reisiva müügimehe probleemi jaoks. Siiani on probleem endiselt NP-raske.
Kuigi viimastel aastatel on avaldatud mõned järgmistest lahendustest, mis on keerukust teatud määral vähendanud:
- Klassikaline sümmeetriline TSP lahendatakse nullsufiksi meetodil.
- Biogeograafial põhinev optimeerimisalgoritm põhineb migratsioonistrateegial, et lahendada optimeerimisprobleeme, mida saab planeerida TSP-na.
- Multi-Objective Evolutionary Algorithm on loodud mitme TSP lahendamiseks NSGA-II baasil.
- Multi-Agent System lahendab N linna TSP püsiressurssidega.
Reisiva müügimehe probleemi rakendamine
Reisiva müügimehe probleemi (TSP) rakendatakse reaalses maailmas nii puhtal kui ka muudetud kujul. Mõned neist on:
- Mikrokiipide planeerimine, logistika ja tootmine: Mikrokiibitööstuses tekivad loomulikult probleemid kiibi sisestamisega. Neid probleeme saab planeerida reisiva müügimehe probleemidena.
- DNA sekveneerimise: DNA sekveneerimisel saab kasutada reisiva müügimehe probleemi kerget muutmist. Siin tähistavad linnad DNA fragmente ja kaugus tähistab kahe DNA fragmendi sarnasust.
- Astronoomia: Astronoomid rakendavad rändkaupmehe probleemi, et minimeerida erinevate allikate vaatlemisele kuluvat aega.
- Optimaalse kontrolli probleem: Rändav müügimees Probleemi sõnastust saab rakendada optimaalsete kontrolliprobleemide korral. Lisatud võib olla mitmeid muid piiranguid.
TSP keerukuse analüüs
- Aja keerukus: Neid on kokku 2N alamprobleemid iga sõlme jaoks. Seega oleks alamülesannete koguarv N*2N. Iga alamprobleemi lahendamiseks on vaja lineaarset aega. Kui lähtesõlme pole määratud, peame käivitama silmuseid N sõlme jaoks.
Seega oleks optimaalse lahenduse koguajaline keerukus sõlmede arv * alamprobleemide arv * iga alamprobleemi lahendamise aeg. Ajalist keerukust saab määratleda kui O(N2 * 2^N).
- Ruumi keerukus: Dünaamilise programmeerimise lähenemisviis kasutab C(S, i) salvestamiseks mälu, kus S on tippude komplekti alamhulk. Kokku on 2N iga sõlme alamhulgad. Seega on ruumi keerukus O(2^N).
Järgmisena saate teada Eratosthenese algoritmi sõel
