Travelling Salesman -ongelma: Python, C++ algoritmi
Sarah Chen
Mikä on Travelling Salesman -ongelma (TSP)?
Travelling Salesman Problem (TSP) on teoreettisen tietojenkäsittelytieteen klassinen kombinatorinen ongelma. Tehtävä pyytää löytämään lyhimmän polun kaaviosta, jossa ehdolla käydään kaikissa solmuissa vain kerran ja palataan lähtökaupunkiin.
Ongelmanselvitys antaa luettelon kaupungeista ja kunkin kaupungin väliset etäisyydet.
Tavoite: Aloita lähtökaupungista vierailemalla muissa kaupungeissa vain kerran ja palaamalla takaisin alkuperäiseen kaupunkiin. Tavoitteemme on löytää lyhin mahdollinen reitti edestakaisen reitin suorittamiseen.
Esimerkki TSP:stä
Tässä esitetään kaavio, jossa 1, 2, 3 ja 4 edustavat kaupunkeja ja jokaiseen reunaan liittyvä paino edustaa näiden kaupunkien välistä etäisyyttä.
Tavoitteena on löytää kiertueelle lyhin mahdollinen polku, joka alkaa lähtökaupungista, kulkee kaavion läpi samalla kun käy muissa kaupungeissa tai solmukohdissa vain kerran ja palaa lähtökaupunkiin.
Yllä olevalle kaaviolle optimaalinen reitti on seurata vähimmäiskustannuspolkua: 1-2-4-3-1. Ja tämä lyhin reitti maksaisi 10+25+30+15 =80
Erilaisia ratkaisuja matkustavan myyjän ongelmaan
Travelling Salesman Problem (TSP) on luokiteltu NP-kovaksi ongelmaksi, koska sillä ei ole polynomiaikaalgoritmia. Monimutkaisuus kasvaa eksponentiaalisesti lisäämällä kaupunkien määrää.
On olemassa useita tapoja ratkaista matkustava myyjä -ongelma (tsp). Joitakin suosittuja ratkaisuja ovat:
Raaka voima lähestymistapa on naiivi menetelmä matkamyyjien ongelmien ratkaisemiseen. Tässä lähestymistavassa laskemme ensin kaikki mahdolliset polut ja sitten vertaamme niitä. Polkujen määrä kaaviossa, joka koostuu n kaupungista, on n! On laskennallisesti erittäin kallista ratkaista matkustava myyjä -ongelma tällä raakavoimalla.
Haara ja sidottu menetelmä: Tässä lähestymistavassa ongelma on jaettu osaongelmiin. Näiden yksittäisten osaongelmien ratkaisu tarjoaisi optimaalisen ratkaisun.
Tämä opetusohjelma esittelee dynaamista ohjelmointitapaa, tämän haarautuneen ja sidotun menetelmän rekursiivisen version, joka ratkaisee matkustavan myyjän ongelman.
Dynaaminen ohjelmointi on tällainen menetelmä optimaalisten ratkaisujen etsimiseen analysoimalla kaikki mahdolliset reitit. Se on yksi täsmällisistä ratkaisumenetelmistä, joka ratkaisee matkustavien myyntimiesten ongelmia suhteellisen korkeammalla hinnalla kuin ahneita menetelmiä jotka tarjoavat lähes optimaalisen ratkaisun.
Tämän lähestymistavan laskennallinen monimutkaisuus on O(N^2 * 2^N) jota käsitellään myöhemmin tässä artikkelissa.
Lähin naapuri menetelmä on heuristinen ahne lähestymistapa, jossa valitsemme lähimmän naapurisolmun. Tämä lähestymistapa on laskennallisesti halvempi kuin dynaaminen lähestymistapa. Mutta se ei takaa optimaalista ratkaisua. Tätä menetelmää käytetään lähes optimaalisiin ratkaisuihin.
Algoritmi matkustavan myyjän ongelmalle
Käytämme dynaamisen ohjelmoinnin lähestymistapaa Traveling Salesman -ongelman (TSP) ratkaisemiseen.
Ennen kuin aloitat algoritmin, tutustutaan joihinkin terminologioihin:
- Graafi G=(V, E), joka on joukko pisteitä ja kulmia.
- V on pisteiden joukko.
- E on reunojen joukko.
- Vertices yhdistetään reunojen kautta.
- Dist(i,j) tarkoittaa ei-negatiivista etäisyyttä kahden kärjen, i ja j, välillä.
Oletetaan, että S on kaupunkien osajoukko ja kuuluu joukkoon {1, 2, 3, …, n}, missä 1, 2, 3…n ovat kaupungit ja i, j ovat kaksi kaupunkia kyseisessä osajoukossa. Nyt kustannus(i, S, j) määritellään siten, että S:n lyhimmän polun vierailevan solmun pituus on täsmälleen kerran, jonka aloitus- ja lopetuspisteet ovat vastaavasti i ja j.
Esimerkiksi hinta (1, {2, 3, 4}, 1) tarkoittaa lyhimmän polun pituutta, jossa:
- Aloituskaupunki on 1
- Kaupungeissa 2, 3 ja 4 käydään vain kerran
- Loppupiste on 1
Dynaaminen ohjelmointialgoritmi olisi:
- Aseta kustannus(i, , i) = 0, mikä tarkoittaa, että aloitamme ja lopetamme pisteeseen i, ja kustannus on 0.
- Kun |S| > 1, määritämme kustannus(i, S, 1) = ∝ missä i !=1 . Koska aluksi emme tiedä tarkkaa hintaa päästä kaupunkiin i kaupunkiin 1 muiden kaupunkien kautta.
- Nyt meidän on aloitettava kello 1 ja suoritettava kiertue. Meidän on valittava seuraava kaupunki sillä tavalla-
kustannus(i, S, j)=min hinta (i, S−{i}, j)+dist(i,j) missä i∈S ja i≠j
Annetun kuvion viereisyysmatriisi olisi seuraava:
| 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 |
Katsotaanpa, miten algoritmimme toimii:
Vaihe 1) Harkitsemme matkaamme alkaen kaupungista 1, vierailemme kerran muissa kaupungeissa ja palaamme kaupunkiin 1.
Vaihe 2) S on kaupunkien osajoukko. Algoritmimme mukaan kaikille |S| > 1, asetetaan etäisyyskustannus(i, S, 1) = ∝. Tässä cost(i, S, j) tarkoittaa, että aloitamme kaupungista i, vierailemme S:n kaupungeissa kerran ja nyt olemme kaupungissa j. Asetamme tämän polun hinnaksi äärettömäksi, koska emme vielä tiedä etäisyyttä. Arvot ovat siis seuraavat:
Kustannus (2, {3, 4}, 1) = ∝ ; merkintä tarkoittaa, että aloitamme kaupungista 2, kuljemme kaupunkien 3, 4 läpi ja saavutamme 1. Ja polun hinta on ääretön. Samalla lailla-
kustannus(3, {2, 4}, 1) = ∝
kustannus(4, {2, 3}, 1) = ∝
Vaihe 3) Nyt kaikille S:n osajoukoille meidän on löydettävä seuraava:
kustannus(i, S, j)=min kustannus (i, S−{i}, j)+dist(i,j), missä j∈S ja i≠j
Tämä tarkoittaa vähimmäiskustannuspolkua alkaen kohdasta i, käymällä läpi kaupunkien osajoukko kerran ja palaamalla kaupunkiin j. Ottaen huomioon, että matka alkaa kaupungista 1, optimaalinen polkuhinta olisi = hinta(1, {muut kaupungit}, 1).
Selvitetään, kuinka voimme saavuttaa sen:
Nyt S = {1, 2, 3, 4}. Siinä on neljä elementtiä. Näin ollen osajoukkojen määrä on 2^4 tai 16. Nämä osajoukot ovat
1) |S| = Nolla:
{Φ}
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}}
Koska aloitamme kohdasta 1, voimme hylätä kaupungin 1 sisältävät osajoukot.
Algoritmin laskenta:
1) |S| = Φ:
hinta (2, Φ, 1) = dist(2, 1) = 10
hinta (3, Φ, 1) = dist(3, 1) = 15
hinta (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
hinta (2, {3}, 1) = dist(2, 3) + hinta (3, Φ, 1) = 35+15 = 50
hinta (2, {4}, 1) = dist(2, 4) + hinta (4, Φ, 1) = 25+20 = 45
hinta (3, {2}, 1) = dist(3, 2) + hinta (2, Φ, 1) = 35+10 = 45
hinta (3, {4}, 1) = dist(3, 4) + hinta (4, Φ, 1) = 30+20 = 50
hinta (4, {2}, 1) = dist(4, 2) + hinta (2, Φ, 1) = 25+10 = 35
hinta (4, {3}, 1) = dist(4, 3) + hinta (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
hinta (2, {3, 4}, 1) = min [ dist[2,3]+kustannus(3,{4},1) = 35+50 = 85,
jaka[2,4]+kustannus(4,{3},1) = 25+45 = 70 ] = 70
hinta (3, {2, 4}, 1) = min [ dist[3,2]+kustannus(2,{4},1) = 35+45 = 80,
jaka[3,4]+kustannus(4,{2},1) = 30+35 = 65 ] = 65
hinta (4, {2, 3}, 1) = min [ dist[4,2]+kustannus(2,{3},1) = 25+50 = 75
jaka[4,3]+kustannus(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
hinta (1, {2, 3, 4}, 1) = min [ dist[1,2]+kustannus(2,{3,4},1) = 10+70 = 80
jaka[1,3]+kustannus(3,{2,4},1) = 15+65 = 80
jaka[1,4]+kustannus(4,{2,3},1) = 20+75 = 95 ] = 80
Optimaalinen ratkaisu olisi siis 1-2-4-3-1
Pseudokoodi
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)
Toteutus C/C++
Tässä toteutus 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;
}
lähtö:
80
Toteutus sisää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))
lähtö:
80
Akateemiset ratkaisut TSP:lle
Tietojenkäsittelytieteilijät ovat käyttäneet vuosia etsiessään parannettua polynomiaikaalgoritmia Travelling Salesman -ongelmaan. Toistaiseksi ongelma on edelleen NP-kova.
Vaikka viime vuosina on julkaistu joitakin seuraavista ratkaisuista, jotka ovat vähentäneet monimutkaisuutta jossain määrin:
- Klassinen symmetrinen TSP ratkaistaan nollaliitemenetelmällä.
- Biogeografiaan perustuva optimointialgoritmi perustuu migraatiostrategiaan, joka ratkaisee optimointiongelmat, jotka voidaan suunnitella TSP:ksi.
- Multi-Objective Evolutionary Algorithm on suunniteltu useiden TSP:iden ratkaisemiseen NSGA-II:n perusteella.
- Multi-Agent System ratkaisee N kaupungin TSP:n kiinteillä resursseilla.
Travelling Salesman -ongelman soveltaminen
Travelling Salesman Problem (TSP) -ongelmaa sovelletaan todellisessa maailmassa sekä puhtaimmissa että muunnetuissa muodoissaan. Jotkut niistä ovat:
- Mikrosirujen suunnittelu, logistiikka ja valmistus: Mikrosiruteollisuudessa esiintyy luonnollisesti sirun kiinnitysongelmia. Nämä ongelmat voidaan suunnitella matkamyyjien ongelmiksi.
- DNA-sekvensointi: Hieman muunneltua matkustava myyjä -ongelmaa voidaan käyttää DNA-sekvensoinnissa. Tässä kaupungit edustavat DNA-fragmentteja, ja etäisyys edustaa kahden DNA-fragmentin välistä samankaltaisuuden mittaa.
- Tähtitiede: Tähtitieteilijät soveltavat Travelling Salesman -ongelmaa minimoimaan eri lähteiden tarkkailuun käytettyä aikaa.
- Optimaalinen ohjausongelma: Travelling Salesman Ongelman muotoilua voidaan soveltaa optimaalisiin ohjausongelmiin. Saattaa olla useita muita rajoituksia lisätty.
TSP:n monimutkaisuusanalyysi
- Ajan monimutkaisuus: Niitä on yhteensä 2N aliongelmat jokaiselle solmulle. Joten aliongelmien kokonaismäärä olisi N*2N. Jokaisen osaongelman ratkaiseminen vaatii lineaarista aikaa. Jos alkuperäsolmua ei ole määritetty, meidän on suoritettava silmukoita N solmulle.
Optimaalisen ratkaisun kokonaisaika monimutkaisuus olisi siis solmujen lukumäärä * aliongelmien lukumäärä * kunkin osaongelman ratkaisemiseen kuluva aika. Aika monimutkaisuus voidaan määritellä muodossa O(N2 * 2^N).
- Avaruuden monimutkaisuus: Dynaaminen ohjelmointitapa käyttää muistia C(S, i) tallentamiseen, missä S on kärkijoukon osajoukko. Niitä on yhteensä 2N alajoukot jokaiselle solmulle. Joten avaruuden kompleksisuus on O(2^N).
Seuraavaksi opit aiheesta Eratosthenes-algoritmin seula
