Travelling Salesman Problem (TSP):
Kun otetaan huomioon joukko kaupunkeja ja jokaisen kaupunkiparin välinen etäisyys, ongelmana on löytää lyhin mahdollinen reitti, joka vierailee jokaisessa kaupungissa täsmälleen kerran ja palaa lähtöpisteeseen. Huomaa ero Hamiltonin syklin ja TSP:n välillä. Hamiltonin pyöräilyongelma on selvittää, onko olemassa kiertomatkaa, joka vierailee jokaisessa kaupungissa tasan kerran. Täällä tiedämme, että Hamiltonin kiertue on olemassa (koska kaavio on valmis) ja itse asiassa, monia tällaisia matkoja on olemassa, ongelmana on löytää vähimmäispainoinen Hamiltonin kierto.
Tarkastellaan esimerkiksi oikeanpuoleisessa kuvassa näkyvää kaaviota. TSP-kierros kaaviossa on 1-2-4-3-1. Retken hinta on 10+25+30+15 eli 80. Ongelma on kuuluisa NP-kova ongelma. Tälle ongelmalle ei ole polynomiaikaista ratkaisua. Seuraavassa on erilaisia ratkaisuja matkustavan myyjän ongelmaan.
Naivi ratkaisu:
1) Pidä kaupunkia 1 aloitus- ja loppupisteenä.
2) Luo kaikki (n-1)! Kaupunkien permutaatiot.
3) Laske jokaisen permutoinnin hinta ja pidä kirjaa vähimmäiskustannuspermutaatiosta.
4) Palauta permutaatio pienin kustannuksin.
Aika monimutkaisuus: ?(n!)
Dynaaminen ohjelmointi:
Olkoon annettu pisteiden joukko {1, 2, 3, 4,….n}. Tarkastellaan 1:tä lähdön aloitus- ja loppupisteenä. Jokaiselle toiselle pisteelle I (muulle kuin 1) löydämme minimikustannuspolun, jossa 1 on aloituspiste, I on loppupiste ja kaikki kärjet esiintyvät täsmälleen kerran. Olkoon tämän polun kustannus (i) ja vastaavan syklin kustannus (i) + dist(i, 1) missä dist(i, 1) on etäisyys I:stä 1:een. Lopuksi palautetaan kaikkien [kustannus(i) + dist(i, 1)]-arvojen minimi. Tämä näyttää toistaiseksi yksinkertaiselta.
Nyt kysymys kuuluu, kuinka saada kustannus(i)? Laskeaksemme kustannus(i) dynaamisen ohjelmoinnin avulla, meillä on oltava jokin rekursiivinen suhde aliongelmien suhteen.
Määritellään termi C(S, i) on vähimmäiskustannuspolun hinta, joka vierailee jokaisessa joukon S kärjessä täsmälleen kerran, alkaen 1:stä ja päättyen kohtaan i . Aloitamme kaikista koon 2 osajoukoista ja laskemme C(S, i) kaikille osajoukoille, joissa S on osajoukko, sitten laskemme C(S, i) kaikille koon 3 alajoukoille S ja niin edelleen. Huomaa, että 1:n on oltava jokaisessa osajoukossa.
If size of S is 2, then S must be {1, i}, C(S, i) = dist(1, i) Else if size of S is greater than 2. C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.> Alla on dynaaminen ohjelmointiratkaisu ongelmaan käyttämällä ylhäältä alas rekursiivista + muistiin tallennettua lähestymistapaa: -
jos muuten jos java
Osajoukkojen ylläpitämiseksi voimme käyttää bitimaskeja edustamaan osajoukkomme jäljellä olevia solmuja. Koska bitit toimivat nopeammin ja graafissa on vain vähän solmuja, bitmaskeja on parempi käyttää.
javafx on eclipse
Esimerkiksi: -
10100 edustaa solmua 2 ja solmu 4 jätetään joukkoon käsiteltäväksi
010010 edustaa solmua 1 ja 4 jätetään osajoukkoon.
HUOMAA: - jätä huomioimatta 0. bitti, koska kaaviomme on 1-pohjainen
C++
#include> using> namespace> std;> // there are four nodes in example graph (graph is 1-based)> const> int> n = 4;> // give appropriate maximum to avoid overflow> const> int> MAX = 1000000;> // dist[i][j] represents shortest distance to go from i to j> // this matrix can be calculated for any given graph using> // all-pair shortest path algorithms> int> dist[n + 1][n + 1] = {> >{ 0, 0, 0, 0, 0 }, { 0, 0, 10, 15, 20 },> >{ 0, 10, 0, 25, 25 }, { 0, 15, 25, 0, 30 },> >{ 0, 20, 25, 30, 0 },> };> // memoization for top down recursion> int> memo[n + 1][1 << (n + 1)];> int> fun(>int> i,>int> mask)> > >// base case> >// if only ith bit and 1st bit is set in our mask,> >// it implies we have visited all other nodes already> >if> (mask == ((1 << i)> // Driver program to test above logic> int> main()> {> >int> ans = MAX;> >for> (>int> i = 1; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = std::min(ans, fun(i, (1 << (n + 1)) - 1)> >+ dist[i][1]);> >printf>(>'The cost of most efficient tour = %d'>, ans);> >return> 0;> }> // This code is contributed by Serjeel Ranjan> |
>
>
Java
import> java.io.*;> import> java.util.*;> public> class> TSE {> >// there are four nodes in example graph (graph is> >// 1-based)> >static> int> n =>4>;> >// give appropriate maximum to avoid overflow> >static> int> MAX =>1000000>;> >// dist[i][j] represents shortest distance to go from i> >// to j this matrix can be calculated for any given> >// graph using all-pair shortest path algorithms> >static> int>[][] dist = {> >{>0>,>0>,>0>,>0>,>0> }, {>0>,>0>,>10>,>15>,>20> },> >{>0>,>10>,>0>,>25>,>25> }, {>0>,>15>,>25>,>0>,>30> },> >{>0>,>20>,>25>,>30>,>0> },> >};> >// memoization for top down recursion> >static> int>[][] memo =>new> int>[n +>1>][>1> << (n +>1>)];> >static> int> fun(>int> i,>int> mask)> >> >// base case> >// if only ith bit and 1st bit is set in our mask,> >// it implies we have visited all other nodes> >// already> >if> (mask == ((>1> << i)> >// Driver program to test above logic> >public> static> void> main(String[] args)> >{> >int> ans = MAX;> >for> (>int> i =>1>; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = Math.min(ans, fun(i, (>1> << (n +>1>)) ->1>)> >+ dist[i][>1>]);> >System.out.println(> >'The cost of most efficient tour = '> + ans);> >}> }> // This code is contributed by Serjeel Ranjan> |
>
>
Python 3
käyttöjärjestelmän käyttötavat
n>=> 4> # there are four nodes in example graph (graph is 1-based)> # dist[i][j] represents shortest distance to go from i to j> # this matrix can be calculated for any given graph using> # all-pair shortest path algorithms> dist>=> [[>0>,>0>,>0>,>0>,>0>], [>0>,>0>,>10>,>15>,>20>], [> >0>,>10>,>0>,>25>,>25>], [>0>,>15>,>25>,>0>,>30>], [>0>,>20>,>25>,>30>,>0>]]> # memoization for top down recursion> memo>=> [[>->1>]>*>(>1> << (n>+>1>))>for> _>in> range>(n>+>1>)]> def> fun(i, mask):> ># base case> ># if only ith bit and 1st bit is set in our mask,> ># it implies we have visited all other nodes already> >if> mask>=>=> ((>1> << i) |>3>):> >return> dist[>1>][i]> ># memoization> >if> memo[i][mask] !>=> ->1>:> >return> memo[i][mask]> >res>=> 10>*>*>9> # result of this sub-problem> ># we have to travel all nodes j in mask and end the path at ith node> ># so for every node j in mask, recursively calculate cost of> ># travelling all nodes in mask> ># except i and then travel back from node j to node i taking> ># the shortest path take the minimum of all possible j nodes> >for> j>in> range>(>1>, n>+>1>):> >if> (mask & (>1> << j)) !>=> 0> and> j !>=> i>and> j !>=> 1>:> >res>=> min>(res, fun(j, mask & (~(>1> << i)))>+> dist[j][i])> >memo[i][mask]>=> res># storing the minimum value> >return> res> # Driver program to test above logic> ans>=> 10>*>*>9> for> i>in> range>(>1>, n>+>1>):> ># try to go from node 1 visiting all nodes in between to i> ># then return from i taking the shortest route to 1> >ans>=> min>(ans, fun(i, (>1> << (n>+>1>))>->1>)>+> dist[i][>1>])> print>(>'The cost of most efficient tour = '> +> str>(ans))> # This code is contributed by Serjeel Ranjan> |
>
ml oz
>
C#
using> System;> class> TSE> {> >// there are four nodes in example graph (graph is> >// 1-based)> >static> int> n = 4;> >// give appropriate maximum to avoid overflow> >static> int> MAX = 1000000;> >// dist[i][j] represents shortest distance to go from i> >// to j this matrix can be calculated for any given> >// graph using all-pair shortest path algorithms> >static> int>[, ] dist = { { 0, 0, 0, 0, 0 },> >{ 0, 0, 10, 15, 20 },> >{ 0, 10, 0, 25, 25 },> >{ 0, 15, 25, 0, 30 },> >{ 0, 20, 25, 30, 0 } };> >// memoization for top down recursion> >static> int>[, ] memo =>new> int>[(n + 1), (1 << (n + 1))];> >static> int> fun(>int> i,>int> mask)> > 3))> >return> dist[1, i];> > >// memoization> >if> (memo[i, mask] != 0)> >return> memo[i, mask];> >int> res = MAX;>// result of this sub-problem> >// we have to travel all nodes j in mask and end the> >// path at ith node so for every node j in mask,> >// recursively calculate cost of travelling all> >// nodes in mask> >// except i and then travel back from node j to node> >// i taking the shortest path take the minimum of> >// all possible j nodes> >for> (>int> j = 1; j <= n; j++)> >if> ((mask & (1 << j)) != 0 && j != i && j != 1)> >res = Math.Min(res,> >fun(j, mask & (~(1 << i)))> >+ dist[j, i]);> >return> memo[i, mask] = res;> >> >// Driver program to test above logic> >public> static> void> Main()> >{> >int> ans = MAX;> >for> (>int> i = 1; i <= n; i++)> >// try to go from node 1 visiting all nodes in> >// between to i then return from i taking the> >// shortest route to 1> >ans = Math.Min(ans, fun(i, (1 << (n + 1)) - 1)> >+ dist[i, 1]);> >Console.WriteLine(> >'The cost of most efficient tour = '> + ans);> >}> }> // This code is contributed by Tapesh(tapeshdua420)> |
>
>
Javascript
vijay-elokuvanäyttelijä
>// JavaScript code for the above approach> >// there are four nodes in example graph (graph is 1-based)> >let n = 4;> > >// give appropriate maximum to avoid overflow> >let MAX = 1000000;> >// dist[i][j] represents shortest distance to go from i to j> >// this matrix can be calculated for any given graph using> >// all-pair shortest path algorithms> >let dist = [> >[0, 0, 0, 0, 0], [0, 0, 10, 15, 20],> >[0, 10, 0, 25, 25], [0, 15, 25, 0, 30],> >[0, 20, 25, 30, 0],> >];> >// memoization for top down recursion> >let memo =>new> Array(n + 1);> >for> (let i = 0; i memo[i] = new Array(1 << (n + 1)).fill(0) } function fun(i, mask) // base case // if only ith bit and 1st bit is set in our mask, // it implies we have visited all other nodes already if (mask == ((1 << i) // Driver program to test above logic let ans = MAX; for (let i = 1; i <= n; i++) // try to go from node 1 visiting all nodes in // between to i then return from i taking the // shortest route to 1 ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1) + dist[i][1]); console.log('The cost of most efficient tour ' + ans); // This code is contributed by Potta Lokesh> |
>
>Lähtö
The cost of most efficient tour = 80>
Aika monimutkaisuus: O(n2*2n) missä O(n*2n)ovat yksilöllisten aliongelmien/tilojen enimmäismäärä ja O(n) siirtymälle (silmukan kautta kuten koodissa) jokaisessa tilassa.
Aputila: O(n*2n), missä n on solmujen/kaupunkien lukumäärä tässä.
Joukkoon, jonka koko on n, otetaan huomioon n-2 osajoukkoa, joista jokainen on kooltaan n-1 siten, että kaikissa osajoukoissa ei ole n:nnettä. Yllä olevaa toistuvuusrelaatiota käyttämällä voimme kirjoittaa dynaamisen ohjelmointipohjaisen ratkaisun. Niitä on enintään O(n*2n) osaongelmia, ja jokaisen ratkaiseminen vie lineaarista aikaa. Kokonaiskäyttöaika on siis O(n2*2n). Aika monimutkaisuus on paljon pienempi kuin O(n!), mutta silti eksponentiaalinen. Tarvittava tila on myös eksponentiaalinen. Joten tämä lähestymistapa on myös mahdoton edes hieman suuremmalla määrällä huippuja. Keskustelemme pian likimääräisistä algoritmeista matkustavan myyjän ongelmaan.
Seuraava artikkeli: Travelling Salesman Problem | Sarja 2
Viitteet:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf