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 będzie grafem pełnym.
- Dla grafu stwórzmy minimalne drzewo rozpinające
- Niech będzie zbiorem wierzchołków o nieparzystym stopniu w Znajdźmy minimalne skojarzenie doskonałe na wierzchołkach spośród krawędzi grafu pełnego
- Niech będzie multigrafem utworzonym z i
- Wyznaczmy cykl Eulera w grafie (graf jest eulerowski, ponieważ ma wszystkie wierzchołki parzystego stopnia).
- 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 jako Zachodzi ponieważ po usunięciu jednej z krawędzi z powstaje drzewo rozpinające, które nie może być mniejsze od minimalnego drzewa rozpinającego Ponadto zachodzi Wynika to z faktu iż jest podgrafem a więc rozwiązanie problemu komiwojażera w jest nie większe niż 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ż W takim razie waga 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
Bibliografia
- NIST Christofides Algorithm Definition
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |