Dla jakich algorytmów istnieje duża luka między analizą teoretyczną a rzeczywistością?

Istnieją dwa sposoby analizy wydajności algorytmu

1. nałożyć asymptotyczną górną granicę czasu działania, oraz
2. aby go uruchomić i zebrać dane eksperymentalne.

Zastanawiam się, czy są znane przypadki, w których istnieje znaczna różnica między (1) a (2). Rozumiem przez to, że albo (a) dane eksperymentalne sugerują silniejszą asymptozę, albo (b) istnieją algorytmy X i Y takie, że analiza teoretyczna sugeruje, że X jest znacznie lepszy niż Y, a dane eksperymentalne sugerują, że Y jest znacznie lepszy niż X.

Ponieważ eksperymenty zwykle ujawniają zachowanie średnich przypadków, oczekuję, że najciekawsze odpowiedzi będą odnosić się do górnych granic średniej wielkości liter. Nie chcę jednak wykluczać interesujących odpowiedzi, które mówią o różnych granicach, takich jak odpowiedź Noama na temat Simplex.

Uwzględnij struktury danych. Proszę podać jeden algo / ds na odpowiedź.

Najbardziej rażącym przykładem jest oczywiście metoda Simplex, która działa szybko w praktyce, co sugeruje wielość aktualności, ale teoretycznie zajmuje wykładniczy czas. Dan Spielman właśnie otrzymał nagrodę Nevanlinna w dużym stopniu za wyjaśnienie tej tajemnicy.

Mówiąc bardziej ogólnie, wiele przypadków programowania liczb całkowitych można rozwiązać całkiem dobrze przy użyciu standardowych solverów IP, np. Można by rozwiązać aukcje kombinatoryczne dla większości prób dystrybucji na znacznych wejściach - http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Bazy Groebner . Najgorszy czas działania jest podwójnie wykładniczy (w liczbie zmiennych). W praktyce jednak, szczególnie w przypadku dobrze ustrukturyzowanych problemów, algorytmy F4 i F5 są skuteczne (tzn. Kończą się dość szybko). Nadal aktywnym obszarem badań jest ustalenie, jaka powinna być właściwa hipoteza dotycząca średniego lub oczekiwanego czasu działania. Przypuszcza się, że jest on w jakiś sposób związany z objętością polytopa Newtona leżącego u podstaw ideału.

$O(2^{(\sqrt{(n log n)})})$

Nie wiem, czy istnieje formalny wynik średnio / wygładzony złożoności problemu, ale pamiętam, że czytałem, że istniał - może ktoś inny może wskazać formalny wynik. Na pewno jest sporo dowodów eksperymentalnych i wiele szybkich solverów. Jestem również ciekawy, czy ta właściwość rozciąga się na innych członków rodziny GI-complete.

Od Davida Johnsona, rozbieżność między teoretycznymi a eksperymentalnymi stosunkami aproksymacji: The Traveling Salesman Problem: A Case Study in Local Optimization, DS Johnson i LA McGeoch . W tym artykule podają eksperymentalne dowody na asymptotyki (ponieważ eksperymenty osiągają rozmiar N = 10 000 000!), Które są sprzeczne z teoretycznymi asymptotykami: algorytm „Chciwy” lub „Multi-Fragment” Jona Bentleya (stosunek przybliżenia najgorszego przypadku co najmniej logN / loglogN) bije Najbliższe wstawianie i Podwójne MST, przy czym oba mają najgorszy stosunek przybliżenia wynoszący 2.

Innym przykładem, który do niedawna nie był dobrze poznany, jest czas działania algorytmu k-średnich Lloyda , który (z praktycznego punktu widzenia) jest wybranym algorytmem klastrowym od ponad 50 lat. Dopiero niedawno, w 2009 r., Udowodniono (przez Vattani ), że w najgorszym przypadku algorytm Lloyda wymaga szeregu iteracji wykładniczych pod względem liczby punktów wejściowych. Z drugiej strony, jednocześnie wygładzona analiza ( Arthur, Manthey i Röglin ) wykazała, że ​​wygładzona liczba iteracji jest jedynie wielomianowa, co wyjaśnia wyniki empiryczne.

Przejście, deque i podzielone następstwa dynamicznej hipotezy o optymalności dla drzew splay są przykładami takich luk. Eksperymenty potwierdzają twierdzenie dotyczące czasu liniowego, ale nie ma znanego dowodu.

Z pytaniem jest niewielki problem. Istnieją w rzeczywistości więcej niż dwa sposoby analizy algorytmu, a jednym z teoretycznych sposobów, który został zaniedbany, jest oczekiwany czas działania, a nie najgorszy przypadek. Tak naprawdę to przeciętne zachowanie przypadku jest istotne podczas przeprowadzania eksperymentów. Oto bardzo prosty przykład: Wyobraź sobie, że masz algorytm dla wejścia o rozmiarze n, który zajmuje czas n dla każdego możliwego wejścia o rozmiarze n, z wyjątkiem jednego określonego wejścia o każdej długości, który zajmuje czas 2 ^ n. Posłuchaj, że najgorszy czas działania jest wykładniczy, ale średni przypadek wynosi [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n, które ograniczenia do n. Oczywiście dwa rodzaje analiz dają bardzo różne odpowiedzi, ale należy się tego spodziewać, ponieważ obliczamy różne wielkości.

Uruchamiając eksperyment kilka razy, nawet jeśli weźmiemy pod uwagę najdłuższy czas wykonywania próbki, nadal próbkujemy tylko niewielką część przestrzeni możliwych danych wejściowych, więc jeśli trudne instancje są rzadkie, możemy je przegapić .

Skonstruowanie takiego problemu jest stosunkowo łatwe: jeśli wszystkie pierwsze n / 2 bity mają wartość zero, rozwiąż instancję 3SAT zakodowaną za pomocą ostatnich n / 2 bitów. W przeciwnym razie odrzuć. Gdy n staje się duże, problem ma mniej więcej taki sam czas działania w najgorszym przypadku, jak najbardziej wydajny algorytm dla 3SAT, gdzie średni czas działania jest gwarantowany na bardzo niskim poziomie.

Wnioskowanie o typie Damasa-Milnera okazało się kompletne dla czasu wykładniczego, i istnieją łatwe do skonstruowania przypadki z wykładniczym powiększeniem wielkości wyniku. Niemniej jednak w przypadku większości rzeczywistych danych wejściowych zachowuje się w sposób liniowy.

PTAS dla drzewa Steiner w grafach płaskich ma absurdalną zależność od epsilon. Istnieje jednak implementacja, która pokazuje zaskakująco dobrą wydajność w praktyce.

Parowanie hałd, od [1] - implementują hałdy, w których wstawianie i łączenie mają złożoność zamortyzowaną O (log n), ale przypuszcza się, że są O (1). W praktyce są one wyjątkowo wydajne, szczególnie dla użytkowników łączenia.

Właśnie je odkryłem dzisiaj, czytając Sec. 5.5 książki C. Okasaki „Czysto funkcjonalne struktury danych”, więc pomyślałem, że powinienem podzielić się informacjami na ich temat.

[1] Fredman, ML, Sedgewick, R., Sleator, DD i Tarjan, RE 1986. Kupa parowania: nowa forma samoregulującej się sterty. Al Algorytmica 1, 1 (styczeń 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Powiązane z uwagą ilyaraza na temat oddziału i granicy, Pataki i in. pokaż, że redukcja rozgałęzień i powiązań plus krata może rozwiązać prawie wszystkie losowe adresy IP w czasie rzeczywistym.

Heurystyka Lin-Kernighana dla TSP („Skuteczna heurystyka dla problemu podróżującego sprzedawcy”, Operations Research 21: 489–516, 1973) jest bardzo skuteczna w praktyce, ale wciąż brakuje przeciętnej liczby przypadków lub wygładzonej analizy wyjaśniającej jej działanie . W przeciwieństwie do tego, Matthias Englert, Heiko Röglin i Berthold Vöcking (pojawią się algorytmy) wygładzili analizę 2-optycznej heurystyki dla TSP.

Istnieje wiele bardzo szybkich i wydajnych w praktyce algorytmów gałęziowych i powiązanych dla różnych problemów trudnych dla NP, których nie możemy rygorystycznie przeanalizować: TSP, drzewo Steiner, pakowanie pojemników i tak dalej.

$\Omega(nm)$