Apakah ada algoritma lain yang waktu berjalannya terburuk adalah eksponensial sementara itu bekerja sangat baik dalam praktik selain Algoritma Simplex?

9

Kami biasanya menyebut algoritma "algoritma yang baik" jika waktu runnning adalah polinomial dalam kasus terburuk. Tetapi dalam beberapa kasus (misalnya algoritma Simplex), meskipun kasus terburuk dari algoritma adalah eksponensial, itu bisa bekerja dengan sangat baik dalam praktiknya.

Adakah contoh (deterministik) untuk situasi ini selain dari algoritma Simplex?

ds.algorithms Arman
sumber
1
Anda mungkin tertarik dengan pertanyaan terkait: cstheory.stackexchange.com/questions/305/…
Radu GRIGore

Jawaban:

13

Algoritma pemecahan SAT modern mampu memecahkan sebagian besar instance dengan cukup cepat, meskipun waktu terburuknya adalah eksponensial. Namun, dalam hal ini, kecepatan praktis lebih merupakan hasil dari rekayasa algoritma selama bertahun-tahun, bukan pada algoritma tunggal yang elegan. Meskipun saya telah memahami bahwa pembelajaran klausa yang didorong oleh konflik menyebabkan lompatan besar dalam kinerja pemecah SAT, peningkatan selanjutnya sering kali dicapai dengan penggunaan berbagai heuristik dalam algoritma secara cerdas.

Janne H. Korhonen
sumber
13

The algoritma -means untuk clustering provably eksponensial bahkan dalam pesawat, tetapi bekerja sangat baik dalam praktek.k

Suresh Venkat
sumber
13

Inferensi tipe Hindley-Milner adalah EKSPTIM-lengkap, tetapi pada program orang biasanya menulisnya cukup dekat dengan linear.

Neel Krishnaswami
sumber
1
Bukankah ini sedikit berbeda? Ingatan saya adalah bahwa kita dapat mengkarakterisasi kondisi yang diperlukan untuk Hindley-Milner berkinerja buruk (memungkinkan bersarang dalam-dalam) dan alasan HM baik dalam praktik adalah bahwa dalam praktiknya, sarang ini dibatasi cukup rendah (biasanya kita indentasi lebih banyak saat berjalan) lebih dalam ke ikatan mengikat dan menjadi gugup ketika kita menuju ke tepi paling kanan layar ...) Memang, saya telah membuat klaim ini dari memori sebelumnya dan saya baru-baru ini tidak dapat memulihkan referensi untuk itu.
Rob Simmons
2
Tidak, itu bukan syarat yang perlu. Anda dapat memberikan urutan let-bindings (tanpa bersarang!) Sedemikian rupa sehingga ukuran kotak dari tipe yang disimpulkan dengan setiap entri tambahan dalam urutan. Lihat cstheory.stackexchange.com/questions/2428/… untuk contoh.
Neel Krishnaswami
Contohnya adalah di SML, dan saya lebih akrab dengan cara OCaml dalam melakukan sesuatu, tetapi jika urutan binding itu "mari", maka saya pikir mereka akan bersarang. Itu hanya karena mereka mendefinisikan fungsi global yang bukan, tetapi ada penyarangan implisit yang terjadi di sini: Definisi yang diberikan memiliki akses ke semua definisi di atasnya dan tidak ada yang di bawah ini.
amnn
1
@ amnn: Bersarang yang dimaksud adalah bersarang memungkinkan dalam bentuk terikat - yaitu, let z = (let y = e in e') in e''sebagai lawan dari let y = e in let z = e' in e''.
Neel Krishnaswami
9

Program Brendan McKay nauty (No AUTomorphisms, Yes?) Memecahkan masalah pelabelan kanonik grafik (sekaligus memecahkan masalah Graph Isomorphism dan Graph Automorphism) dan memiliki kinerja kasus terburuk yang eksponensial (Miyazaki, 1996). Namun, ini bekerja sangat cepat untuk sebagian besar grafik, terutama yang memiliki beberapa otomorfisme.

Secara khusus, algoritma dimulai dengan mempartisi simpul dengan derajat, kemudian dengan derajat antara masing-masing bagian. Ketika proses ini stabil, pilihan harus dibuat untuk membedakan simpul di bagian non-sepele, dan ini mengarah pada perilaku eksponensial. Di sebagian besar grafik, kedalaman prosedur percabangan ini kecil.

Derrick Stolee
sumber
Saya pikir bahari juga menggunakan beberapa keacakan untuk membantu dalam penyempurnaan? Dalam hal ini, ini mungkin sangat analog dengan algoritma simpleks (meskipun tidak jelas ada gagasan analisis yang diperhalus untuk isomorfisme grafik).
Joshua Grochow
1
Itu tidak menggunakan keacakan, karena perlu membuat label kanonik yang konsisten. Namun, ia dapat menggunakan prosedur invers-vertex yang dibuat khusus untuk membantu mempartisi simpul. Kadang-kadang invarian ini terlihat acak bagaimana ia diproduksi (seringkali, ini adalah fungsi yang rumit pada urutan tingkat-jarak), tapi itu hanya untuk mengurangi tabrakan.
Derrick Stolee
1
Vertex-invariant ini dapat dibandingkan dengan aturan anti-bersepeda dari algoritma simpleks.
Derrick Stolee
4

Beberapa algoritma untuk permainan stokastik sederhana bekerja dengan baik dalam praktiknya, meskipun mereka memiliki waktu berjalan terburuk secara eksponensial. Tentu saja, masalah ini dalam beberapa hal terkait dengan pemrograman linier, meskipun tidak diketahui dalam waktu polinomial.

Peter Shor
sumber
1

Ada algoritma untuk menemukan kesetimbangan Nash campuran yang mirip dengan algoritma simpleks untuk piringan hitam. (Saya lupa namanya.) Ia memiliki kompleksitas kasus terburuk yang eksponensial, tetapi saya memiliki ingatan yang samar bahwa sering berperilaku baik dalam praktik.

Warren Schudy
sumber
Apakah yang Anda maksud adalah algoritma Lemke-Howson?
Rahul Savani
1

Tempat sampah (banyak varian) adalah masalah yang kerumitannya dikenal sebagai NP-hard:

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

Namun, banyak heuristik ketika diterapkan pada versi "praktis" sangat baik. Untuk pengemasan bin 1 dimensi beberapa heuristik ini, seperti first-fit; penurunan fit pertama; paling cocok; penurunan paling cocok sangat menarik sebagai topik untuk ditunjukkan kepada siswa. Siswa sering dapat menemukan beberapa heuristik dasar untuk diri mereka sendiri.

Joseph Malkevitch
sumber
Ada banyak contoh bahkan jika masalahnya adalah NP-lengkap, algortihms sederhana dapat mengatasinya. Terutama dengan algoritma perkiraan. Tapi saya sebenarnya mencari algoritma waktu eksponensial, contoh Anda terkait dengan masalah sulit yang mudah diselesaikan dengan algoritma sederhana. Mungkin ada algoritma waktu eksponensial untuk menyelesaikan pengemasan Bin (atau masalah lain) secara tepat; dan dalam praktiknya dibutuhkan waktu polinomial.
Arman
0

Algoritma kegigihan (berasal dari Edelsbrunner-Letscher-Zomorodian, dengan banyak variasi sejak itu) adalah kasus kubik terburuk, tetapi tampaknya dari eksperimen biasanya berjalan dalam waktu linier.


sumber