Tentang apa pemrograman dinamis?

Maaf sebelumnya jika pertanyaan ini terdengar bodoh ...

Sejauh yang saya tahu, membangun algoritma menggunakan pemrograman dinamis bekerja seperti ini:

1. mengungkapkan masalah sebagai relasi berulang;
2. menerapkan hubungan perulangan baik melalui memoisasi atau melalui pendekatan bottom up.

Sejauh yang saya tahu, saya telah mengatakan segalanya tentang pemrograman dinamis. Maksud saya: pemrograman dinamis tidak memberikan alat / aturan / metode / teorema untuk mengekspresikan hubungan perulangan, atau untuk mengubahnya menjadi kode.

Jadi, apa yang spesial dari pemrograman dinamis? Apa yang diberikannya kepada Anda, selain metode yang tidak jelas untuk mendekati jenis masalah tertentu?

Pemrograman dinamis memberi Anda cara untuk berpikir tentang desain algoritma. Ini seringkali sangat membantu.

Metode memoo dan bottom-up memberi Anda aturan / metode untuk mengubah hubungan perulangan menjadi kode. Memoisasi adalah ide yang relatif sederhana, tetapi sering kali ide terbaik adalah!

Pemrograman dinamis memberi Anda cara terstruktur untuk berpikir tentang waktu berjalan dari algoritma Anda. Waktu yang berjalan pada dasarnya ditentukan oleh dua angka: jumlah sub-masalah yang harus Anda selesaikan, dan waktu yang dibutuhkan untuk menyelesaikan setiap sub-masalah. Ini memberikan cara mudah yang mudah untuk memikirkan masalah desain algoritma. Ketika Anda memiliki relasi pengulangan kandidat, Anda dapat melihatnya dan dengan sangat cepat mengetahui waktu pelaksanaannya (misalnya, Anda seringkali dapat dengan cepat memberi tahu berapa banyak subproblem yang akan ada, yang merupakan batas bawah pada waktu berjalan; jika ada banyak masalah yang harus Anda selesaikan secara eksponensial, maka perulangan mungkin tidak akan menjadi pendekatan yang baik). Ini juga membantu Anda mengesampingkan dekomposisi kandidat subproblem. Misalnya, jika kita memiliki string urutan S tidak mungkin menjadi pendekatan yang baik (jumlah subproblem adalah eksponensial dalam n ). Ini memungkinkan Anda memangkas "ruang pencarian" dari kemungkinan perulangan. , mendefinisikan subproblem dengan awalan S [ 1 .. i ] atau suffix S [ j . . n ] atau substring S [ i . . j ] mungkin masuk akal (jumlah subproblem adalah polinomial dalam n ), tetapi mendefinisikan subproblem dengan urutan dari$S[1..n]$$S[1..i]$$S[j..n]$$S[i..j]$$n$$S$$n$

Pemrograman dinamis memberi Anda pendekatan terstruktur untuk mencari hubungan pengulangan kandidat. Secara empiris, pendekatan ini seringkali efektif. Secara khusus, ada beberapa heuristik / pola umum yang dapat Anda kenali untuk cara-cara umum untuk mendefinisikan subproblem, tergantung pada jenis input. Contohnya:

• Jika input adalah bilangan bulat positif , salah satu cara kandidat untuk mendefinisikan subproblem adalah dengan mengganti n dengan integer yang lebih kecil n ′ (st 0 ≤ n $n$$n$$n'$ ).$0 \le n' \le n$

• Jika inputnya adalah string , beberapa kandidat cara untuk mendefinisikan subproblem meliputi: ganti S [ 1 .. n ] dengan awalan S [ 1 .. i ] ; ganti S [ 1 .. n ] dengan akhiran S [ j . . n ] ; ganti S [ 1 .. n ] dengan substring S [ i . (Di sini subproblem ditentukan oleh pilihan i $S[1..n]$$S[1..n]$$S[1..i]$$S[1..n]$$S[j..n]$$S[1..n]$$S[i..j]$$i,j$ .)

• Jika input adalah daftar , lakukan hal yang sama seperti yang Anda lakukan untuk string.

• Jika inputnya adalah pohon , salah satu cara kandidat untuk mendefinisikan subproblem adalah mengganti T dengan subtree T (yaitu, pilih node x dan ganti T dengan subtree yang di-root pada x ; subproblem ditentukan oleh pilihan x ).$T$$T$$T$$x$$T$$x$$x$

• Jika inputnya adalah sepasang , maka secara rekursif lihatlah tipe x dan tipe y untuk mengidentifikasi cara untuk memilih subproblem untuk masing-masing. Dengan kata lain, satu kandidat cara untuk mendefinisikan subproblem adalah mengganti ( x , y ) dengan ( x ′ , y ′ ) di mana x ′ adalah subproblem untuk x dan y ′ adalah subproblem untuk y . (Anda juga dapat mempertimbangkan submasalah formulir$(x,y)$$x$$y$$(x,y)$$(x',y')$$x'$$x$$y'$$y$ Atau ( x ′ , y ) .)$(x,y')$$(x',y)$

Dan seterusnya. Ini memberi Anda heuristik yang sangat berguna: hanya dengan melihat tipe tanda tangan dari metode ini, Anda dapat menemukan daftar cara kandidat untuk mendefinisikan subproblem. Dengan kata lain, hanya dengan melihat pernyataan masalah - hanya melihat jenis input - Anda dapat menemukan beberapa kandidat cara untuk mendefinisikan subproblem.

Ini seringkali sangat membantu. Itu tidak memberi tahu Anda apa hubungan perulangan itu, tetapi ketika Anda memiliki pilihan tertentu untuk bagaimana mendefinisikan subproblem, seringkali tidak terlalu sulit untuk menentukan hubungan perulangan yang sesuai. Jadi, sering kali mengubah desain algoritma pemrograman dinamis menjadi pengalaman terstruktur. Anda menuliskan pada kertas memo daftar kandidat cara untuk mendefinisikan subproblem (menggunakan heuristik di atas). Kemudian, untuk masing-masing kandidat, Anda mencoba untuk menulis hubungan pengulangan, dan mengevaluasi waktu berjalannya dengan menghitung jumlah sub-masalah dan waktu yang dihabiskan per sub-masalah. Setelah mencoba setiap kandidat, Anda menyimpan yang terbaik yang dapat Anda temukan. Menyediakan beberapa struktur untuk proses desain algoritma adalah bantuan besar, karena jika tidak, desain algoritma dapat mengintimidasi (ada '

Pemahaman Anda tentang pemrograman dinamis benar ( afaik ), dan pertanyaan Anda dibenarkan.

Saya pikir ruang desain tambahan yang kita dapatkan dari jenis perulangan yang kita sebut "pemrograman dinamis" paling baik dilihat dibandingkan dengan skema pendekatan rekursif lainnya.

Mari kita berpura-pura input kita adalah array demi menyoroti konsep.$A[1..n]$

1. Pendekatan Induktif

   Di sini idenya adalah untuk membuat masalah Anda lebih kecil, pecahkan versi yang lebih kecil dan dapatkan solusi untuk yang asli. Secara skematis,

   $\qquad f(A) = g\bigl( f(A[1..n-c]), A \bigr)$

   dengan fungsi / algoritma yang menerjemahkan solusi.$g$

   Contoh: Menemukan bintang dalam waktu linier

2. Bagilah & Taklukkan

   Partisi input menjadi beberapa bagian yang lebih kecil, pecahkan masalah untuk masing-masing dan gabungkan. Secara skematis (untuk dua bagian),

   .$\qquad f(A) = g\bigl(f(A[1..c]), f(A[c+1..n]), A\bigr)$

   Contoh: Gabung- / Quicksort, Jarak berpasangan terpendek di pesawat

3. Pemrograman Dinamis

   Pertimbangkan semua cara mempartisi masalah menjadi masalah yang lebih kecil dan pilih yang terbaik. Secara skematis (untuk dua bagian),

   .$\qquad f(A) = \operatorname{best} \Bigl\{ g\bigl(f(A[1..c]), f(A[c+1..n])\bigr) \Bigm| 1 \leq c \leq n-1 \Bigr\}$

   Contoh: Edit jarak, Masalah perubahan-pembuatan

   Catatan penting: pemrograman dinamis bukanlah kekerasan ! Penerapan dalam setiap langkah mengurangi ruang pencarian.$\operatorname{best}$

Dalam arti tertentu, Anda tahu semakin sedikit statis berjalan dari atas ke bawah, dan harus membuat semakin banyak keputusan secara dinamis.

Pelajaran dari belajar tentang pemrograman dinamis adalah tidak apa - apa untuk mencoba semua partisi yang mungkin (well, itu diperlukan untuk kebenaran) karena masih bisa efisien menggunakan memoisasi.

Pemrograman Dinamis memungkinkan Anda untuk menukar memori dengan waktu komputasi. Perhatikan contoh klasiknya, Fibonacci.

Fibonacci didefinisikan oleh perulangan . Jika Anda menyelesaikan menggunakan rekursi ini, Anda akhirnya melakukan panggilan O ( 2 n ) ke F i b ( $Fib(n)=Fib(n-1)+Fib(n-2)$$O(2^n)$ , karena pohon rekursi adalah pohon biner dengan tinggi n .$Fib(\cdot)$$n$

Sebagai gantinya, Anda ingin menghitung , lalu gunakan ini untuk menemukan F i b ( 3 ) , gunakan itu untuk menemukan F i b ( 4 ) , dll. Ini hanya membutuhkan waktu O ( n ) .$Fib(2)$$Fib(3)$$Fib(4)$$O(n)$

DP juga memberi kita teknik dasar untuk menerjemahkan hubungan perulangan menjadi solusi bottom-up, tetapi ini relatif mudah (dan umumnya melibatkan penggunaan matriks dimensi , atau batas matriks seperti itu, di mana m adalah jumlah parameter dalam hubungan perulangan). Ini dijelaskan dengan baik dalam teks tentang DP.$m$$m$

Berikut ini adalah cara lain yang sedikit berbeda dari ungkapan apa yang diberikan pemrograman dinamis kepada Anda. Pemrograman dinamis runtuh sejumlah eksponensial solusi kandidat menjadi sejumlah polinomial kelas ekivalensi, sehingga solusi kandidat di setiap kelas tidak bisa dibedakan dalam beberapa hal.

$k$$A$$n$$2^n$$O(n^2)$$f(i, \ell)$$i$$\ell$

$O(n^2k)$