Pemrograman dinamis

Pemrograman dinamis (Inggris: dynamic programming) adalah metode pengoptimalan matematika dan metode pemrograman komputer. Metode ini dikembangkan oleh Richard Bellman pada 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik kedirgantaraan hingga ekonomi.

Gambar 1. Menemukan jalur terpendek dalam grafik menggunakan substruktur optimal; garis lurus menunjukkan satu sisi; garis bergelombang menunjukkan jalur terpendek antara dua sudut yang terhubung (di antara jalur lain, tidak ditampilkan, berbagi dua sudut yang sama); garis tebal adalah jalur terpendek keseluruhan dari awal sampai tujuan.

Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang rumit dengan memecahnya menjadi sub-masalah yang lebih sederhana secara rekursif. Meskipun beberapa masalah keputusan tidak dapat dipisahkan dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali pecah secara rekursif. Begitu pula dalam ilmu komputer, jika suatu masalah dapat diselesaikan secara optimal dengan memecahnya menjadi sub-sub masalah dan kemudian secara rekursif mencari solusi optimal untuk sub masalah tersebut, maka dikatakan memiliki substruktur yang optimal.

Jika sub-masalah dapat disarangkan secara rekursif di dalam masalah yang lebih besar, sehingga metode pemrograman dinamis dapat diterapkan, maka ada hubungan antara nilai masalah yang lebih besar dengan nilai-nilai sub-masalah tersebut. Dalam literatur optimasi, hubungan ini disebut persamaan Bellman.

Gambaran

Pengoptimalan matematika

Dalam hal optimasi matematis, pemrograman dinamis biasanya mengacu pada penyederhanaan keputusan dengan memecahnya menjadi urutan langkah-langkah keputusan dari waktu ke waktu. Ini dilakukan dengan mendefinisikan urutan fungsi nilai V₁, V₂, ..., V_n mengambil y sebagai argumen yang mewakili keadaan sistem pada waktu i dari 1 sampai n. Definisi V_n(y) adalah nilai yang diperoleh di keadaan y terakhir kali n. Nilai V_i di waktu sebelumnya i = n −1, n − 2, ..., 2, 1 dapat ditemukan dengan bekerja mundur, menggunakan hubungan rekursif yang disebut persamaan Bellman. untuk i = 2, ..., n, V_i−1 di setiap keadaan y dihitung dari V_i dengan memaksimalkan fungsi sederhana (biasanya jumlah) keuntungan dari keputusan pada saat itu i − 1 dan fungsi V_i di keadaan baru sistem jika keputusan ini dibuat. Sejak V_i telah dihitung untuk keadaan yang diperlukan, hasil operasi di atas V_i−1 untuk keadaan tersebut. Akhirnya, V₁ pada keadaan awal sistem adalah nilai solusi optimal. Nilai optimal dari variabel keputusan dapat dipulihkan, satu per satu, dengan melacak kembali perhitungan yang telah dilakukan.

Teori kontrol

Dalam teori kontrol, masalah tipikal adalah menemukan kontrol yang dapat diterima $\mathbf {u} ^{\ast }$ yang menyebabkan sistem ${\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)$ untuk mengikuti lintasan yang bisa diterima $\mathbf {x} ^{\ast }$pada interval waktu yang terus menerus $t_{0}\leq t\leq t_{1}$ yang meminimalkan biaya fungsi.

$J=b\left(\mathbf {x} (t_{1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)\mathrm {d} t$

Solusi untuk masalah ini adalah pengendalian hukum atau kebijakan yang optimal $\mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)$, yang menghasilkan lintasan yang optimal $\mathbf {x} ^{\ast }$ dan sebuah fungsi cost-to-go $J^{\ast }$. Yang terakhir mematuhi persamaan fundamental dari pemrograman dinamis:

$-J_{t}^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x}^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}$

persamaan diferensial parsial yang dikenal sebagai persamaan Hamilton-Jacobi-Bellman, di mana $J_{x}^{\ast }={\frac {\partial J^{\ast }}{\partial \mathbf {x} }}=\left[{\frac {\partial J^{\ast }}{\partial x_{1}}}~~~~{\frac {\partial J^{\ast }}{\partial x_{2}}}~~~~\dots ~~~~{\frac {\partial J^{\ast }}{\partial x_{n}}}\right]^{\mathsf {T}}$ dan $J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}$. Salah satu menemukan meminimalkan $\mathbf {u}$ istilah dari $t$, $\mathbf {x}$, dan fungsi yang tidak diketahui $J_{x}^{\ast }$dan kemudian mensubstitusikan hasilnya ke dalam persamaan Hamilton – Jacobi – Bellman untuk mendapatkan persamaan diferensial parsial yang akan diselesaikan dengan kondisi batas $J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)$. Dalam praktiknya, ini umumnya memerlukan teknik numerik untuk beberapa pendekatan diskrit ke hubungan pengoptimalan yang tepat.

Atau, proses kontinu dapat didekati dengan sistem diskrit, yang mengarah ke analog relasi rekurensi berikut dengan persamaan Hamilton – Jacobi – Bellman:

$J_{k}^{\ast }\left(\mathbf {x} _{n-k}\right)=\min _{\mathbf {u} _{n-k}}\left\{{\hat {f}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)+J_{k-1}^{\ast }\left({\hat {g}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}$

Pada tahap $k$ dari $n$ interval waktu diskrit dengan jarak yang sama, dan dimana ${\hat {f}}$ dan ${\hat {g}}$ menunjukkan pendekatan diskrit untuk $f$ dan $\mathbf {g}$. Persamaan fungsional ini dikenal sebagai persamaan Bellman, yang dapat diselesaikan untuk solusi tepat dari pendekatan diskrit persamaan optimasi.

Pemrograman komputer

Ada dua atribut utama yang harus dimiliki masalah agar pemrograman dinamis dapat diterapkan: substruktur yang optimal dan sub-masalah yang tumpang tindih. Jika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah tidak tumpang tindih, strateginya disebut "divide and conquer". Inilah sebabnya mengapa merge sort dan quick sort tidak diklasifikasikan sebagai masalah pemrograman dinamis.

Substruktur optimal berarti bahwa solusi untuk masalah pengoptimalan yang diberikan dapat diperoleh dengan kombinasi solusi optimal untuk sub-masalahnya. Substruktur optimal seperti itu biasanya dijelaskan melalui rekursi. Misalnya diberi grafik G=(V,E), jalur terpendek p dari sebuah vertex u ke sebuah vertrex v menunjukkan substruktur yang optimal: ambil perantara vertex w di jalur terpendek ini p. Jika p benar-benar merupakan jalur terpendek, kemudian dapat dipecah menjadi sub-jalur p₁ dari u ke w dan p₂ dari w ke v sedemikian rupa sehingga ini, pada gilirannya, memang merupakan jalur terpendek antara simpul yang sesuai (dengan argumen potong-dan-tempel sederhana yang dijelaskan dalam Introduction to Algorithms). Oleh karena itu, salah satu dapat dengan mudah merumuskan solusi untuk menemukan jalur terpendek secara rekursif, yang dilakukan oleh algoritma Bellman–Ford atau algoritma Floyd–Warshall.

Sub-masalah yang tumpang tindih berarti bahwa ruang sub-masalah harus kecil, yaitu, algoritma rekursif apa pun yang memecahkan masalah harus menyelesaikan sub-masalah yang sama berulang kali, daripada menghasilkan sub-masalah baru. Misalnya, pertimbangkan formulasi rekursif untuk menghasilkan deret Fibonacci: F_i = F_i−1 + F_i−2, dengan kasus dasar F₁ = F₂ = 1. Lalu F₄₃ = F₄₂ + F₄₁, dan F₄₂ = F₄₁ + F₄₀. Sekarang F₄₁ sedang diselesaikan di sub-pohon rekursif dari keduanya F₄₃ sebaik F₄₂. Meskipun jumlah total sub-masalah sebenarnya kecil (hanya 43 dari mereka), kita akhirnya menyelesaikan masalah yang sama berulang kali jika kita mengadopsi solusi rekursif naif seperti ini. Pemrograman dinamis memperhitungkan fakta ini dan memecahkan setiap sub-masalah hanya sekali.

Gambar 2. Grafik sub-masalah untuk deret Fibonacci. Fakta bahwa ini bukan pohon menunjukkan sub-masalah yang tumpang tindih.

Ini dapat dicapai dengan salah satu dari dua cara:

• Pendekatan top-down: Ini adalah hasil langsung dari formulasi rekursif dari masalah apa pun. Jika solusi untuk masalah apa pun dapat dirumuskan secara rekursif menggunakan solusi untuk sub-masalahnya, dan jika sub-masalah tersebut tumpang tindih, maka seseorang dapat dengan mudah memoisasi atau menyimpan solusi untuk sub-masalah dalam sebuah tabel. Setiap kali kita mencoba untuk memecahkan sub-masalah baru, pertama-tama kita memeriksa tabel untuk melihat apakah sudah terpecahkan. Jika solusi telah dicatat, kita dapat menggunakannya secara langsung, jika tidak kita menyelesaikan sub-masalah dan menambahkan solusinya ke tabel.
• Pendekatan bottom-up: Setelah kita merumuskan solusi untuk suatu masalah secara rekursif seperti dalam sub-masalah, kita dapat mencoba merumuskan kembali masalah secara bottom-up: coba selesaikan sub-masalah terlebih dahulu dan gunakan solusi mereka untuk membangun dan sampai pada solusi untuk sub-masalah yang lebih besar. Ini juga biasanya dilakukan dalam bentuk tabel dengan menghasilkan solusi secara berulang untuk sub-masalah yang lebih besar dan lebih besar dengan menggunakan solusi untuk sub-masalah kecil. Misalnya, jika kita sudah mengetahui nilai F₄₁ dan F₄₀, kita bisa langsung menghitung nilai F₄₂.

Beberapa bahasa pemrograman dapat secara otomatis memoisasi hasil panggilan fungsi dengan sekumpulan argumen tertentu, untuk mempercepat evaluasi Call-by-name. (mekanisme ini disebut sebagai call-by-need). Beberapa bahasa membuatnya mungkin portabel (misalnya Scheme, Common Lisp, Perl atau D). Beberapa bahasa memiliki memoisasi otomatis bawaan, seperti tabel Prolog dan J, yang mendukung memoization dengan kata keterangan M. . Bagaimanapun, ini hanya mungkin untuk fungsi transparansi referensial. Memoisasi juga ditemukan sebagai pola desain yang mudah diakses dalam bahasa berbasis penulisan-ulang istilah seperti Bahasa Wolfram.

Bioinformatika

Pemrograman dinamis banyak digunakan dalam bioinformatika untuk tugas-tugas seperti penyelarasan urutan, pelipatan protein, prediksi struktur RNA, dan pengikatan protein-DNA. Algoritme pemrograman dinamis pertama untuk pengikatan protein-DNA dikembangkan pada tahun 1970-an secara independen oleh Charles DeLisi di AS dan Georgii Gurskii dan Alexander Zasedatelev di Uni Soviet. Baru-baru ini algoritma ini menjadi sangat populer dalam bioinformatika dan biologi komputasi, khususnya dalam studi tentang posisi nukleosom dan pengikatan faktor transkripsi.

Contoh: Algoritme komputer

Algoritma Dijkstra untuk masalah jalur terpendek

Dari sudut pandang pemrograman dinamis, algoritma Dijkstra untuk masalah jalur terpendek merupakan skema aproksimasi berurutan yang menyelesaikan persamaan fungsional pemrograman dinamis untuk masalah jalur terpendek dengan metode Reaching.

Faktanya, penjelasan Dijkstra tentang logika di balik algoritme, dinamakan

Masalah 2. Temukan jalur dengan panjang total minimum antara dua node yang diberikan $P$ dan $Q$. Kami menggunakan fakta bahwa, jika $R$ adalah node di jalur minimal dari $P$ ke $Q$, pengetahuan yang terakhir menyiratkan pengetahuan tentang jalan minimal dari $P$ ke $R$.

adalah parafrase dari Prinsip Optimalitas Bellman yang terkenal dalam konteks masalah jalur terpendek.

Deret Fibonacci

Menggunakan pemrograman dinamis dalam perhitungan anggota ke-n deret Fibonacci meningkatkan kinerjanya secara signifikan. Berikut adalah implementasi naif, berdasarkan langsung pada definisi matematis:

   function fib(n)
       if n <= 1 return n
       return fib(n − 1) + fib(n − 2)

Perhatikan bahwa jika kita sebut, katakanlah, fib(5), kita menghasilkan pohon panggilan yang memanggil fungsi pada nilai yang sama berkali-kali:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Khususnya, fib(2) dihitung tiga kali dari awal. Dalam contoh yang lebih besar, lebih banyak nilai fib, atau subproblem, dihitung ulang, yang mengarah ke algoritme waktu eksponensial.

Sekarang, misalkan kita memiliki objek peta sederhana, m, yang memetakan setiap nilai fib yang telah dihitung ke hasilnya, dan kita memodifikasi fungsi kita untuk menggunakannya dan memperbaruinya. Fungsi yang dihasilkan hanya membutuhkan O(n) waktu, bukan waktu eksponensial (tetapi membutuhkan O(n) ruang):

   var m := map(0 → 0, 1 → 1)
   function fib(n)
       if key n is not in map m 
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

Teknik menyimpan nilai yang telah dihitung ini disebut memoization; ini adalah pendekatan top-down, karena kita pertama kali memecah masalah menjadi subproblem lalu menghitung dan menyimpan nilai.

Dalam pendekatan bottom-up, kita menghitung nilai fib yang lebih kecil terlebih dahulu, lalu buat nilai yang lebih besar darinya. Metode ini juga menggunakan waktu O(n) karena mengandung loop yang berulang n - 1 kali, tetapi hanya membutuhkan ruang konstan (O(1)), berbeda dengan pendekatan top-down yang membutuhkan ruang O(n) untuk simpan peta.

   function fib(n)
       if n = 0
           return 0
       else
           var previousFib := 0, currentFib := 1
           repeat n − 1 times // loop is skipped if n = 1
               var newFib := previousFib + currentFib
               previousFib := currentFib
               currentFib  := newFib
       return currentFib

Dalam kedua contoh tersebut, kita hanya menghitung fib(2) satu kali, lalu gunakan untuk menghitung keduanya fib(4) dan fib(3), alih-alih menghitungnya setiap kali salah satu dari mereka dievaluasi.

Metode di atas sebenarnya membutuhkan $\Omega (n^{2})$ waktu untuk n besar karena penjumlahan dua bilangan bulat dengan $\Omega (n)$ bit masing-masing mengambil $\Omega (n)$ waktu. (Nomor n^th fibonacci memiliki $\Omega (n)$ bit.) Juga, ada bentuk tertutup untuk deret Fibonacci, yang dikenal sebagai rumus Binet, yang darinya suku $n$-th dihitung kira-kira $O(n(\log n)^{2})$ waktu, yang lebih efisien daripada teknik pemrograman dinamis di atas. Namun, pengulangan sederhana secara langsung memberikan bentuk matriks yang mengarah ke perkiraan $O(n\log n)$ algoritma dengan eksponensial matriks cepat.

Perataan urutan

Dalam genetika, perataan urutan adalah aplikasi penting di mana pemrograman dinamis sangat penting. Biasanya, masalahnya terdiri dari mengubah satu urutan menjadi urutan lain menggunakan operasi edit yang mengganti, menyisipkan, atau menghapus elemen. Setiap operasi memiliki biaya terkait, dan tujuannya adalah menemukan urutan pengeditan dengan total biaya terendah.

Masalahnya dapat dinyatakan secara alami sebagai rekursi, urutan A diedit secara optimal menjadi urutan B dengan baik:

1. memasukkan karakter pertama B, dan melakukan penyelarasan optimal A dan ekor B
2. menghapus karakter pertama A, dan melakukan penyelarasan optimal pada ekor A dan B
3. mengganti karakter pertama A dengan karakter pertama B, dan melakukan penjajaran optimal pada ekor A dan B.

Perataan parsial bisa ditabulasi dalam matriks, di mana sel (i,j) berisi biaya penyelarasan yang optimal A[1..i] ke B[1..j]. Biaya dalam sel (i,j) dapat dihitung dengan menambahkan biaya operasi yang relevan dengan biaya sel tetangganya, dan memilih yang optimal.

Ada varian yang berbeda, lihat algoritma Smith – Waterman dan algoritma Needleman – Wunsch.

Bacaan lanjutan

• Adda, Jerome; Cooper, Russell (2003), Dynamic Economics, MIT Press . Pengenalan yang dapat diakses untuk pemrograman dinamis di bidang ekonomi. MATLAB code for the book Diarsipkan 2020-10-09 di Wayback Machine..
• Bellman, Richard (1954), "Teori pemrograman dinamis", Bulletin of the American Mathematical Society, 60 (6): 503–516, doi:10.1090/S0002-9904-1954-09848-8 , MR 0067459 . Termasuk bibliografi literatur yang luas di daerah tersebut, hingga tahun 1954.
• Bellman, Richard (1957), Dynamic Programming, Princeton University Press . Edisi paperback Dover (2003), ISBN 0-486-42809-5.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (edisi ke-2nd), MIT Press & McGraw–Hill, ISBN 978-0-262-03293-3 . Terutama hal. 323–69.
• Dreyfus, Stuart E.; Law, Averill M. (1977), Seni dan Teori Pemrograman Dinamis, Academic Press, ISBN 978-0-12-221860-6 .
• Giegerich, R.; Meyer, C.; Steffen, P. (2004), "Sebuah Disiplin Pemrograman Dinamis atas Data Urutan" (PDF), Science of Computer Programming, 51 (3): 215–263, doi:10.1016/j.scico.2003.12.005 .
• Meyn, Sean (2007), Teknik Kontrol untuk Jaringan Kompleks, Cambridge University Press, ISBN 978-0-521-88441-9, diarsipkan dari versi asli tanggal 2010-06-19  .
• Sritharan, S. S. (1991). "Pemrograman Dinamis Persamaan Navier-Stokes". Systems and Control Letters. 16 (4): 299–307. doi:10.1016/0167-6911(91)90020-f. 
• Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989), Metode Rekursif dalam Dinamika Ekonomi, Harvard Univ. Press, ISBN 978-0-674-75096-8 .

Pranala luar

• Sebuah Tutorial tentang Pemrograman Dinamis
• MIT course on algorithms – Termasuk video kuliah tentang DP bersama dengan catatan kuliah, lihat lecture 15.
• Lebih banyak Catatan DP
• King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." Pengantar pemrograman dinamis sebagai alat penting dalam teori ekonomi.
• Dynamic Programming: from novice to advanced sebuah artikel TopCoder.com oleh Dumitru tentang Pemrograman Dinamis
• Algebraic Dynamic Programming – kerangka kerja formal untuk pemrograman dinamis, termasuk kursus tingkat awal kepada DP, University of Bielefeld
• Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming. Diarsipkan 2020-10-13 di Wayback Machine."
• Tutorial pemrograman dinamis
• Pengantar Lembut tentang Pemrograman Dinamis dan Algoritma Viterbi
• Prolog Tabel BProlog dan XSB
• Modul pemrograman dinamis interaktif online IFORS termasuk, jalur terpendek, penjual keliling, ransel, koin palsu, menjatuhkan telur, jembatan dan obor, penggantian, produk matriks yang dirantai, dan masalah jalur kritis.