Algorytmy aproksymacyjne stosowane w algorytmach dokładnych

Algorytmy aproksymacyjne mogą dawać wynik do pewnego stałego współczynnika. Jest to nieco mniej satysfakcjonujące niż dokładne algorytmy.

Jednak stałe czynniki są ignorowane w złożoności czasowej.

Zastanawiam się więc, czy następująca sztuczka jest możliwa lub została zastosowana, aby rozwiązać jakiś problem :$B \circ A$

1. Użyj algorytmu aproksymacyjnego rozwiązującego problem aby uzyskać rozwiązanie w ramach stałego współczynnika;$A$$S$
2. Użyj dokładnego algorytmu, rozwiązując problem , którego czas działania zależy od masy ale działa, dopóki jest poprawnym rozwiązaniem.S $B$$S$$S$

W ten sposób aproksymacja jest „podprocedurą” dokładnego algorytmu, a stały współczynnik utracony w kroku 1 zostaje połknięty w kroku 2.

Przykładem sparametryzowanej złożoności jest jądro dla problemu pokrycia wierzchołka przy użyciu twierdzenia Nemhausera i Trottera.

W przypadku problemu minimalnego pokrycia wierzchołków otrzymujemy niekierowany wykres G i musimy znaleźć pokrycie wierzchołków G o minimalnym rozmiarze. Pokrywa wierzchołka niekierowanego wykresu jest podzbiorem wierzchołków, który dotyka wszystkich krawędzi.

Oto dokładny algorytm, który wykorzystuje aproksymację w pierwszej fazie.

Faza 1: Skonfiguruj liczbowe programowanie liczb całkowitych problemu minimalnego pokrycia wierzchołków . Wiadomo (lub łatwo wykazać), że podstawowe optymalne rozwiązanie relaksacji programowania liniowego jest w połowie integralne (tj. Każda współrzędna ma wartość 0, 1 lub 1/2). Takie podstawowe optymalne rozwiązanie można znaleźć w zwykłym algorytmie wielomianowym dla programowania liniowego (lub w tym szczególnym przypadku możemy sformułować go jako problem z przepływem sieci, abyśmy mogli rozwiązać go kombinatorycznie w czasie wielomianowym). Mając takie podstawowe optymalne rozwiązanie, zaokrąglamy je w górę, aby uzyskać możliwe rozwiązanie pierwotnego problemu programowania liniowego liczb całkowitych. Niech S będzie odpowiednim podzbiorem wierzchołków. Warto zauważyć, że S jest przybliżeniem 2 podanej instancji minimalnego pokrycia wierzchołka.

Faza 2: Znajdź minimalną osłonę wierzchołka w podrozdziale wywołanym przez S (na przykład przez wyczerpujące wyszukiwanie). Twierdzenie Nemhausera i Trottera stwierdza, że ​​ten podgraph zawiera optymalne rozwiązanie oryginalnego wykresu wejściowego. Tak więc następuje poprawność tego podejścia.

Możesz zapoznać się z książką Niedermeiera na temat algorytmów o stałych parametrach dla tego algorytmu.

Jeden przykład dotyczy rozkładów drzew i wykresów małej szerokości.

Zazwyczaj, jeśli otrzymamy rozkład drzewa, dość łatwo zastosować programowanie dynamiczne w celu optymalnego rozwiązania danego problemu graficznego Czas działania zależy od szerokości rozkładu drzewa.$B$

Zwykle jednak nie dostajemy rozkładu drzewa, ale musimy go znaleźć. Aby rozwiązać problem, tak szybko jak to możliwe, chcielibyśmy znaleźć rozkład drzewa najmniejszej szerokości - teraz to jest nasz problem .$B$$A$

$A$$A$$A$$A$$B$

$B$$A$

$B$$A$$A$$B$

Przykładem algorytmu aproksymacyjnego, który jest zbieżny z dokładnym rozwiązaniem, jest algorytm elipsoidy do rozwiązywania LP - jeśli współczynniki są wymierne, wówczas można obliczyć minimalną odległość między dwoma wierzchołkami wykonalnego polytopa. Teraz algorytm elipsoidy oblicza wielokrotnie coraz mniejszą elipsoidę, która musi zawierać optymalne rozwiązanie. Kiedy elipsosoid jest wystarczająco mały, aby pomieścić tylko taki pojedynczy wierzchołek, w zasadzie znalazłeś optymalny wierzchołek. Dlatego LP jest słabo wielomianowy.

$k$

Wreszcie, idąc dalej do pola - wiele algorytmów, które podążają za techniką modyfikacji (pobierz losową próbkę - a następnie wykonaj kilka poprawek, aby uzyskać to, czego chcesz), wpada do takiej struktury. Jednym uroczym przykładem jest algorytm obliczania mediany przy użyciu losowego próbkowania (patrz książka Motwani i Raghavan). Istnieje wiele takich przykładów - prawdopodobnie wiele randomizowanych algorytmów przyrostowych w geometrii obliczeniowej mieści się w tej strukturze.

Wiele algorytmów wrażliwych na wyniki wykorzystuje tę technikę. Na przykład tutaj jest prosty problem, na którym można zastosować tę technikę:

Problem . Otrzymujesz tablicę A [1 .. n ], w której każdy element znajduje się w odległości k pozycji od pozycji, w której byłby, gdyby A był posortowany.

Na przykład A [1..7] pokazany poniżej może być tablicą wejściową dla k = 2.

Źródło problemu: Archiwum Algo Muse .