Potężne algorytmy zbyt skomplikowane do wdrożenia

67

Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować?

Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go bezużytecznym w praktyce. Szukam algorytmów, które mogłyby mieć praktyczną wartość, ale są tak trudne do zakodowania, że ​​nigdy nie zostały zaimplementowane, tylko zaimplementowane w wyjątkowo sztucznych ustawieniach lub tylko zaimplementowane w aplikacjach o wyjątkowym przeznaczeniu.

Również mile widziane są prawie niemożliwe do wdrożenia algorytmy, które mają dobrą asymptotę, ale prawdopodobnie będą miały słabą rzeczywistą wydajność.

Elliot Jans
źródło
1
czyniąc to CW, ponieważ może to być długa lista.
Suresh Venkat
4
Czy istnieje wskaźnik „prawie niemożliwy do wdrożenia”? Czy istnieje teoria, która ją definiuje?
Ritwik Bose
@Mechko, być może dolna granica wielkości najmniejszej maszyny Turinga, która wyświetla opis maszyny Turinga, która jest implementacją algorytmu. :)
Radu GRIGore
@Radu GRIGore jest to metryka zaakceptowana czy należy ją opracować? Przypuszczam, że (na razie) istnieje prosta, nieruchoma linia, która definiuje „meh, not worth it” ...: D
Ritwik Bose
4
Interesuje mnie sugestia, że ​​wdrożenie Coppersmith-Winograd jest rozsądne. Czy ktoś widział kiedyś implementację spisaną nawet w pseudokodzie wysokiego poziomu i czy ktokolwiek kiedykolwiek oszacował stałe?
Raphael

Odpowiedzi:

33

Chazelle podał liniowy algorytm czasowy do triangulacji prostego wielokąta . Skiena napisała (str. 575, Podręcznik projektowania algorytmów), że „jest wystarczająco beznadziejna do wdrożenia, że ​​kwalifikuje się bardziej jako dowód istnienia”

Jarosław Bułatow
źródło
3
Czy algorytm ma rozsądne stałe?
jbapple 25.01.11
Czy to jedyny znany algorytm czasu liniowego dla problemu?
Thomas Ahle,
2
@ThomasAhle Uważam, że jest to jedyny znany deterministyczny algorytm liniowy czasu. Amato, Goodrich i Ramos mają prostszą, losową: cs.princeton.edu/courses/archive/fall05/cos528/handouts/...
Sasho Nikolov
Według mojej wiedzy prosty algorytm triangulacji wielokąta Chazelle w czasie liniowym nigdy nie został zaimplementowany i prawdopodobnie nigdy nie będzie z powodu swojej złożoności, a także dlatego, że stałe są wysokie, więc nie będzie w stanie konkurować z alternatywami w praktyce. Najważniejsze osiągnięcie teoretyczne. Ralph Boland
Ralph Boland
Zapytam jeszcze raz: czy algorytm ma rozsądne stałe?
użytkownik1271772
29

Algorytm Risch do obliczania podstawowych funkcja pierwotna. Według Wikipedii żaden pakiet oprogramowania nie jest w stanie wdrożyć pełnego algorytmu ze względu na jego złożoność.

Mark Reitblatt
źródło
3
Wikipedia wskazuje również, że nie jest to algorytm, ale pół-algorytm, ponieważ wymaga heurystyki do rozwiązania stałego problemu.
sclv
Co to jest heurystyka? Czy możesz podać link, aby przeczytać więcej na ten temat?
zygimantus
22

Każdy algorytm, który wykorzystuje wyniki Robertsona-Seymoura do wnioskowania o algorytmie „czasu policy” dla rzeczy obejmujących wykresy, które wykluczają ustaloną drugorzędną, prosi o kłopoty. Stałą ukrytą w ich wyniku jest „galaktyczna”.

Suresh Venkat
źródło
3
Czy to również jest trudne do wdrożenia, czy po prostu ma ogromną stałą?
Lev Reyzin
5
Tak, to nie wygląda na dobry przykład. Jeśli dobrze rozumiem, pytanie dotyczy algorytmów, które mogą być praktyczne (stąd prawdopodobnie „małe” stałe), ale są zbyt skomplikowane do wdrożenia. Oczywiście całe pytanie jest otwarte na różne interpretacje :-)
Aryabhata
5
Problem polega na tym, że stała pochodzi z bardzo dużej listy nieletnich, którą należy wykluczyć dla konkretnej nieruchomości. Nie znam żadnego sposobu na wygenerowanie pożądanej listy wykluczonych nieletnich dla danej nieruchomości, więc nie jest to tylko kwestia skali.
Suresh Venkat
2
Na przykład nie znamy nawet listy wykluczonych nieletnich dla wykresów możliwych do osadzenia w torusie.
Derrick Stolee
17
Problem wydaje się tutaj głębszy: nie ma skutecznego sposobu generowania listy nieletnich, więc w rzeczywistości nie daje to żadnego algorytmu. Większość drobnych zamkniętych właściwości daje nieskończoną listę wykluczonych nieletnich, jeśli bezpośrednio tłumaczy się wyrażenie logiczne. Twierdzenie Robertsona-Seymour'a (hipoteza Wagnera) mówi nam, że skończona lista wykluczonych nieletnich czai się na tej nieskończonej liście, ale twierdzenie absolutnie nie pomaga w ich odnalezieniu. Zatem Robertson-Seymour zwykle prowadzi do czystego dowodu istnienia.
András Salamon
16

O(n)O(log2nB)B

Artykuł ma 55 stron, a jego wniosek odnotowuje kilka ulepszeń stałych, których autor nie opisuje ze względu na miejsce. To sprawia, że ​​podejrzewam, że być może stałe nie są tak galaktyczne i że ta struktura danych byłaby „uzasadnioną użytecznością”, zwłaszcza że była wielokrotnie cytowana.

jbapple
źródło
12

Algorytm ujednolicania wzorców wyższego rzędu w linii liniowej przez Qian nigdy nie został wdrożony ze względu na jego złożoność AFAIK.

Dominic Mulligan
źródło
Na szczęście istnieją jeszcze praktyczne algorytmy. Podręcznik automatycznego rozumowania mówi, że można to zrobić w czasie polytime (tuż obok miejsca, w którym przytacza algorytm Qian), więc jest to całkiem niesamowite.
Jake,
11

Algorytm czasu liniowego do sprawdzania, czy wykres można osadzić na stałej powierzchni.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: Prostszy algorytm czasu liniowego do osadzania wykresów na powierzchni arbitralnej i rodzaju wykresów ograniczonej szerokości drzewa. FOCS 2008: 771–780.

Bojan Mohar: Algorytm czasu liniowego do osadzania wykresów na powierzchni arbitralnej. SIAM J. Discrete Math. 12 (1): 6-26 (1999)

ktoś
źródło
1
Jest mało prawdopodobne, aby miało to wartość praktyczną, nawet jeśli zostanie wdrożone, z powodu dużej wykładniczej (sic) zależności od rodzaju.
Jeffε
8

Nie jestem pewien, jak użyteczna może być w praktyce (chociaż myślę o zwijaniu i porównywaniu białek, a także przewidywaniu struktury drugorzędowej RNA), ale Wolfgang Haken podał pierwszy algorytm czasu wielomianowego do decydowania, czy węzeł jest prosta pętla ( Theorie der Normalflächen. Acta Math. 105, 1961, s. 245--375). O ile pamiętam, wciąż jest zbyt skomplikowany, aby wdrożyć go przez te wszystkie dekady później.

Jeśli wierzyć Wikipedii, później podano kilka innych algorytmów, a „Zrozumienie złożoności tych algorytmów jest aktywnym obszarem badań”.

rev Anthony Labarre
źródło
4
Haken podał pierwszy algorytm, ale nie działa on w czasie wielomianowym; w rzeczywistości żaden algorytm wieloczasowy (lub wynik twardości NP) nie jest znany. Nowsze prace zmniejszyły trywialność węzłów (poprzez formułowanie normalnej powierzchni Hakena) do programowania liczb całkowitych, które zwykle jest w praktyce szybkie.
Jeffε 27.01.11
3

Rozkład drzew i być może sterty Fibonacciego .

Peter Boothe
źródło
14
Stosy Fibonacciego z pewnością nie są zbyt skomplikowane do wdrożenia; zostały wdrożone i przetestowane. Problem z nimi polega raczej na tym, że ich praktyczna wydajność nie jest tak dobra, jak niektóre inne sterty ze względu na duże stałe czynniki w czasie ich działania.
David Eppstein
1
Napisałem pakiet, aby znaleźć rozkład drzewa i nie sądzę, że trudno jest wdrożyć yaroslavvb.blogspot.com/2011/01/building-junction-trees.html
Jarosław
2
Mój kod jest po prostu heurystycznym rozkładem drzew, a nie optymalnym jak podejście do programowania dynamicznego w gałęziach i gałęziach ... Zgaduję, że miałeś na myśli "Algorytm czasu liniowego Bodlaendera ..."? Nie widziałem żadnych implementacji tego
Jarosław Bułatow
4
2O(k3)O(n)
3
Myślę, że to najlepszy wysiłek wdrożeniowy: hein.roehrig.name/dipl
Diego de Estrada
1

Idealna konstrukcja skrótu ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) miałaby zastosowanie do każdego przypadku użycia ze statycznymi lub rzadko zmieniającymi się kluczami (np. Nazwy domen najwyższego poziomu na routerach, słowa kluczowe w kompilatorach lub nazwy funkcji w bibliotekach standardowych), ale kiedy ostatnio szukałem, nie mogłem znaleźć żadnych implementacji.

Wyszukiwanie parametryczne może rozwiązać wiele trudnych problemów związanych z optymalizacją, w tym niektóre, które mogą wyglądać na trudne NP, w czasie wielomianowym. Dobrze nazwany artykuł Wyszukiwanie parametryczne w praktyce zaimplementował wariant wyszukiwania parametrycznego, ale nadal nie sądzę, aby został zaimplementowany w praktycznym oprogramowaniu.

knO(nlogn+k)O((n+k)logn)

Kevin A. Wortman
źródło
1
Nie wierzę, że konstrukcja FKS jest zbyt skomplikowana, aby ją wdrożyć. To jest właściwie całkiem proste. Może nie jest to praktyczne, ale z pewnością nie jest zbyt skomplikowane do wdrożenia.
Sasho Nikolov