Algoritma yang kuat terlalu rumit untuk diimplementasikan

67

Apa saja beberapa algoritma utilitas yang sah yang terlalu rumit untuk diterapkan?

Biarkan saya menjadi jelas: Saya tidak mencari algoritma seperti algoritma multiplikasi matriks optimal asimptotik saat ini (Coppersmith-Winograd), yang masuk akal untuk diimplementasikan tetapi memiliki konstanta yang membuatnya tidak berguna dalam praktiknya. Saya mencari algoritma yang mungkin memiliki nilai praktis, tetapi sangat sulit untuk dikodekan sehingga tidak pernah diimplementasikan, hanya diimplementasikan dalam pengaturan yang sangat buatan, atau hanya diimplementasikan untuk aplikasi dengan tujuan khusus yang luar biasa.

Selamat datang juga hampir tidak mungkin untuk mengimplementasikan algoritma yang memiliki asimptotik yang baik tetapi kemungkinan akan memiliki kinerja nyata yang buruk.

ds.algorithms ds.data-structures big-list implementation Elliot Jans
sumber
1
membuat CW ini, karena bisa jadi daftar panjang.
Suresh Venkat
4
Apakah ada metrik untuk 'hampir mustahil untuk diterapkan'? Apakah ada teori yang mendefinisikannya?
Ritwik Bose
@ Techko, mungkin batas bawah pada ukuran mesin Turing terkecil yang menghasilkan deskripsi mesin Turing yang merupakan implementasi dari algoritma. :)
Radu GRIGore
@ Radu GRIGore apakah ini metrik yang diterima atau yang harus dikembangkan? Saya kira (untuk saat ini) ada garis sederhana dan tak tergoyahkan yang mendefinisikan 'meh, tidak layak' ...: D
Ritwik Bose
4
Saya tertarik dengan saran bahwa Coppersmith-Winograd masuk akal untuk diterapkan. Adakah yang pernah melihat implementasi yang dituliskan bahkan dalam pseudo-code tingkat tinggi dan adakah yang pernah memperkirakan konstanta?
Raphael

Jawaban:

33

Chazelle memberikan algoritma waktu linier untuk melakukan triangulasi poligon sederhana . Skiena menulis (hal.575, Manual Desain Algoritma) bahwa "tidak ada harapan untuk mengimplementasikannya sehingga lebih memenuhi syarat sebagai bukti keberadaan"

Yaroslav Bulatov
sumber
3
Apakah algoritma memiliki konstanta yang masuk akal?
jbapple
Apakah ini satu-satunya algoritma waktu linear yang diketahui untuk masalahnya?
Thomas Ahle
2
@ Thomas, saya percaya itu adalah satu-satunya algoritma waktu linear deterministik yang diketahui. Amato, Goodrich, dan Ramos memiliki yang acak sederhana: cs.princeton.edu/courses/archive/fall05/cos528/handouts/…
Sasho Nikolov
Algoritma triangulasi poligon sederhana linear waktu Chazelle, setahu saya, belum pernah diterapkan dan kemungkinan tidak akan pernah karena kompleksitasnya dan juga karena konstanta yang tinggi sehingga tidak akan dapat bersaing dengan alternatif dalam praktik. Namun, pencapaian teoretis utama. Ralph Boland
Ralph Boland
Saya akan bertanya lagi: Apakah algoritma memiliki konstanta yang masuk akal?
user1271772
29

The algoritma Risch untuk menghitung antiturunan SD. Menurut Wikipedia, tidak ada paket perangkat lunak yang diketahui mengimplementasikan algoritma penuh karena kerumitannya.

Tandai Reitblatt
sumber
3
Wikipedia juga menunjukkan bahwa ini bukan algoritma tetapi semi-algoritma karena memerlukan heuristik untuk menyelesaikan masalah yang konstan.
sclv
Apa itu heuristik? Bisakah Anda memberikan beberapa tautan untuk membaca lebih lanjut tentang itu?
zygimantus
22

Algoritme apa pun yang menggunakan hasil Robertson-Seymour untuk menyimpulkan algoritma "polytime" untuk hal-hal yang melibatkan grafik yang mengecualikan minor tetap meminta masalah. Konstanta yang tersembunyi dalam hasilnya adalah "galaksi".

Suresh Venkat
sumber
3
Apakah ini juga sulit untuk diterapkan atau hanya memiliki konstanta yang sangat besar?
Lev Reyzin
5
Ya, ini bukan contoh yang bagus. Jika saya mengerti dengan benar, pertanyaannya adalah tentang algoritma yang bisa praktis (karena itu kemungkinan konstanta 'kecil') tetapi terlalu rumit untuk diimplementasikan. Tentu saja, seluruh pertanyaan terbuka untuk interpretasi yang berbeda :-)
Aryabhata
5
Masalahnya adalah konstanta berasal dari daftar anak di bawah umur yang sangat besar yang perlu dikecualikan untuk properti tertentu. Saya tidak tahu cara apa pun untuk menghasilkan daftar yang diinginkan dari anak di bawah umur untuk properti tertentu, jadi itu bukan hanya masalah skala.
Suresh Venkat
2
Misalnya, kita bahkan tidak tahu daftar anak di bawah umur yang dikecualikan untuk grafik yang dapat disematkan di torus.
Derrick Stolee
17
Masalahnya di sini tampaknya lebih dalam: tidak ada cara efektif yang diketahui untuk menghasilkan daftar anak di bawah umur, jadi ini sebenarnya tidak menghasilkan algoritma sama sekali. Sebagian besar properti tertutup kecil menghasilkan daftar terbatas anak di bawah umur yang dikecualikan, jika seseorang menerjemahkan ekspresi logis secara langsung. Teorema Robertson-Seymour (Wagner's Conjecture) memberi tahu kita bahwa daftar terbatas anak di bawah umur yang bersembunyi di dalam daftar yang tak terbatas itu, tetapi teorema itu sama sekali tidak membantu dalam menemukan mereka. Jadi, Robertson-Seymour karenanya biasanya mengarah pada bukti keberadaan murni.
András Salamon
16

Dan Willard "Algoritma kontrol kerapatan untuk melakukan penyisipan dan penghapusan dalam file berurutan dalam waktu kasus terburuk yang baik" menjelaskan algoritma untuk mempertahankan kumpulan yang diatur dalam array ukuran dengan penyisipan dan penghapusan terburuk, di mana adalah ukuran halaman.O(n)O(log2⁡nB)B

Makalah ini panjangnya 55 halaman, dan kesimpulannya mencatat beberapa perbaikan pada konstanta yang tidak dijelaskan oleh penulis karena alasan ruang. Ini membuat saya curiga bahwa konstanta mungkin tidak begitu galaksi, dan bahwa struktur data ini akan menjadi "utilitas yang sah", terutama karena telah dikutip berulang kali.

jbapple
sumber
12

Algoritma unifikasi pola orde tinggi waktu linier oleh Qian tidak pernah diterapkan karena kompleksitasnya AFAIK.

Dominic Mulligan
sumber
Untungnya masih ada algoritma praktis untuk itu. Buku pegangan penalaran otomatis mengatakan itu bisa dilakukan dalam polytime (tepat di sebelah mana ia mengutip algoritma Qian) sehingga cukup mengagumkan.
Jake
11

Algoritma linear waktu untuk memeriksa apakah grafik dapat disematkan pada permukaan yang tetap.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: Algoritma Waktu Linear yang Lebih Sederhana untuk Memasukkan Grafik ke Permukaan Sewenang-wenang dan Genus Grafik dari Lebar Pohon yang Dibatasi. FOCS 2008: 771-780.

Bojan Mohar: Algoritma Waktu Linear untuk Menanamkan Grafik di Permukaan Sewenang-wenang. SIAM J. Discrete Math. 12 (1): 6-26 (1999)

some one
sumber
1
Ini tidak mungkin memiliki nilai praktis bahkan jika diimplementasikan, karena ketergantungan (sic) eksponensial yang besar pada genus.
Jeffε
8

Saya tidak yakin seberapa berguna itu dalam praktek (walaupun saya berpikir tentang pelipatan protein dan perbandingan, serta prediksi struktur sekunder RNA), tetapi Wolfgang Haken memberikan algoritma waktu polinomial pertama untuk memutuskan apakah simpul adalah suatu loop sederhana ( Theorie der Normalflächen. Acta Math. 105, 1961, hlm. 245--75). Seingat saya, masih terlalu rumit untuk diimplementasikan beberapa dekade kemudian.

Jika Wikipedia dapat dipercaya, beberapa algoritma lain kemudian diberikan, dan "Memahami kompleksitas algoritma ini adalah bidang studi aktif.".

Anthony Labarre
sumber
4
Haken memberikan algoritma pertama, tetapi tidak berjalan dalam waktu polinomial; pada kenyataannya, tidak ada algoritma poli-waktu (atau hasil NP-hardness) yang diketahui. Pekerjaan yang lebih baru telah mengurangi simpul simpel (melalui formulasi normal-permukaan Haken) ke pemrograman integer, yang biasanya cepat diselesaikan dalam praktek.
Jeffε
3

Dekomposisi pohon , dan mungkin tumpukan Fibonacci .

Peter Boothe
sumber
14
Tumpukan Fibonacci tentu tidak terlalu rumit untuk diterapkan; mereka telah diimplementasikan, dan diuji. Masalahnya dengan mereka adalah bahwa kinerja praktis mereka tidak sebagus beberapa tumpukan lainnya karena faktor konstan yang besar dalam waktu berjalan mereka.
David Eppstein
1
Saya menulis sebuah paket untuk menemukan dekomposisi pohon, dan saya pikir tidak sulit untuk mengimplementasikan yaroslavvb.blogspot.com/2011/01/building-junction-trees.html
Yaroslav Bulatov
2
Kode saya hanyalah dekomposisi heuristik pohon, tidak optimal seperti pendekatan pemrograman cabang-dan-terikat dan dinamis ... Saya kira maksud Anda adalah Bodlaender, "Algoritma Waktu Linear ..."? Saya belum melihat implementasi itu
Yaroslav Bulatov
4
Algoritma linear-waktu Bodlaender menggunakan algoritma pemrograman dinamis dari makalah sebelumnya sebagai subrutin: algoritma yang menghitung komposisi treed yang optimal dalam waktu sekitar , ketika diberi perkiraan komposisi-treed dengan lebar k sebagai input. Saya pikir saya ingat bahwa Hans Bodlaender pernah mengatakan kepada saya bahwa mereka menerapkan algoritma pemrograman dinamis ini yang digunakan sebagai subrutin, tetapi sudah terlalu lambat untuk k = 3. Pemrograman dinamis adalah bagian utama dari algoritma linear-waktu, jadi algoritma Bodlaender tidak terlalu sulit untuk diterapkan, terlalu lambat. 2O(k3)O(n)
Bart Jansen
3
Saya pikir ini adalah upaya implementasi terbaik: hein.roehrig.name/dipl
Diego de Estrada
1

Konstruksi hash yang sempurna ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) akan berlaku untuk setiap kasus penggunaan dengan kunci statis atau yang jarang berubah (misalnya nama domain tingkat atas pada router, kata kunci dalam kompiler, atau nama fungsi di perpustakaan standar) tetapi terakhir kali saya melihat saya tidak dapat menemukan implementasi.

Pencarian parametrik dapat menyelesaikan banyak masalah optimasi yang sulit, termasuk beberapa yang mungkin terlihat seperti NP-hard, dalam waktu polinomial. Makalah bernama Pencarian parametrik yang dibuat membuat implementasi praktis varian pencarian parametrik, tetapi saya masih berpikir itu tidak diimplementasikan dalam perangkat lunak praktis.

The algoritma optimal untuk simpang segmen garis dengan Chazelle dan Edelsbrunner menemukan semua persimpangan dari segmen garis di waktu, tetapi kompleks. CGAL adalah pustaka algoritma geometri yang canggih, tetapi mengimplementasikan algoritma yang lebih sederhana yaitu .n O ( n log n + k ) O ( ( n + k ) log n )knO(nlog⁡n+k)O((n+k)log⁡n)

Kevin A. Wortman
sumber
1
Saya menolak untuk percaya bahwa konstruksi FKS terlalu rumit untuk diimplementasikan. Ini sebenarnya cukup mudah. Mungkin tidak praktis, tetapi tentunya tidak terlalu rumit untuk diterapkan.
Sasho Nikolov