Kapan dua algoritma dikatakan “mirip”?

Saya tidak bekerja dalam teori, tetapi pekerjaan saya membutuhkan membaca (dan memahami) makalah teori sesekali. Setelah saya memahami (set) hasil, saya membahas hasil ini dengan orang-orang yang bekerja dengan saya, yang sebagian besar tidak bekerja secara teori juga. Selama salah satu diskusi tersebut, pertanyaan berikut muncul:

Kapan ada yang mengatakan bahwa dua algoritma yang diberikan "mirip"?

Apa yang saya maksud dengan "mirip"? Katakanlah dua algoritme dikatakan serupa jika Anda dapat membuat salah satu dari klaim berikut dalam makalah tanpa membingungkan / mengganggu pengulas mana pun (disambut dengan definisi yang lebih baik):

Klaim 1. "Algoritma $A$ , yang mirip dengan algoritma , juga memecahkan masalah "$B$$X$

Klaim 2. "Algoritme kami mirip dengan Algoritma "$C$

Biarkan saya membuatnya sedikit lebih spesifik. Misalkan kita bekerja dengan algoritma grafik. Pertama, beberapa kondisi yang diperlukan untuk kedua algoritme agar serupa:

1. Mereka harus memecahkan masalah yang sama.
2. Mereka harus memiliki ide intuitif tingkat tinggi yang sama.

Sebagai contoh, berbicara tentang traversal grafik, traversal lebar-pertama dan kedalaman-pertama memenuhi dua kondisi di atas; untuk perhitungan jalur terpendek, luasnya pertama dan algoritma Dijkstra memenuhi dua kondisi di atas (tentu saja, pada grafik tidak berbobot); dll.

Apakah ini juga kondisi yang memadai? Lebih khusus, anggap dua algoritma memenuhi kondisi yang diperlukan untuk menjadi serupa. Apakah Anda memang memanggil mereka serupa, jika

1. mereka memiliki kinerja asimptotik yang berbeda?
2. untuk kelas grafik khusus, satu algoritma memerlukan waktu sementara yang lain membutuhkan waktu ?$\Omega(n)$$O(n^{1/3})$
3. mereka memiliki kondisi pemberhentian yang berbeda? (ingat, mereka memecahkan masalah yang sama)
4. langkah pra-pemrosesan berbeda dalam dua algoritma?
5. kompleksitas memori berbeda dalam dua algoritma?

Sunting: Pertanyaannya jelas sangat tergantung konteks dan subyektif. Saya berharap bahwa lima kondisi di atas, akan memungkinkan mendapatkan beberapa saran. Saya senang untuk memodifikasi pertanyaan lebih lanjut dan memberikan rincian lebih lanjut, jika diperlukan untuk mendapatkan jawaban. Terima kasih!

Ini adalah masalah yang sulit untuk memberikan definisi yang koheren tentang "Algoritma A mirip dengan Algoritma B". Untuk satu, saya tidak berpikir bahwa "mereka harus menyelesaikan masalah yang sama" adalah kondisi yang diperlukan. Seringkali ketika seseorang mengatakan dalam sebuah makalah bahwa "algoritma dari Theorem 2 mirip dengan algoritma B di Theorem 1 ", algoritma A sebenarnya memecahkan masalah yang berbeda dari B , tetapi memiliki beberapa modifikasi kecil untuk menangani masalah baru .$A$$2$$B$$1$$A$$B$

Bahkan mencoba menentukan apa artinya dua algoritma menjadi sama adalah masalah yang menarik dan sulit. Lihat kertas "Kapan dua algoritma itu sama?" http://research.microsoft.com/~gurevich/Opera/192.pdf

Lebih sering daripada tidak, itu berarti "Saya tidak ingin menuliskan Algoritma B secara rinci, karena semua detail menarik hampir identik dengan yang ada di Algoritma A, dan saya tidak ingin melampaui batas 10 halaman, dan lagi pula tenggat waktu pengiriman adalah tiga jam. "

Jika Anda bermaksud "serupa" dalam arti sehari-hari, saya pikir jawaban JeffE menangkap apa yang beberapa orang maksudkan.

Dalam arti teknis, itu tergantung pada apa yang Anda pedulikan. Jika hanya kompleksitas waktu asimptotik yang Anda pedulikan, perbedaan antara rekursi dan iterasi mungkin tidak masalah. Jika hanya kemampuan komputasi yang Anda pedulikan, perbedaan antara variabel penghitung dan tumpukan satu simbol tidak penting.

Untuk membandingkan algoritma, langkah pertama adalah membuat gagasan tentang kesetaraan menjadi tepat. Secara intuitif, biarkan menjadi ruang algoritma dan M menjadi ruang objek matematika dan s e m : A → M menjadi encoding fungsi yang s e m ( P ) adalah makna dari algoritma P . Ruang M dapat berisi apa saja mulai dari jumlah variabel dalam algoritme Anda, hingga grafik keadaannya atau kompleksitas waktunya. Saya tidak percaya ada gagasan absolut tentang apa yang bisa M. Diberikan $A$$M$$\mathit{sem}: A \to M$$\mathit{sem}(P)$$P$$M$$M$$M$meskipun, kita dapat mengatakan dua algoritma setara jika sama dengan s e m ( Q ) . Izinkan saya menambahkan bahwa saya pikir masing-masing dari lima kriteria yang Anda sebutkan dapat diformalkan secara matematis dengan cara ini.$\mathit{sem}(P)$$\mathit{sem}(Q)$

Jika kita ingin berbicara tentang suatu algoritma yang lebih umum daripada yang lain (atau suatu algoritma yang memperbaiki yang lain), saya akan memberi lebih banyak struktur. Bayangkan bahwa ( M , ⊑ ) adalah himpunan yang diurutkan sebagian dan urutan x ⊑ y menyandikan bahwa x adalah objek yang lebih didefinisikan daripada y . Misalnya, jika M berisi kumpulan jejak suatu algoritma dan ⊑ diatur penyertaan, s e m ( P ) ⊑ s e m ( Q ) berarti bahwa setiap jejak $M$$(M, \sqsubseteq)$$x \sqsubseteq y$$x$$y$$M$$\sqsubseteq$$\mathit{sem}(P) \sqsubseteq \mathit{sem}(Q)$$P$adalah jejak . Kita bisa menafsirkan ini sebagai mengatakan bahwa P lebih deterministik dari Q .$Q$$P$$Q$

Selanjutnya, kita bisa bertanya apakah mungkin untuk mengukur seberapa dekat dua algoritma itu. Dalam hal ini, saya akan membayangkan bahwa harus diberkahi dengan metrik. Kemudian, kita dapat mengukur jarak antara objek matematika yang diwakili oleh dua algoritma. Kemungkinan selanjutnya adalah memetakan algoritma untuk mengukur ruang atau ruang probabilitas dan membandingkannya menggunakan kriteria lain.$M$

Secara umum, saya akan bertanya - apa yang Anda pedulikan (dalam istilah intuitif), apa saja objek matematika yang mewakili properti intuitif ini, bagaimana saya bisa memetakan dari algoritma ke objek-objek ini, dan apa struktur ruang ini? Saya juga akan bertanya apakah ruang objek menikmati struktur yang cukup untuk mengakui gagasan kesamaan. Ini adalah pendekatan yang akan saya ambil dari perspektif semantik bahasa pemrograman. Saya tidak yakin apakah Anda menganggap pendekatan ini menarik, mengingat budaya pemikiran yang sangat berbeda dalam ilmu komputer.

Sejalan dengan jawaban Jeff, dua algoritma serupa jika penulis salah satunya mengharapkan bahwa penulis yang lain mungkin akan meninjau makalahnya.

Tapi bercanda samping, dalam komunitas teori, saya akan mengatakan bahwa apa algoritma masalah A adalah penyelesaian agak tangental apakah itu "mirip" dengan algoritma B, yang mungkin memecahkan masalah yang sama sekali berbeda. A mirip dengan B jika "bekerja" karena ide teoretis utama yang sama. Misalnya, apakah ide utama dalam kedua algoritma tersebut adalah Anda dapat memproyeksikan data ke dalam ruang dimensi yang jauh lebih rendah, mempertahankan norma dengan lemma Johnson-Lindenstrauss, dan kemudian melakukan pencarian brute-force? Kemudian algoritma Anda mirip dengan algoritma lain yang melakukan ini, tidak masalah apa pun yang Anda pecahkan. Ada sejumlah kecil teknik algoritme tugas berat yang dapat digunakan untuk menyelesaikan berbagai masalah, dan saya akan berpikir bahwa teknik ini membentuk centroid dari banyak set algoritma "mirip".

Pertanyaan yang sangat menarik, dan kertas Ryan yang sangat bagus!

Saya benar-benar setuju dengan gagasan bahwa membuat penilaian tentang kesamaan keseluruhan antara algoritma terutama merupakan penilaian nilai subyektif. Sementara dari sudut pandang teknis ada sejumlah fitur yang diamati dengan cermat untuk memutuskan kesamaan algoritma, pada akhirnya, itu juga masalah selera pribadi. Saya akan mencoba memberikan deskripsi tentang pentingnya kedua sisi dari koin yang sama sambil merujuk pada poin-poin tertentu dari pertanyaan Anda:

Dari sudut pandang teknis:

1. Ryan sudah menunjukkan bahwa kedua algoritma harus menyelesaikan masalah yang sama . Seseorang dapat melangkah lebih jauh dan menggeneralisasikan gagasan ini dengan mengatakan bahwa biasanya cukup untuk membuktikan bahwa ada transformasi polinomial dari contoh yang sama yang dapat dimengerti oleh algoritma A sehingga algoritma B dapat menanganinya. Namun, ini sebenarnya sangat lemah. Saya lebih suka memikirkan kesamaan dalam arti yang lebih kuat.
2. Namun, saya tidak akan pernah berharap untuk dua algoritma setara memiliki ide intuitif yang sama --- walaupun, sekali lagi, ini adalah definisi yang tidak mudah untuk ditangkap. Lebih dari itu, sering terjadi bahwa algoritma yang dianggap serupa tidak mengikuti alasan utama. Pertimbangkan misalnya beberapa algoritma pengurutan yang, bagaimanapun, berasal dari cara yang berbeda mengikuti ide yang berbeda. Sebagai contoh ekstrim, pertimbangkan algoritma genetika yang biasanya dianggap oleh komunitas matematika hanya sebagai proses stokastik (dan karena itu mereka setara dalam pandangan mereka) yang kemudian dimodelkan dan dianalisis dengan cara yang sangat berbeda.
3. Selain itu, saya bahkan akan menggeneralisasikan gagasan ini untuk mengatakan bahwa teknis lainnya seperti kondisi penghentian atau tahap pra-pemrosesan tidak terlalu penting. Tapi ini tidak selalu terjadi. Lihat misalnya Algoritma Dijkstra versus Pencarian Biaya Seragam atau Kasus Terhadap Algoritma Dijkstra . Kedua algoritma sangat dekat sehingga kebanyakan orang tidak mengatakan perbedaannya, namun perbedaannya (menjadi teknis) sangat penting bagi penulis makalah itu. Sama halnya dengan langkah pra-pemrosesan. Jika Anda terbiasa dengan$N$-Tuangkan, lalu amati bahwa huruf A$^*$Algoritma pencarian-seperti menggunakan jarak Manhattan atau $(N^2-1)$database pola aditif sebenarnya akan memperluas jumlah node yang sama dalam urutan yang sama persis, dan itu membuat kedua algoritma (dan heuristik mereka) menjadi sangat setara dalam arti yang sangat kuat, sedangkan pendekatan pertama tidak memiliki pra-pemrosesan dan yang kedua memiliki overhead yang signifikan sebelum mulai memecahkan contoh tertentu. Namun, segera setelah Pola Database Anda mempertimbangkan interaksi yang lebih simulaten ada perbedaan besar dalam kinerja di antara mereka, sehingga mereka pasti berbeda ide / algoritma.
4. Sebagai soal fakta, saya berpikir bahwa kebanyakan orang akan menilai algoritma untuk tujuan dan kinerja mereka . Oleh karena itu, kinerja asimptotik adalah metrik yang baik untuk alasan tentang kesamaan antar program. Namun, ingatlah bahwa kinerja ini tidak selalu merupakan kasus tipikal sehingga jika dua algoritma memiliki kinerja asimptotik yang sama tetapi berperilaku berbeda dalam praktiknya, maka Anda mungkin akan menyimpulkan bahwa mereka berbeda. Bukti kuat dalam hal ini adalah bahwa kedua algoritma memiliki kinerja yang sama baik pada waktu dan memori (dan ini, seperti kata Suresh, membuat DFS dan BFS terlihat berbeda). Jika pernyataan ini tidak terdengar meyakinkan bagi Anda, silakan merujuk ke buku yang sangat bagus (dan sangat direkomendasikan): Programming the Universeoleh Seth Lloyd. Dalam halaman 189 ia merujuk ke daftar dengan lebih dari 30 ukuran kompleksitas yang dapat digunakan untuk menganggap algoritma sebagai berbeda.

Jadi apa yang membuat algoritma menjadi serupa / berbeda? Dalam pandangan saya (dan ini murni spekulatif), perbedaan utama adalah tentang apa yang mereka sarankan kepada Anda. Banyak, banyak (banyak!) Algoritma berbeda hanya dalam beberapa teknis ketika melayani untuk tujuan yang sama sehingga kasus khas berbeda untuk rentang input yang berbeda. Namun, perbedaan terbesar adalah (menurut saya) apa yang mereka sarankan kepada Anda. Algoritma memiliki kemampuan yang berbeda dan oleh karena itu kekuatan dan kelemahan mereka sendiri. Jika dua algoritma terlihat seperti sama tetapi mungkin diperluas dengan cara yang berbeda untuk mengatasi kasus yang berbeda maka saya akan menyimpulkan bahwa mereka berbeda. Namun, sering kali, dua algoritme terlihat sangat mirip sehingga Anda akan menganggapnya sama ... sampai seseorang tiba membuat perbedaan utama dan tiba-tiba, mereka benar-benar berbeda!

Maaf, tanggapan saya pada akhirnya begitu lama ...

Bersulang,

Penyebutan kesamaan tanpa mendefinisikan kesamaan metrik tidak didefinisikan dengan baik. Ada banyak cara di mana dua algoritma dapat serupa:

Quicksort dan Mergesort memecahkan masalah yang sangat mirip, tetapi mereka menggunakan algoritma yang berbeda untuk melakukannya. Mereka memiliki kompleksitas algoritmik yang serupa (meskipun kinerja kasus terburuk dan penggunaan memori dapat bervariasi). Quicksort dan Mergesort keduanya mirip dengan Bubblesort, namun Bubblesort memiliki metrik kinerja yang sangat berbeda. Jika Anda mengabaikan statistik kompleksitas Quicksort, Mergesort dan Bubblesort semuanya berada dalam kelas ekivalensi yang sama. Namun, jika Anda sama sekali peduli tentang kompleksitas algoritmik, maka Quicksort dan Mergesort jauh lebih mirip satu sama lain daripada keduanya adalah Bubblesort.

Pemrograman dinamis Smith-Waterman dan upaya perbandingan urutan HMM untuk memecahkan masalah menyelaraskan dua urutan. Namun, mereka mengambil input berbeda. Smith-Waterman mengambil dua sekuens sebagai input, dan perbandingan sekuens HMM mengambil HMM dan sekuens sebagai input. Kedua keselarasan urutan output. Dalam hal memotivasi ide, keduanya mirip dengan jarak sunting Levenshtein , tetapi hanya pada tingkat yang sangat tinggi.

Berikut adalah beberapa kriteria yang dengannya dua algoritma dapat disebut serupa:

1. Jenis input / output
2. Kompleksitas Algoritma / Memori
3. Asumsi tentang jenis input (mis. Hanya angka positif atau stabilitas floating point)
4. Hubungan bersarang (mis. Beberapa algoritma adalah kasus khusus dari yang lain)

Keputusan kritis tentang arti kesamaan tetap ada. Terkadang Anda peduli dengan kompleksitas suatu algoritma, terkadang Anda tidak. Karena definisi kesamaan tergantung pada konteks diskusi, istilah "algoritma yang serupa" tidak didefinisikan dengan baik.