Algorytm Christofidesa

Algorytm Christofidesa – algorytm aproksymacyjny znajdujący rozwiązanie problemu komiwojażera w grafach w których wagi krawędzi są nieujemne i spełniają warunek nierówności trójkąta. Algorytm jest 1,5-optymalny, to znaczy, że znalezione rozwiązanie będzie nie gorsze niż 1,5 rozwiązania optymalnego.

Algorytm

Niech ${\displaystyle G}$ będzie grafem pełnym.

1. Dla grafu ${\displaystyle G}$ stwórzmy minimalne drzewo rozpinające ${\displaystyle T.}$
2. Niech ${\displaystyle O}$ będzie zbiorem wierzchołków o nieparzystym stopniu w ${\displaystyle T.}$ Znajdźmy minimalne skojarzenie doskonałe ${\displaystyle M}$ na wierzchołkach ${\displaystyle O}$ spośród krawędzi grafu pełnego ${\displaystyle G.}$
3. Niech ${\displaystyle H}$ będzie multigrafem utworzonym z ${\displaystyle M}$ i ${\displaystyle T.}$
4. Wyznaczmy cykl Eulera w grafie ${\displaystyle H}$ (graf ${\displaystyle H}$ jest eulerowski, ponieważ ma wszystkie wierzchołki parzystego stopnia).
5. Z cyklu Eulera zróbmy cykl Hamiltona poprzez pomijanie odwiedzonych wierzchołków (skracanie).

Dowód 1,5 optymalności

Oznaczmy rozwiązanie optymalne problemu komiwojażera w ${\displaystyle G}$ jako ${\displaystyle OPT.}$ Zachodzi ${\displaystyle w(T)<OPT,}$ ponieważ po usunięciu jednej z krawędzi z ${\displaystyle OPT}$ powstaje drzewo rozpinające, które nie może być mniejsze od minimalnego drzewa rozpinającego ${\displaystyle T.}$ Ponadto zachodzi ${\displaystyle w(M)\leqslant OPT/2.}$ Wynika to z faktu iż ${\displaystyle O}$ jest podgrafem ${\displaystyle G,}$ a więc rozwiązanie problemu komiwojażera w ${\displaystyle O}$ jest nie większe niż ${\displaystyle OPT,}$ oraz z faktu iż to rozwiązanie można podzielić na dwa uzupełniające się skojarzenia z których przynajmniej jedno musi być nie większe niż ${\displaystyle OPT/2.}$ W takim razie waga ${\displaystyle w(H)=w(M)+w(T)<1{,}5*OPT.}$ W grafie spełniającym nierówność trójkąta, operacja skracania nie może wydłużyć cyklu, więc waga uzyskanego cyklu Hamiltona jest równa ${\displaystyle 1{,}5*OPT.}$

Bibliografia

• NIST Christofides Algorithm Definition