Czy jest jakiś inny algorytm, którego najgorszy czas działania jest wykładniczy, podczas gdy działa on bardzo dobrze w praktyce, inny niż algorytm Simplex?

Na ogół algorytm nazywamy „dobrym algorytmem”, jeśli jego czas działania jest w najgorszym przypadku wielomianowy. Ale w niektórych przypadkach (na przykład algorytm Simplex), chociaż najgorszy przypadek algorytmu ma charakter wykładniczy, może on działać bardzo dobrze w praktyce.

Czy są jakieś (deterministyczne) przykłady tej sytuacji inne niż algorytm Simplex?

Współczesne algorytmy rozwiązywania SAT są w stanie dość szybko rozwiązać większość przypadków, nawet jeśli najgorszy przypadek jest oczywiście wykładniczy. W tym przypadku jednak praktyczna szybkość jest raczej wynikiem wielu lat inżynierii algorytmów, a nie pojedynczego eleganckiego algorytmu. Chociaż zrozumiałem, że uczenie się klauzul sterowanych konfliktami spowodowało znaczny skok w wydajności solverów SAT, późniejsze ulepszenia są często osiągane przez sprytne wykorzystanie różnych heurystyk w algorytmach.

The $k$-Oznacza, że ​​algorytm grupowania jest wykładniczy nawet w samolocie, ale działa bardzo dobrze w praktyce.

Wnioskowanie o typie Hindleya-Milnera jest zakończone WYŁĄCZNIE, ale w programach, które ludzie zwykle piszą, jest to prawie liniowe.

Program nauty Brendana McKaya (No AUTomorphisms, Yes?) Rozwiązuje kanoniczny problem znakowania grafów (jednocześnie rozwiązując problemy z Graph Isomorphism i Graph Automorphism) i ma wykładniczą wydajność w najgorszym przypadku (Miyazaki, 1996). Działa jednak bardzo szybko w przypadku większości wykresów, szczególnie tych z kilkoma automorfizmami.

W szczególności algorytm rozpoczyna się od podzielenia wierzchołków według stopnia, a następnie stopnia między każdą częścią. Gdy proces ten się ustabilizuje, należy dokonać wyboru, aby rozróżnić wierzchołek w części niebanalnej, a to prowadzi do zachowania wykładniczego. Na większości wykresów głębokość tej procedury rozgałęziania jest niewielka.

Kilka algorytmów dla prostych gier stochastycznych działa dobrze w praktyce, mimo że mają one wykładniczo najgorsze czasy działania. Oczywiście problem ten jest w pewnym sensie związany z programowaniem liniowym, chociaż nie wiadomo, że występuje w czasie wielomianowym.

Istnieje algorytm znajdowania mieszanych równowag Nasha, podobny do algorytmu simpleksowego dla płyt LP. (Zapominam nazwę.) Ma wykładniczą najgorszą złożoność, ale mam niejasne wspomnienie, że często zachowuje się dobrze w praktyce.

Pakowanie pojemników (wiele wariantów) to problem, którego złożoność jest trudna do NP:

http://en.wikipedia.org/wiki/Bin_packing_problem

Jednak wiele heurystyk przy zastosowaniu do „praktycznych” wersji ma się bardzo dobrze. Do jednowymiarowego pakowania bin niektóre z tych heurystyk, na przykład pierwsze dopasowanie; pierwsze dopasowanie maleje; Najlepsze dopasowanie; zmniejszanie najlepszego dopasowania jest bardzo atrakcyjne jako temat do pokazania uczniom. Studenci często mogą odkryć niektóre podstawowe heurystyki dla siebie.

Algorytm trwałości (pochodzący z Edelsbrunner-Letscher-Zomorodian, z dużą ilością odmian od tego czasu) jest najgorszym przypadkiem sześciennym, ale wydaje się, że z eksperymentów zwykle działa w czasie liniowym.