Problem ustalenia, czy program ma „wydajność optymalną” A lub „wydajność optymalną” B w przypadku niemal dowolnej definicji „wydajności optymalnej”, jest ogólnie nierozstrzygalny (dowód poniżej). Oznacza to, że nie ma jednej metody, która zawsze może powiedzieć, jak optymalny jest algorytm.
Istnieją jednak metody, które są często stosowane podczas analizy algorytmów aproksymacyjnych. Często algorytmy aproksymacyjne są oceniane na podstawie ich gwarancji, jak daleko jest to rozwiązanie optymalne. Podam przykładowy problem i przybliżenie, które udowodnię za pomocą metody „dolnej granicy”, która jest bardzo często stosowaną metodą do udowodnienia współczynników.
Problemem jest problem „ładowania ciężarówek”: mamy wiele identycznych ciężarówek (tyle, ile nam się podoba), z których każda jest w stanie unieść ładunek o wadze co najwyżej T. Mamy n przedmiotów, które chcemy załadować w tych ciężarówkach dla transport. Każdy obiekt i ma wagę w_i, gdzie w_i <= T (więc nie ma przedmiotów, które nie mogłyby zmieścić się na ciężarówce nawet same). Przedmioty nie mogą być podzielone na części. Chcielibyśmy napełnić ciężarówki, aby potrzebować jak najmniej ciężarówek. Ten problem jest NP-zupełny.
Istnieje bardzo prosty algorytm aproksymacyjny dla tego problemu. Po prostu zaczynamy ładować ciężarówkę przedmiotami, aż ciężarówka będzie tak pełna, że następny przedmiot nie będzie pasował. Następnie bierzemy kolejną ciężarówkę i ładujemy tę ciężarówkę tym produktem, który nie pasował do poprzedniej ciężarówki. Nie ładujemy już więcej przedmiotów na tę ciężarówkę: zamiast tego bierzemy nową ciężarówkę, ponownie napełniamy ją dużą ilością przedmiotów, aż nie będzie już pasować, ponownie umieszczamy ostatni przedmiot na własnej ciężarówce i tak dalej.
Algorytm ten stanowi tak zwane przybliżenie 2 problemu: wykorzystuje maksymalnie dwa razy więcej ciężarówek, niż byłoby potrzebne optymalne rozwiązanie. „Co najwyżej” jest kluczowe: możemy mieć szczęście i znaleźć optymalne rozwiązanie, ale przynajmniej nie zrobimy nic złego.
Aby to udowodnić, najpierw określamy dolną granicę optymalnej liczby potrzebnych ciężarówek. W tym celu wyobraźmy sobie, że możemy kroić przedmioty na części: moglibyśmy wtedy łatwo napełnić każdą ciężarówkę, ale ostatnią całkowicie. Liczba ciężarówek, których potrzebowalibyśmy, gdybyśmy to zrobili, stanowi dolną granicę liczby ciężarówek potrzebnych w pierwotnym pytaniu: w najlepszym przypadku optymalne rozwiązanie zawsze zapełnia każdą ciężarówkę, w którym to przypadku liczba ciężarówek jest równa, ale jeśli optymalne rozwiązania pozostawiają ciężarówki niewypełnione, może potrzebować tylko więcej ciężarówek.
Teraz patrzymy na nasz algorytm aproksymacyjny. Pamiętaj, że na każdym etapie (częściowo) napełniamy dwie ciężarówki. Zauważ też, że zgodnie z algorytmem elementy w pierwszej ciężarówce i element w drugiej ciężarówce nie mogą zmieścić się w pierwszej ciężarówce, więc ich suma wynosi co najmniej T. Oznacza to, że na każdym etapie ładujemy co najmniej pełny przedmioty warte ciężarówki na dwóch ciężarówkach. Porównajmy to teraz z dolną granicą: w takim przypadku ładujemy przedmioty o wartości pełnej ciężarówki na jedną ciężarówkę. Innymi słowy, nasz algorytm aproksymacyjny oblicza (w czasie liniowym) rozwiązanie, które bardzo przypomina nasze „dolne ograniczenie”, ale używa dwóch ciężarówek zamiast jednego. Dlatego używamy maksymalnie dwa razy więcej ciężarówek niż algorytm optymalny, ponieważ używamy co najmniej dwa razy więcej ciężarówek niż nasza dolna granica optymalnego algorytmu.
Ten algorytm daje przybliżenie o stałym współczynniku: jest co najwyżej 2 razy tak zły, jak optymalne rozwiązanie. Niektóre przykłady innych miar: co najwyżej C więcej niż optymalne rozwiązanie (błąd addytywny, dość rzadki), co najwyżej c log n razy tak źle, jak optymalne rozwiązanie, co najwyżej cn razy tak źle, jak optymalne rozwiązanie, co najwyżej c 2 ^ (dn) razy tak źle, jak optymalne rozwiązanie (bardzo źle; na przykład ogólny TSP dopuszcza tylko algorytmy z tego rodzaju gwarancjami).
Oczywiście, jeśli chcesz mieć pewność, że czynnik, który udowodnisz, jest najlepszym czynnikiem, jaki możesz udowodnić, powinieneś spróbować znaleźć przypadki, w których rozwiązanie podane przez algorytm jest rzeczywiście tak złe, jak to tylko możliwe.
Zauważ również, że czasami używamy algorytmów aproksymacyjnych w przypadku problemów, które nie są trudne NP.
Nauczyłem się tego (wśród wielu innych) na kursie algorytmów aproksymacyjnych na moim uniwersytecie.
Dowód nierozstrzygalności: niech P będzie problemem, a A i B będą algorytmami aproksymacji dla P, gdzie A i B nie mają tej samej „optymalności” dla sensownej definicji „optymalności” i gdzie czas działania A i B jest zarówno omega (1) (ściśle wolniejsze niż stały czas, tj. Stają się wolniejsze w większych przypadkach) i gdzie A i B zawsze się zatrzymują.
Niech D będzie programem, który twierdzi, że może obliczyć następujące: biorąc pod uwagę jakiś program C obliczający przybliżenie dla P, zdecyduj, czy jest on tak dobry jak A czy tak dobry jak B dla wystarczająco dużych danych wejściowych (możesz zatem użyć tego do kategoryzacji programów zgodnie z ich optymalnością).
Następnie możemy użyć D do rozwiązania problemu zatrzymania. Niech E będzie programem, a F wejściem dla tego programu. Użyjemy D, aby zdecydować, czy E zatrzyma się na wejściu F.
Projektujemy program G, który wykonuje następujące czynności: biorąc pod uwagę wejście S dla problemu P, uruchamia E na F i A na S równolegle: wykonuje E przez chwilę, potem A, a następnie E i tak dalej. Jeśli E zatrzyma się na F, przestaje działać A i zamiast tego uruchamia B na S i zwraca wynik B. Jeśli A zatrzymuje się przed E zatrzymuje, zwraca wynik A.
Użycie D na G decyduje teraz, czy E zatrzymuje się na F: jeśli E zatrzymuje się na F, to dla wystarczająco dużych danych wejściowych S, E zatrzymuje się na F przed A zatrzymuje się na S (ponieważ czas, w którym E się zatrzymuje, nie zależy od wielkości wejście, w przeciwieństwie do A). D informuje zatem, że G ma charakterystykę optymalności B. Jeśli E nie zatrzyma się na F, D zgłosi, że G ma charakterystykę optymalności A.