Fondasi teoretis Divide and Conquer

Ketika datang ke desain algoritma, orang sering menggunakan teknik berikut:

• Pemrograman Dinamis
• Strategi Serakah
• Membagi dan menaklukkan

Sementara untuk dua metode pertama, ada dasar-dasar teoretis yang terkenal, yaitu Prinsip Optimalitas Bellman dan teori matroid (resp. Greedoid), saya tidak dapat menemukan kerangka kerja umum untuk algoritma berdasarkan D&C.

Pertama, saya menyadari sesuatu yang kami (atau lebih tepatnya, prof) perkenalkan di kelas pemrograman fungsional, yang disebut "kerangka algoritmik", yang muncul dalam konteks combinator. Sebagai contoh perjanjian ini, kami memberikan kerangka kerja untuk algoritma D&C sebagai berikut:

Definisi : Misalkan adalah perangkat yang tidak kosong. Kami menyebut elemen solusi S , dan elemen P : = P ( A ) (yaitu, himpunan bagian A ) disebut sebagai masalah . Kemudian, kerangka D & C adalah tupel 4 ( P β , β , D , C ) , di mana:$A,S$$S$ $P:=\mathfrak{P}(A)$$A$$(P_\beta, \beta, \mathcal{D}, \mathcal{C})$

• adalah predikat atas serangkaian masalah dan kami mengatakan bahwa masalah p adalahdasarjika P β ( p ) berlaku.$P_\beta$$p$$P_\beta(p)$
• adalah pemetaan P β → S yang memberikan solusi untuk setiap masalah dasar.$\beta$$P_\beta \rightarrow S$
• adalah pemetaan P → P ( P ) yang membagi setiap masalah menjadi satu set submasalah.$\mathcal{D}$$P \rightarrow \mathfrak{P}(P)$
• adalah pemetaan P × P ( S ) → S yang menggabungkan solusi (tergantung pada jenis "masalah pivot") dari subproblem untuk menghasilkan solusi.$\mathcal{C}$$P\times \mathfrak{P}(S) \rightarrow S$

Kemudian, untuk kerangka yang diberikan dan masalah p , fungsi generik berikut f s : P → S menghitung solusi (dalam pengertian formal) untuk p :$s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$$p$$f_s: P\rightarrow S$$p$

$f_s(p)= \left\{ \begin{array}{l l} \beta(p) & \quad \text{if $p$ is basic}\\ \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise} \end{array} \right.$

di mana pada baris kedua kita menggunakan notasi untuk himpunan bagian X dari kodomain pemetaan f .$f(X) := \{f(x) : x\in X\}$$X$$f$

Namun, kami tidak meneliti lebih lanjut sifat masalah "struktural" yang mendasarinya yang dapat dirumuskan dengan cara ini (seperti yang saya katakan, itu adalah kelas pemrograman fungsional dan ini hanya contoh kecil). Sayangnya, saya tidak dapat menemukan referensi lebih lanjut tentang pendekatan ini. Karenanya saya tidak berpikir definisi di atas cukup standar. Jika seseorang mengenali apa yang telah saya nyatakan di atas, saya akan senang tentang artikel terkait.

Kedua, untuk strategi serakah kami memiliki hasil yang terkenal bahwa masalah diselesaikan dengan benar oleh algoritma serakah umum jika dan hanya jika solusinya merupakan matroid tertimbang. Apakah ada hasil yang serupa untuk algoritma D & C (tidak harus berdasarkan metode yang diuraikan di atas)?

Perlakuan formal (agak menyerupai model yang diajukan dalam pertanyaan) dari subjek menggunakan apa yang disebut pseudo-morfisme (yaitu, fungsi yang hampir morfisme, dengan beberapa pra-dan pasca-perhitungan dilakukan), serta pertimbangan kompleksitas analisis dan implementasi paralel dari algoritma tersebut diberikan dalam:

Model aljabar untuk divide-and-conquer dan paralelismenya oleh Zhijing G. Mou dan Paul Hudak (dalam The Journal of Supercomputing , Volume 2, Issue 3, hlm. 257-278, November 1988)

Saya tidak menyadari sesuatu yang konkret seperti Prinsip Optimalitas Bellman untuk algoritma Divide and Conquer. Namun, dasar yang mendasari membagi dan menaklukkan bagi saya tampaknya definisi rekursif (atau induktif) dari input masalah dan kemudian sarana untuk menggabungkan solusi untuk masalah ke solusi yang lebih besar. Wawasan utama di sini adalah memikirkan input masalah secara rekursif dan memanfaatkannya menjadi algoritme D&C rekursif.

$n$

• $n=0$
• $n=1$
• $n>1$$\lceil{\frac{n}{2}}\rceil$$\lfloor{\frac{n}{2}}\rfloor$

$n\leq1$

Penting untuk dicatat bahwa ini tidak selalu mengarah pada apa yang Anda harapkan dari algoritma D&C. Kita dapat mendefinisikan struktur array sebagai berikut:

• $n=0$
• $n>0$$n-1$

Mengikuti strategi yang sama yang kami gunakan untuk mergesort di sini mengarah ke jenis penyisipan rekursif. Jadi, biasanya kami mengembangkan definisi rekursif yang melibatkan beberapa elemen rekursif, yaitu memotong set data menjadi setengah atau ketiga.

Sekarang, ada Teorema Utama untuk menganalisis algoritma D&C dan ini menyoroti ekspektasi efisiensi untuk sub-komponen algoritma D&C dengan efisiensi run-time keseluruhan tertentu.