Czy istnieje ogólna metoda oceny optymalności algorytmu optymalizacji?

czy istnieje ogólna metoda oceny optymalności algorytmu optymalizacyjnego, na przykład algorytm rozwiązujący problem, który w innym przypadku byłby trudny do wykonania lub byłby kompletny?

Jedyną metodą, jaką do tej pory wymyśliłem, jest porównanie wyników algorytmu ze znanymi optymalnymi rozwiązaniami.

Jeśli nie, to czy istnieją specjalne metody na niektóre specjalne problemy?

EDYCJA Wyjaśnienie: Przez optymalność rozumiem, jak blisko jest wyniku do optymalnych wyników rozwiązań.

To zależy od rodzaju problemu.

Jeśli dla problemu istnieje schemat aproksymacji czasu wielomianowego (PTAS) (np. Euclidian TSP), możesz uzyskać rozwiązanie, które arbitralnie jest bliskie optymalnemu rozwiązaniu w czasie wielomianowym. Oznacza to, że dla każdego e > 0 istnieje algorytm wielomianowy, który znajdzie przybliżone rozwiązanie problemu, które z pewnością znajdzie się w zakresie (1+ e ) od optymalnego rozwiązania. W takim przypadku po prostu porównałbyś złożoność środowiska wykonawczego / pamięci dla dwóch algorytmów dla tych samych wartości e . Jeśli jeden algorytm może zapewnić te same „gwarancje optymalności” niż drugi, ale przy niższym czasie działania / koszcie pamięci, prawdopodobnie jest to lepszy algorytm.

Jeśli problemem jest APX, ale nie PTAS , tzn. Jeśli istnieją algorytmy aproksymacji czasu wielomianowego, które gwarantują uzyskanie rozwiązań, które mieszczą się w stałym współczynniku optymalnego rozwiązania, można porównać ten stały współczynnik. Ten o niższym współczynniku zapewni lepsze rozwiązania (ale często kosztem wyższego czasu działania / kosztów pamięci)

Jeśli problem nie występuje w żadnej z tych klas, myślę, że najlepiej, co możesz zrobić, to porównać ich rozwiązania dla zestawu problemów losowych lub problemów ze znanymi optymalnymi rozwiązaniami.

Nie sądzę, że istnieje ogólny sposób, aby to zrobić, ale z pewnością istnieją na to metody.

Weźmy na przykład problem SET-COVER. Dla tych, którzy nie wiedzą, problem jest następujący:

Biorąc pod uwagę zestaw elementów B={1,2,...,m}i pewną liczbę podzbiorów, S_1, S_2, ..., S_nktórych połączeniem jest B. Próbujesz znaleźć minimalną liczbę tych podzbiorów, aby związek był nadal B. Typowy przykład tego problemu w świecie rzeczywistym polega na tym, że dostajesz zbiór dzielnic i próbujesz znaleźć optymalne miejsca do umieszczenia szkół, tak aby każda dzielnica była obsługiwana mniej niż w pewnej odległości dod najbliższej szkoły. W tym przypadku Bjest to zestaw dzielnic i S_xskłada się ze wszystkich zestawów w obrębie dmiasta x.

Udowadniasz, że ten problem jest NP-COMPLETE. Istnieje jednak proste chciwe rozwiązanie, w którym wielokrotnie wybierasz zestaw S_iz największą liczbą odkrytych elementów. I możesz udowodnić, że ten algorytm działa dobrze .

Jeśli optymalny algorytm składa się z kzestawów, zachłanny algorytm będzie się składał z nie więcej niż k ln(n)zestawów, w których ln jest logarytmem naturalnym.

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.