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

52

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ź.

Radu GRIGore
źródło
Byłoby pomocne, gdybyś wyjaśnił, o jakich górnych granicach mówisz. Czy mówisz tylko o problemach, w przypadku których istnieje znaczna luka między najlepiej znanymi górnymi i dolnymi granicami dla złożoności w najgorszym przypadku? A może obejmujesz również problemy, dla których znane są ścisłe ograniczenia złożoności w najgorszym przypadku, ale typowe czasy działania są znacznie krótsze? Bardziej interesujące może być rozważenie wygładzonej złożoności niż złożoności w najgorszym przypadku. Wyniki eksperymentalne dotyczące „typowych” danych wejściowych lub danych losowych niewiele robią, by obalić istnienie danych patologicznych.
James King
W takim przypadku uważam, że należy zadać osobno dwa pytania: jedno dotyczące luk między złożonością najgorszego przypadku a złożonością średniego przypadku / wygładzonej, a drugie dotyczące luk między teoretyczną złożonością średniego przypadku / wygładzonej a praktycznymi wynikami eksperymentalnymi. Edycja: dokonałeś edycji, zajmując się tym podczas pisania komentarza :)
James King,

Odpowiedzi:

37

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

Noam
źródło
3
Czy istnieje wyraźna rodzina programów liniowych, dla których simpleks wymaga czasu wykładniczego?
Opt
1
O ile rozumiem, istnieje wiele wyraźnych rodzin, które wymagają wykładniczego czasu (np. Pierwsze podanie podane przez Klee i Minty: „Jak dobry jest algorytm simpleks?”, 1972). Jednak wybór reguły przestawnej jest istotny dla tych wyników. Myślę, że większość odniesień do tych wyników można znaleźć w pracy Spielmana i Tenga ( arxiv.org/abs/cs/0111050 ).
MRA,
istnieją ograniczenia dla niektórych konkretnych zasad przestawiania w tym dokumencie cs.au.dk/~tdh/papers/random_edge.pdf
Igor Shinkar
26

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.

Jacques Carette
źródło
Średnia / oczekiwana przy jakiej dystrybucji? Myślałem, że nawet określenie oczekiwanego czasu działania jest trudne z powodu problemów algebraicznych ...
Joshua Grochow
1
Nie znam przypadków szybko rozwiązanych metodami F4 i F5, ale dość łatwo jest zbudować system wielomianów z wieloma zmiennymi i niskim stopniem, które kodują instancję SAT. W takim przypadku nie wiadomo mi, że algorytm przewyższa DPLL / DPLL +. Naprawdę chciałbym dowiedzieć się więcej o wynikach eksperymentalnych tych rzeczy!
MassimoLauria,
@Joshua: w tym momencie każda dystrybucja, która pozwala na wyniki ... @Massimo: kodowanie problemu X jako instancji Y prawie nigdy nie przebije wyspecjalizowanych algorytmów dla X! Ale GB i DPLL są zasadniczo równoważne, więc byłbym bardzo zaskoczony, widząc skuteczną różnicę.
Jacques Carette,
1
@Massimo: Tak, obliczenia w GB są trudne. W zależności od receptury. W rzeczywistości większość pytań (wypełnienie, idealne członkostwo, algebraicznie zamknięte pole vs booleany) jest PSPACE kompletna lub gorsza (EXPSPACE ukończona). To znaczy, że obliczenia GB będą znacznie trudniejsze niż problemy z NP-zupełnością (a więc nawet średni przypadek, każdy algorytm dla nich jak F5 najprawdopodobniej nie przewyższy DPLL).
Mitch
22

O(2)((nlosoln)))

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.

Anand Kulkarni
źródło
1
O(2)nlogn)
2
O! Być może myślisz o Babai-Kucera, który podaje algorytm GI dla średniego czasu liniowego: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua
Tak, to Babai-Kucera! Dzięki za referencje.
Anand Kulkarni
20

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.

Joshua Grochow
źródło
20

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.

MRA
źródło
10

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.

Radu GRIGore
źródło
3
Seth Pettie udowodnił, że n operacji deque zajmuje nie więcej niż czas O (n alpha * (n)), gdzie „alpha *” to iterowana odwrotna funkcja Ackermanna, która jest dość małą przerwą.
jbapple,
9

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.

Joe Fitzsimons
źródło
Już odpowiedziałem Jamesowi Kingowi, że spodziewam się, że najciekawsze odpowiedzi będą dotyczyły oczekiwanego czasu działania. Zmienię pytanie, aby było bardziej widoczne.
Radu GRIGore
9

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.

sclv
źródło
Czy możesz polecić ten wynik? Chciałbym przeczytać więcej na ten temat.
Radu GRIGore
1
Nie czytałem go sam, ale najczęściej cytowanym artykułem jest Harry G. Mairson, „Rozstrzygalność pisania ML jest kompletna w deterministycznym czasie wykładniczym”, 17. Sympozjum na temat zasad programowania języków (1990).
sclv
9

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.

zotachidil
źródło
8

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

Blaisorblade
źródło
Od czasu Okasaki nastąpił pewien postęp, a teraz są (imperatywne) parowanie hałd z O (0) meld, O (1) insert and findMin, O (lg lg n) zmniejszKey i O (lg n) deleteMin: arxiv. org / abs / 0903.4130 . Ta sterta wykorzystuje inny mechanizm parowania niż oryginalne stosy parowania Fredmana i in.
jbapple
7

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.

Marco
źródło
6

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.

Bodo Manthey
źródło
5

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.

Ω(nm)

ilyaraz
źródło
Masz na myśli O (mn), czy jestem zdezorientowany?
Radu GRIGore
O(nmlosol(n2)/m))