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

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(\frac{\log^2 n}{B})$ $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

2^{O (k^{3})} O (n)

$2^{O(k^3)} 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.

$k$ $n$ $O(n \log n + k)$ $O((n+k) \log n)$

— 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