Algorytm Christofidesa
Algorytm Christofidesa to algorytm aproksymacyjny, który rozwiązuje problem komiwojażera w grafach, gdzie wagi krawędzi są nieujemne i spełniają warunek nierówności trójkąta. Jest on 1,5-optymalny, co oznacza, że uzyskane rozwiązanie nie jest gorsze niż 1,5-krotność rozwiązania optymalnego.
Opis algorytmu
Rozważmy graf G, który jest grafem pełnym. Dla tego grafu stworzymy minimalne drzewo rozpinające, oznaczane jako T.
Niech zbiór O zawiera wierzchołki o nieparzystym stopniu w drzewie T. Następnie znajdźmy minimalne skojarzenie doskonałe M na wierzchołkach zbioru O spośród krawędzi grafu pełnego G.
Niech graf H będzie multigrafem utworzonym z M i T. Następnie wyznaczamy cykl Eulera w grafie H, który jest eulerowski, ponieważ wszystkie jego wierzchołki mają parzysty stopień. Z cyklu Eulera tworzymy cykl Hamiltona, pomijając już odwiedzone wierzchołki (skracanie).
Dowód 1,5 optymalności
Oznaczmy optymalne rozwiązanie problemu komiwojażera w grafie G jako OPT. Wówczas zachodzi:
w(T) < OPT,
gdyż po usunięciu jednej krawędzi z OPT otrzymujemy drzewo rozpinające, które nie może być mniejsze od minimalnego drzewa T.
Oprócz tego, mamy:
w(M) ≤ OPT / 2.
Wynika to z faktu, że O jest podgrafem G, co oznacza, że rozwiązanie problemu komiwojażera w O jest nie większe niż OPT. Dodatkowo, 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 rezultacie, mamy:
w(H) = w(M) + w(T) < 1.5 * OPT.
W grafie, który spełnia 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.
