Perbedaan Kasus pada Pemrograman Dinamis: Dibutuhkan Contoh!

Saya telah mengerjakan pemrograman dinamis selama beberapa waktu. Cara kanonik untuk mengevaluasi rekursi pemrograman dinamis adalah dengan membuat tabel dari semua nilai yang diperlukan dan mengisinya baris demi baris. Lihat misalnya Cormen, Leiserson et al: "Pengantar Algoritma" untuk pengantar.

Saya fokus pada skema perhitungan berbasis tabel dalam dua dimensi (pengisian baris-demi-baris) dan menyelidiki struktur dependensi sel, yaitu sel mana yang perlu dilakukan sebelum yang lain dapat dihitung. Kami menyatakan dengan set indeks sel yang bergantung pada sel . Perhatikan bahwa harus bebas siklus.$\Gamma(\mathbf{i})$$\mathbf{i}$$\Gamma$

Saya abstrak dari fungsi aktual yang dihitung dan berkonsentrasi pada struktur rekursifnya. Secara formal, saya mempertimbangkan recurrrence menjadi pemrograman dinamis jika memiliki bentuk$d$

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

dengan , dan beberapa fungsi (yang dapat dihitung) yang tidak menggunakan selain melalui .$\mathbf{i} \in [0\dots m] \times [0\dots n]$$\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$$f$$d$$\widetilde{\Gamma}_d$

Ketika membatasi granularity dari ke area kasar (ke kiri, atas-kiri, atas, atas-kanan, ... dari sel saat ini) satu mengamati bahwa pada dasarnya ada tiga kasus (hingga simetri dan rotasi) yang valid rekursi pemrograman dinamis yang menginformasikan bagaimana tabel dapat diisi:$\Gamma_d$

Area merah menunjukkan (perkiraan berlebihan) . Kasus satu dan dua mengakui himpunan bagian, kasus ketiga adalah kasus terburuk (hingga transformasi indeks). Perhatikan bahwa tidak sepenuhnya diwajibkan bahwa seluruh area merah dilindungi oleh ; beberapa sel di setiap bagian merah tabel cukup untuk mengecatnya merah. Area putih secara eksplisit diperlukan untuk tidak mengandung sel yang diperlukan.$\Gamma$$\Gamma$

Contoh untuk kasus satu adalah edit jarak dan urutan umum terpanjang , kasus kedua berlaku untuk Bellman & Ford dan CYK . Contoh yang kurang jelas termasuk yang bekerja pada diagonal daripada baris (atau kolom) karena dapat diputar agar sesuai dengan kasus yang diusulkan; lihat jawaban Joe sebagai contoh.

Saya tidak punya contoh (alami) untuk kasus tiga! Jadi pertanyaan saya adalah: Apa contoh untuk kasus rekursi / masalah pemrograman dinamis?

Ada banyak contoh lain dari algoritma pemrograman dinamis yang tidak sesuai dengan pola Anda sama sekali.

• Masalah kenaikan urutan terpanjang hanya membutuhkan tabel satu dimensi.

• Ada beberapa algoritma pemrograman dinamis alami yang tabelnya membutuhkan tiga atau lebih dimensi. Sebagai contoh: Temukan persegi panjang putih area-maksimum dalam bitmap. Algoritma pemrograman dinamis alami menggunakan tabel tiga dimensi.

• Tetapi yang paling penting, pemrograman dinamis bukan tentang tabel ; ini tentang penguraian rekursi. Ada banyak algoritma pemrograman dinamis alami di mana struktur data yang digunakan untuk menyimpan hasil antara bukan array, karena perulangan yang dibatalkan tidak melebihi rentang bilangan bulat. Dua contoh mudah adalah menemukan kumpulan simpul independen terbesar di pohon, dan menemukan subtree umum terbesar dari dua pohon. Contoh yang lebih kompleks adalah algoritma -aproximation untuk masalah salesman keliling Euclidean oleh Arora dan Mitchell.$(1+\epsilon)$

Fungsi Computing Ackermann ada dalam semangat ini. Untuk menghitung Anda perlu tahu A ( m , n - 1 ) dan A ( m - 1 , k ) untuk beberapa k besar . Koordinat kedua menurun, atau menurun pertama, dan yang kedua berpotensi meningkat.$A(m,n)$$A(m,n-1)$$A(m-1,k)$$k$

Ini idealnya tidak sesuai dengan persyaratan, karena jumlah kolom tidak terbatas, dan perhitungan biasanya dilakukan top-down dengan menghafal, tetapi saya pikir itu layak untuk disebutkan.

Ini tidak cocok dengan case 3 persis, tapi saya tidak tahu apakah ada kasus Anda menangkap masalah yang sangat umum digunakan untuk mengajarkan pemrograman dinamis: Matrix Chain Multiplication . Untuk mengatasi masalah ini, (dan banyak lainnya, ini hanya yang kanonik) kami mengisi matriks diagonal dengan diagonal, bukan baris demi baris.

Jadi aturannya kira-kira seperti ini:

Saya tahu ini contoh konyol, tapi saya pikir masalah iteratif yang sederhana seperti

Temukan jumlah angka dalam matriks persegi

mungkin memenuhi syarat. The "tradisional untuk setiap baris untuk setiap kolom" agak seperti kasus Anda 3.

Ini sebenarnya bukan ruang pencarian yang Anda cari, tetapi saya memiliki ide tentang bagian atas kepala saya yang mungkin bisa membantu.

Masalah:

$n × n$$M$$x$$M$

Menjawab

Ini dapat diselesaikan dengan cara rekursif berikut:

$k = \lceil{\frac{1+n}{2}}\rceil$$x$$m_{k,k}$$x<m_{k,k}$$m_{i,j}$$k\leq i\leq n$$k\leq j\leq n$$1/4$$x>m_{k,k}$$1/4$$\frac{3}{4} n^2$$x$$\left(\frac{3}{4}\right)^3 n^2$