Untuk algoritma apa ada kesenjangan besar antara analisis teoritis dan kenyataan?

52

Dua cara menganalisis efisiensi suatu algoritma adalah

  1. untuk menempatkan batas atas asimptotik pada runtime, dan
  2. untuk menjalankannya dan mengumpulkan data eksperimental.

Saya ingin tahu apakah ada kasus yang diketahui di mana ada kesenjangan yang signifikan antara (1) dan (2). Maksud saya, baik (a) data eksperimental menunjukkan asimtotik yang lebih ketat atau (b) ada algoritma X dan Y sehingga analisis teoritis menunjukkan bahwa X jauh lebih baik daripada Y dan data eksperimental menunjukkan bahwa Y jauh lebih baik daripada X.

Karena eksperimen biasanya mengungkapkan perilaku kasus rata-rata, saya mengharapkan jawaban paling menarik untuk merujuk pada batas atas kasus rata-rata. Namun, saya tidak ingin mengesampingkan kemungkinan jawaban menarik yang membicarakan batasan yang berbeda, seperti jawaban Noam tentang Simplex.

Sertakan struktur data. Silakan masukkan satu algo / ds per jawaban.

Radu GRIGore
sumber
Akan membantu jika Anda mengklarifikasi batas atas seperti apa yang sedang Anda bicarakan. Apakah Anda hanya berbicara tentang masalah yang ada kesenjangan signifikan antara batas atas dan bawah yang paling dikenal untuk kompleksitas waktu terburuk? Atau apakah Anda juga memasukkan masalah yang batas ketatnya pada kompleksitas waktu terburuk diketahui, tetapi waktu berjalan yang khas jauh lebih cepat? Mungkin lebih menarik untuk mempertimbangkan kompleksitas yang dihaluskan daripada kompleksitas yang terburuk. Hasil eksperimental pada input 'tipikal' atau input acak tidak banyak membantah keberadaan input patologis.
James King
Dalam hal ini saya pikir ada dua pertanyaan yang harus ditanyakan secara terpisah: satu tentang kesenjangan antara kompleksitas kasus terburuk dan kompleksitas kasus rata-rata / smoothed, dan satu tentang kesenjangan antara kompleksitas kasus rata-rata / kompleksitas halus dan hasil eksperimen praktis. Sunting: Anda membuat pengeditan mengatasi ini ketika saya sedang menulis komentar saya :)
James King

Jawaban:

37

Contoh yang paling mencolok tentu saja adalah metode Simplex yang berjalan cepat dalam praktiknya, menunjukkan poli-waktu, tetapi membutuhkan waktu yang eksponensial dalam teori. Dan Spielman baru saja mendapatkan penghargaan Nevanlinna untuk menjelaskan misteri ini.

Secara lebih umum, banyak contoh Integer-programming dapat diselesaikan dengan cukup baik dengan menggunakan IP-solver standar, misalnya lelang kombinatorial untuk sebagian besar distribusi yang dicoba pada input berukuran besar dapat diselesaikan - http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Noam
sumber
3
Apakah ada keluarga eksplisit dari program linier yang ditemukan untuk simpleks yang membutuhkan waktu eksponensial?
Memilih
1
Sejauh yang saya mengerti, ada banyak keluarga eksplisit yang membutuhkan waktu eksponensial (misalnya, beeing pertama yang diberikan oleh Klee dan Minty: "Seberapa baik algoritma simpleks?", 1972). Namun, pilihan aturan pivot relevan untuk hasil ini. Saya kira sebagian besar referensi untuk hasil ini dapat ditemukan di koran Spielman dan Teng ( arxiv.org/abs/cs/0111050 ).
MRA
ada lowerbounds untuk beberapa aturan berputar khusus dalam makalah ini cs.au.dk/~tdh/papers/random_edge.pdf
Igor Shinkar
26

Pangkalan Groebner . Waktu berjalan terburuk adalah eksponensial ganda (dalam jumlah variabel). Namun dalam praktiknya, terutama untuk masalah yang terstruktur dengan baik, algoritma F4 dan F5 efektif (yaitu berakhir dengan cepat). Ini masih merupakan bidang penelitian aktif untuk mencari tahu apa dugaan yang tepat bahkan tentang waktu berjalan rata-rata atau yang diharapkan. Dugaan bahwa itu terkait, entah bagaimana, dengan volume Newton polytope dari idealnya.

Jacques Carette
sumber
Rata-rata / diharapkan dalam distribusi apa? Saya pikir bahkan mendefinisikan waktu berlari yang diharapkan sulit untuk masalah aljabar ...
Joshua Grochow
1
Saya tidak tahu untuk kasus diselesaikan dengan cepat dengan metode F4 dan F5, tetapi cukup mudah untuk membangun sistem polinomial dengan banyak variabel dan tingkat rendah yang mengkodekan contoh SAT. Dalam kasus seperti itu tidak diketahui oleh saya bahwa algoritma mengungguli DPLL / DPLL +. Saya benar-benar ingin tahu lebih banyak tentang hasil eksperimen tentang hal-hal ini!
MassimoLauria
@ Yosua: pada titik ini, distribusi apa pun yang memungkinkan hasil ... @ Massimo: menyandikan masalah X sebagai contoh Y hampir tidak pernah mengalahkan algoritma khusus untuk X! Tetapi GB dan DPLL pada dasarnya setara, jadi saya akan sangat terkejut melihat perbedaan yang efektif.
Jacques Carette
1
@ Massimo: Ya, perhitungan GB adalah NP-Hard. Tergantung formulasi. Bahkan, sebagian besar pertanyaan (penyelesaian, keanggotaan ideal, bidang tertutup secara aljabar vs boolean) adalah PSPACE lengkap atau lebih buruk (EXPSPACE selesai). Yang mengatakan bahwa perhitungan GB diharapkan akan jauh lebih sulit daripada masalah NP-lengkap (dan bahkan rata-rata, algoritma apa pun untuk mereka seperti F5 kemungkinan besar tidak akan mengungguli DPLL).
Mitch
22

O(2((nlogn)))

Saya tidak tahu apakah ada hasil formal rata-rata / merapikan kerumitan masalah, tetapi saya ingat pernah membaca bahwa ada - mungkin orang lain bisa berpura-pura menunjukkan hasil resmi. Tentu saja, ada banyak bukti eksperimental dan banyak pemecah masalah yang cepat. Saya juga ingin tahu apakah properti ini meluas ke anggota keluarga lengkap GI lainnya.

Anand Kulkarni
sumber
1
O(2nlogn)
2
Oh! Mungkin Anda memikirkan Babai-Kucera, yang memberikan algoritma kasus-rata-rata linear-waktu untuk GI: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua Grochow
Ya, Babai-Kucera adalah satu-satunya! Terima kasih untuk referensi.
Anand Kulkarni
20

Dari David Johnson, perbedaan dalam rasio pendekatan teoritis dan eksperimental: Travelling Salesman Problem: Studi Kasus dalam Optimalisasi Lokal, DS Johnson dan LA McGeoch . Dalam makalah ini mereka memberikan bukti eksperimental asimptotik (karena percobaan berjalan hingga ukuran N = 10.000.000!) Yang menentang asimtotik teoritis: Algoritma "Greedy" atau "Multi-Fragmen" karya Jon Bentley (rasio aproksimasi kasus terburuk setidaknya logN / loglogN) mengalahkan Insertion Terdekat dan MST Ganda, yang keduanya memiliki rasio perkiraan kasus terburuk 2.

Joshua Grochow
sumber
20

Contoh lain yang belum dipahami dengan baik sampai saat ini adalah waktu berjalan dari algoritma k-means Lloyd , yang (dari sudut pandang praktis) telah menjadi algoritma pengelompokan pilihan selama lebih dari 50 tahun. Hanya baru-baru ini, pada tahun 2009, telah terbukti (oleh Vattani ) bahwa dalam kasus terburuk, algoritma Lloyd membutuhkan sejumlah iterasi yang eksponensial dalam jumlah titik input. Di sisi lain, pada saat yang sama, analisis yang dihaluskan (oleh Arthur, Manthey dan Röglin ) membuktikan bahwa jumlah iterasi yang dihaluskan hanyalah polinomial, yang menjelaskan kinerja empiris.

MRA
sumber
10

Traversal, deque, dan split akibat wajar dari dugaan optimalitas dinamis untuk pohon hamparan adalah contoh dari kesenjangan tersebut. Eksperimen mendukung klaim untuk waktu linier, tetapi tidak ada bukti yang diketahui.

Radu GRIGore
sumber
3
Seth Pettie membuktikan bahwa operasi n deque membutuhkan waktu tidak lebih dari O (n alpha * (n)), di mana "alpha *" adalah fungsi Ackermann terbalik yang diulang, yang merupakan celah yang cukup kecil.
jbapple
9

Ada sedikit masalah dengan pertanyaan itu. Sebenarnya ada lebih dari dua cara menganalisis suatu algoritma, dan salah satu cara teoretis yang telah diabaikan adalah waktu yang diharapkan, bukan waktu yang terburuk. Ini benar-benar perilaku kasus rata-rata ini yang relevan untuk melakukan percobaan. Berikut adalah contoh yang sangat sederhana: Bayangkan Anda memiliki algoritma untuk input ukuran n, yang membutuhkan waktu n untuk setiap input ukuran yang mungkin kecuali untuk satu input spesifik dari setiap panjang yang membutuhkan waktu 2 ^ n. Mendengar run time case terburuk adalah eksponensial, tetapi case rata-rata adalah [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n yang batas ke n. Jelas kedua jenis analisis ini memberikan jawaban yang sangat berbeda, tetapi ini diharapkan karena kami menghitung jumlah yang berbeda.

Dengan menjalankan percobaan beberapa kali, bahkan jika kami mengambil waktu berjalan terpanjang untuk sampel, kami masih hanya mengambil sampel sebagian kecil dari ruang input yang mungkin, dan jadi jika instans keras jarang terjadi maka kami kemungkinan akan melewatkannya .

Relatif mudah untuk membangun masalah seperti itu: Jika n / 2 bit pertama semuanya nol, daripada menyelesaikan instance 3SAT yang dienkode dengan n / 2 bit terakhir. Kalau tidak tolak. Ketika n bertambah besar, masalah memiliki waktu berjalan yang kira-kira sama dalam kasus terburuk sebagai algoritma yang paling efisien untuk 3SAT, di mana waktu lari rata-rata dijamin sangat rendah.

Joe Fitzsimons
sumber
Saya sudah menjawab James King di atas bahwa saya mengharapkan jawaban yang paling menarik adalah tentang runtime yang diharapkan. Saya akan mengedit pertanyaan untuk membuatnya lebih terlihat.
Radu GRIGore
9

Inferensi tipe Damas-Milner terbukti lengkap untuk waktu eksponensial, dan ada kasus yang mudah dibangun dengan ledakan eksponensial dalam ukuran hasilnya. Meskipun demikian, pada sebagian besar input dunia nyata berperilaku secara linier efektif.

sclv
sumber
Apakah ada referensi yang akan Anda rekomendasikan untuk hasil ini? Saya ingin membaca lebih lanjut tentang itu.
Radu GRIGore
1
Saya belum membacanya sendiri, tetapi makalah yang paling sering dikutip adalah Harry G. Mairson, "Decidability dari mengetik ML selesai untuk waktu eksponensial deterministik," Simposium ke-17 tentang Prinsip-prinsip Bahasa Pemrograman (1990).
sclv
9

PTAS untuk Steiner tree dalam grafik planar memiliki ketergantungan konyol pada epsilon. Namun ada implementasi yang menunjukkan kinerja yang sangat baik dalam praktiknya.

zotachidil
sumber
8

Pairing heaps, from [1] - mereka mengimplementasikan heaps, di mana insert dan gabungan memiliki O (log n) kompleksitas yang diamortisasi, tetapi dikira sebagai O (1). Dalam praktiknya, mereka sangat efisien, terutama untuk pengguna gabungan.

Saya baru saja menemukan mereka hari ini ketika membaca Sec. 5.5 dari buku C. Okasaki "Struktur data murni fungsional", jadi saya pikir saya harus membagikan info tentangnya.

[1] Fredman, ML, Sedgewick, R., Sleator, DD, dan Tarjan, RE 1986. Tumpukan pasangan: bentuk baru tumpukan penyesuaian diri. Algorithmica 1, 1 (Jan. 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Blaisorblade
sumber
Sudah ada beberapa kemajuan sejak Okasaki, dan sekarang ada tumpukan (keharusan) pairing dengan O (0) berbaur, O (1) masukkan dan temukanMin, O (lg lg n) kurangiKey, dan O (lg n) deleteMin: arxiv. org / abs / 0903.4130 . Tumpukan ini menggunakan mekanisme pemasangan yang berbeda dari tumpukan pemasangan asli Fredman et al.
jbapple
7

Terkait dengan komentar ilyaraz tentang cabang dan terikat, Pataki et al. menunjukkan bahwa reduksi cabang dan basis ditambah kisi dapat menyelesaikan hampir semua IP acak dalam polytime.

Marco
sumber
6

Heuristik Lin-Kernighan untuk TSP ("Heuristik yang efektif untuk masalah salesman keliling", Operations Research 21: 489-516, 1973) sangat berhasil dalam praktiknya, tetapi masih kekurangan analisis kasus rata-rata atau perataan untuk menjelaskan kinerjanya . Sebaliknya, ada analisis yang mulus dari heuristik 2-pilihan untuk TSP oleh Matthias Englert, Heiko Röglin, dan Berthold Vöcking (Algorithmica, untuk muncul).

Bodo Manthey
sumber
5

Ada banyak algoritma cabang dan terikat yang sangat cepat dan efisien untuk berbagai masalah NP-hard yang tidak dapat kita analisis dengan teliti: TSP, pohon Steiner, pengemasan bin dan sebagainya.

Ω(nm)

ilyaraz
sumber
Maksudmu O (mn), atau aku bingung?
Radu GRIGore
O(nmlog(n2/m))