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 $G$ będzie grafem pełnym.

1. Dla grafu $G$ stwórzmy minimalne drzewo rozpinające $T.$
2. Niech $O$ będzie zbiorem wierzchołków o nieparzystym stopniu w $T.$ Znajdźmy minimalne skojarzenie doskonałe $M$ na wierzchołkach $O$ spośród krawędzi grafu pełnego $G.$
3. Niech $H$ będzie multigrafem utworzonym z $M$ i $T.$
4. Wyznaczmy cykl Eulera w grafie $H$ (graf $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 $G$ jako $OPT.$ Zachodzi $w(T)<OPT,$ ponieważ po usunięciu jednej z krawędzi z $OPT$ powstaje drzewo rozpinające, które nie może być mniejsze od minimalnego drzewa rozpinającego $T.$ Ponadto zachodzi $w(M)<=OPT/2.$ Wynika to z faktu iż $O$ jest podgrafem $G,$ a więc rozwiązanie problemu komiwojażera w $O$ jest nie większe niż $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ż $OPT/2.$ W takim razie waga $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 $1{,}5*OPT.$

Bibliografia

• NIST Christofides Algorithm Definition