Held–Karp-algoritm

Held –Karp-algoritmen , även kallad Bellman–Held–Karp-algoritmen , är en dynamisk programmeringsalgoritm som 1962 föreslogs oberoende av Bellman och av Held och Karp för att lösa resandesäljarproblemet (TSP), där indata är en avståndsmatris mellan en uppsättning städer, och målet är att hitta en rundtur med minsta längd som besöker varje stad exakt en gång innan du återvänder till startpunkten. Den hittar den exakta lösningen på detta problem, och till flera relaterade problem, inklusive Hamiltons cykelproblem, i exponentiell tid .

Algoritmbeskrivning och motivation

Numrera städerna $1,2,\ldots ,n$ , med $1$ godtyckligt betecknad som en "startstad" (eftersom lösningen på TSP är en cykel, är valet startstad spelar ingen roll). Held–Karp-algoritmen börjar med att beräkna, för varje uppsättning städer $S\subseteq \{2,\ldots ,n\}$ och varje stad $e \neq 1$ ingår inte i $S$ , den kortaste enkelriktade vägen från $1$ till $e$ som passerar genom varje stad i $S$ i någon ordning ( men inte genom några andra städer). Beteckna detta avstånd $g(S,e)$ , och skriv $d(u,v)$ för längden på den direkta kanten från $u$ till $v$ . Vi kommer att beräkna värden på $g(S,e)$ med början med de minsta uppsättningarna $S$ och avslutar med den största.

När $S$ har två eller färre element kräver beräkningen av $g(S,e)$ att man tittar på en eller två möjliga kortaste vägar. Till exempel $g(\emptyset ,e)$ helt enkelt $d(1,e)$ och ${\ displaystyle g(\{2\},3)}$ är bara längden på $1\rightarrow 2\rightarrow 3$ . Likaså är $g(\{2,3\},4)$ längden på antingen $1\rightarrow 2\rightarrow 3 \rightarrow 4$ eller ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4} , beroende på$ vilket som är kortast.

När $S$ innehåller tre eller fler städer, ökar antalet vägar genom $S$ snabbt, men endast ett fåtal sådana vägar behöver undersökas för att hitta den kortaste. Till exempel, om $1\rightarrow 2\rightarrow 3\rightarrow 4$ är kortare än $1\rightarrow 3\rightarrow 2\rightarrow 4$ , sedan $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ måste vara kortare än $1\rightarrow 3\rightarrow 2 \rightarrow 4\rightarrow 5$ och längden på $1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5$ är inte ett möjligt värde på $g(\{2,3,4\},5)$ . På liknande sätt, om den kortaste vägen från $1$ till $\{2,3,4\}$ till $5$ är $1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5$ och den kortaste vägen från $1$ till $\{2,3,4 ,5\}$ till $6$ slutar med kanten $5\rightarrow 6$ , då måste hela vägen från $1$ till $6$ vara ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 6} ,$ och inte någon av de andra fem sökvägarna som skapats genom att besöka ${\ displaystyle \{2,3,4\}}$ i en annan ordning.

Mer generellt, anta att $S=\{s_{1},\ldots ,s_{k}\}$ är en uppsättning $k$ städer. För varje heltal $1\leq i\leq k$ , skriv $S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_ {k}\}$ för uppsättningen som skapats genom att ta bort $s_{i}$ från $S$ . Om den kortaste vägen från $1$ till $S$ till $e$ har $s_{i}$ som sin näst sista stad, tas den slutliga bort kanten från denna väg måste ge den kortaste vägen från $1$ till $s_{i}$ genom $S_{i}$ . Detta innebär att det bara finns $k$ möjliga kortaste vägar från $1$ till $e$ till $S$ , en för varje möjlig näst sista stad ${\ displaystyle s_{i}}$ med längden ${\displaystyle g(S_{i},s_{i})+d(s_{i},e)$ och ${\displaystyle g(S,e)=\min _{1\leq$ .

Detta steg i algoritmen avslutas när $g(\{2,\ldots ,i-1,i+1,\ ldots ,n\},i)$ är känt för varje heltal $2\leq i\leq n$ , vilket ger det kortaste avståndet från stad $1$ till stad $i$ som passerar genom varannan stad. Det mycket kortare andra steget adderar dessa avstånd till kantlängderna $d(i,1)$ för att ge $n-1$ möjliga kortaste cykler, och hittar sedan den kortaste.

Den kortaste vägen i sig (och inte bara dess längd) kan slutligen rekonstrueras genom att lagra bredvid $g(S,e)$ etiketten för den näst sista staden på vägen från $1$ till $e$ till $S$ , vilket höjer utrymmeskraven med endast en konstant faktor.

Algoritmisk komplexitet

Held–Karp-algoritmen har exponentiell tidskomplexitet $\Theta (2^{n}n^{2})$ , betydligt bättre än den superexponentiella prestandan $\ Theta (n!)$ av en brute-force-algoritm. Held–Karp kräver dock $\Theta (n2^{n})$ utrymme för att hålla alla beräknade värden för funktionen $g(S,e)$ , medan brute force bara behöver $\Theta (n^{2})$ utrymme för att lagra själva grafen.

Tid

Beräknar ett värde av $g(S,e)$ för en $k$ -elementdelmängd $S$ av $\{ 2,\ldots ,n\}$ kräver att man hittar den kortaste av $k$ möjliga vägar, var och en hittas genom att lägga till ett känt värde på $g$ och en kantlängd från den ursprungliga grafen; det vill säga det kräver tid proportionell mot $k$ . Det finns ${\textstyle {\binom {n-1}{k}}}$ $k$ -elementdelmängder av $\{2,\ldots ,n\}$ ; och varje delmängd ger $nk-1$ möjliga värden för $e$ . Beräknar alla värden på $g(S,e)$ där $|S|=k$ kräver alltså tid ${\textstyle k(nk-1){\binom {n-1}{k}}=(n-1)(n-2){\binom {n-3}{k-1}}} , för en total tid$ över alla delmängder storlekar ${\textstil (n-1)(n-2)\summa _{k=1}^{n-2}{\binom {n-3}{k-1}}=(n-1)(n -2)2^{n-3}=\Theta (n^{2}2^{n})}$ . Det andra steget av algoritmen, att hitta en komplett cykel från $n-1$ kandidater, tar $\Theta (n)$ tid och påverkar inte asymptotisk prestanda.

För oriktade grafer kan algoritmen stoppas tidigt efter steget ${\textstyle k=\lfloor {\frac {n-1}{2}}\rfloor }$ och hitta det lägsta ${\textstil g(S,e)+g(S^{c}\setminus \{1,e\},e)}$ för varje ${\textstil \{(S,e):|S|=\lgolv {\frac {n-1}{2}}\rgolv ,e \in S^{c}\setminus \{1\}\}}$ , där ${\textstyle S^{c}}$ är komplementmängden av ${\textstyle S}$ . Detta är analogt med en dubbelriktad sökning som börjar vid ${\textstyle 1}$ och möter mittpunkten ${\textstyle e}$ . Detta är dock en konstant faktorförbättring och påverkar inte den asymptotiska prestandan.

Plats

Lagring av alla värden för $g(S,e)$ ${\textstyle (nk-1){\binom {n-1}{k}}=(n-1){\binom {n-2}{k}}} värden$ delmängder av storleken $k$ kräver att man behåller . En komplett värdetabell för $g(S,e)$ kräver alltså mellanslag ${\textstyle \sum _{k=0}^{n-2}(n-1){\binom {n-2}{k}}=(n-1)2^{ n}=\Theta (n2^{n})}$ . Detta förutsätter att ${\textstyle n}$ är tillräckligt liten så att ${\textstyle S}$ kan lagras som en bitmask av konstant multipel av maskinord snarare än en explicit k-tupel.

Om bara längden på den kortaste cykeln behövs, inte själva cykeln, så kan rymdkomplexiteten förbättras något genom att notera att man beräknar $g(S,e)$ för en $S$ av storlek $k$ kräver endast värden på $g$ för delmängder av storlek $k-1$ . Behåller endast ${\textstyle (n-1)\left[{\binom {n-2}{k-1}} +{\binom {n-2}{k}}\right]}$ värden för $g(S,e)$ där $S$ har storlek antingen ${\ displaystyle k-1}$ eller $k$ minskar algoritmens maximala utrymmeskrav, som uppnås när ${\textstyle k=\left\lfloor {\frac {n}{2}}\right\rfloor }$ , till $\Theta ({\sqrt {n}}2^{n})$ .

Exempel

Avståndsmatris:

C={\begin{pmatrix}0&2&9&10\\1&0&6&4\\15&7&0&8\\6&3&12&0\end{pmatrix}}

Funktionsbeskrivning:

g(x, S) - från 1 slutar min kostnad för banor vid toppunkt x, passerar hörn i mängd S exakt en gång
c _xy - kantkostnaden slutar på x från y
p(x, S) - det näst sista hörnet till x från mängden S. Används för att konstruera TSP-vägen tillbaka i slutet.

k = 0, nolluppsättning:

Ställ in ∅:

 g(2, ∅) = c ₂₁ = 1 g(3, ∅) = c ₃₁ = 15 g(4, ∅) = c ₄₁ = 6

k = 1, betrakta mängder av 1 element:

Ställ in {2}:

 g(3,{2}) = c ₃₂ + g(2, ∅ ) = c ₃₂ + c ₂₁ = 7 + 1 = 8 p(3,{2}) = 2 g(4,{2}) = c ₄₂ + g(2, ∅ ) = c ₄₂ + c ₂₁ = 3 + 1 = 4 p(4,{2}) = 2

Ställ in {3}:

 g(2,{3}) = c ₂₃ + g(3, ∅ ) = c ₂₃ + c ₃₁ = 6 + 15 = 21 p(2,{3}) = 3 g(4,{3}) = c ₄₃ + g(3, ∅ ) = c ₄₃ + c ₃₁ = 12 + 15 = 27 p(4,{3}) = 3

Ställ in {4}:

 g(2,{4}) = c ₂₄ + g(4, ∅ ) = c ₂₄ + c ₄₁ = 4 + 6 = 10 p(2,{4}) = 4 g(3,{4}) = c ₃₄ + g(4, ∅ ) = c ₃₄ + c ₄₁ = 8 + 6 = 14 p(3,{4}) = 4

k = 2, betrakta uppsättningar av 2 element:

Ställ in {2,3}:

 g(4,{2,3}) = min {c ₄₂ + g(2,{3}), c ₄₃ + g(3,{2})} = min {3+21, 12+8}= min {24, 20}= 20 p(4,{2,3}) = 3

Ställ in {2,4}:

 g(3,{2,4}) = min {c ₃₂ + g(2,{4}), c ₃₄ + g(4,{2})} = min {7+10, 8+4}= min {17, 12} = 12 p(3,{2,4}) = 4

Ställ in {3,4}:

 g(2,{3,4}) = min {c ₂₃ + g(3,{4}), c ₂₄ + g(4,{3})} = min {6+14, 4+27}= min {20, 31}= 20 p(2,{3,4}) = 3

Längd på en optimal tur:

 f = g(1,{2,3,4}) = min { c ₁₂ + g(2,{3,4}), c ₁₃ + g(3,{2,4}), c ₁₄ + g( 4,{2,3}) } = min {2 + 20, 9 + 12, 10 + 20} = min {22, 21, 30} = 21

Föregångare till nod 1: p(1,{2,3,4}) = 3

Föregångare till nod 3: p(3, {2,4}) = 4

Föregångare till nod 4: p(4, {2}) = 2

Föregångare till nod 2: p(2, {}) = 1

Därför ges en optimal TSP-tur av 1 → 2→ 4 → 3→ 1.

Pseudokod

    

    
        
            
        
     funktionsalgoritm  TSP (G, n)  är  för  k := 2 till n  do  g({k}, k) := d(1, k)  slut för  för  s := 2  till  n−1  gör  för alla  S ⊆ { 2, ..., n}, |S| = s   gör  för alla  k ∈ S  gör  g(S, k) := min _m≠k,m∈S [g(S\{k}, m) + d(m, k)]  slut för  ände för  slut för  opt := min _k≠1 [g({2, 3, ..., n}, k) + d(k, 1)]  returnera  (opt)  slutfunktion

Relaterade algoritmer

Exakta algoritmer för att lösa TSP

Förutom dynamisk programmering, linjär programmering och Branch and bound är designmönster som också används för exakta lösningar till TSP. Linjär programmering tillämpar skärplansmetoden i heltalsprogrammering , dvs löser LP som bildas av två begränsningar i modellen och söker sedan skärplanet genom att lägga till olikhetsbegränsningar för att gradvis konvergera till en optimal lösning. När människor tillämpar denna metod för att hitta ett skärplan är de ofta beroende av erfarenhet, så denna metod används sällan som en generell metod.

Termen gren och bunden användes första gången 1963 i en artikel publicerad av Little et al. på TSP, som beskriver en teknik för att kombinera mindre sökutrymmen och fastställa lägre gränser för att utöka det praktiska tillämpningsområdet för en exakt lösning. Tekniken är användbar för att utöka antalet städer som kan övervägas beräkningsmässigt, men bryts fortfarande ned i storskaliga datamängder.

Den styr sökningsprocessen genom att tillämpa restriktiva gränser, vilket möjliggör en sökning efter den optimala lösningsgrenen från rymdtillståndsträdet för att hitta en optimal lösning så snabbt som möjligt. Den centrala komponenten i denna algoritm är valet av den restriktiva gränsen. Olika restriktiva gränser kan bilda olika grenbundna algoritmer.

Ungefärliga algoritmer för att lösa TSP

Eftersom tillämpningen av exakt algoritm för att lösa problem är mycket begränsad, använder vi ofta ungefärlig algoritm eller heuristisk algoritm. Resultatet av algoritmen kan bedömas med C/C* ≤ ε . C är det totala färdavståndet som genereras från en ungefärlig algoritm; C* är det optimala färdavståndet; ε är den övre gränsen för förhållandet mellan den totala färdsträckan för ungefärlig lösning och optimal lösning under det värsta läget. Värdet på ε >1,0. Ju mer den närmar sig 1.0, desto bättre är algoritmen. Dessa algoritmer inkluderar: Interpolationsalgoritm, Nearest Neighbor-algoritmen , Clark & Wright-algoritmen, Dubbelspännande trädalgoritm, Christofides-algoritmen , Hybridalgoritmen, Probabilistisk algoritm (som Simulated annealing ).