Pemrograman dinamis: Perbedaan antara revisi
k Menghapus Kategori:Ilmu komputer; Menambah Kategori:Pemrograman dinamis menggunakan HotCat |
|||
Baris 32: | Baris 32: | ||
''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<sub>1</sub>'' dari ''u'' ke ''w'' dan ''p<sub>2</sub>'' 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 [[Algoritme Bellman-Ford|algoritma Bellman–Ford]] atau [[Algoritme Floyd-Warshall|algoritma Floyd–Warshall]]. |
''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<sub>1</sub>'' dari ''u'' ke ''w'' dan ''p<sub>2</sub>'' 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 [[Algoritme Bellman-Ford|algoritma Bellman–Ford]] atau [[Algoritme Floyd-Warshall|algoritma Floyd–Warshall]]. |
||
=== 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<ref>DeLisi, Biopolymers, 1974, Volume 13, Issue 7, pages 1511–1512, July 1974</ref> dan Georgii Gurskii dan Alexander Zasedatelev di Uni Soviet.<ref>Gurskiĭ GV, Zasedatelev AS, Biofizika, 1978 Sep-Oct;23(5):932-46</ref> Baru-baru ini algoritma ini menjadi sangat populer dalam bioinformatika dan biologi komputasi, khususnya dalam studi tentang posisi [[nukleosom]] dan pengikatan [[faktor transkripsi]]. |
|||
== Referensi == |
== Referensi == |
Revisi per 17 Oktober 2020 03.02
Halaman ini sedang dipersiapkan dan dikembangkan sehingga mungkin terjadi perubahan besar. Anda dapat membantu dalam penyuntingan halaman ini. Halaman ini terakhir disunting oleh PinkDash (Kontrib • Log) 1464 hari 545 menit lalu. Jika Anda melihat halaman ini tidak disunting dalam beberapa hari, mohon hapus templat ini. |
Pemrograman dinamis (bahasa 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.
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.[1] 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 V1, V2, ..., Vn mengambil y sebagai argumen yang mewakili keadaan sistem pada waktu i dari 1 sampai n. Definisi Vn(y) adalah nilai yang diperoleh di keadaan y terakhir kali n. Nilai Vi 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, Vi−1 di setiap keadaan y dihitung dari Vi dengan memaksimalkan fungsi sederhana (biasanya jumlah) keuntungan dari keputusan pada saat itu i − 1 dan fungsi Vi di keadaan baru sistem jika keputusan ini dibuat. Sejak Vi telah dihitung untuk keadaan yang diperlukan, hasil operasi di atas Vi−1 untuk keadaan tersebut. Akhirnya, V1 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 yang menyebabkan sistem untuk mengikuti lintasan yang bisa diterima pada interval waktu yang terus menerus yang meminimalkan biaya fungsi.
Solusi untuk masalah ini adalah pengendalian hukum atau kebijakan yang optimal , yang menghasilkan lintasan yang optimal dan sebuah fungsi cost-to-go . Yang terakhir mematuhi persamaan fundamental dari pemrograman dinamis:
persamaan diferensial parsial yang dikenal sebagai persamaan Hamilton-Jacobi-Bellman, di mana dan . Salah satu menemukan meminimalkan istilah dari , , dan fungsi yang tidak diketahui dan kemudian mensubstitusikan hasilnya ke dalam persamaan Hamilton – Jacobi – Bellman untuk mendapatkan persamaan diferensial parsial yang akan diselesaikan dengan kondisi batas .[2] 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:
Pada tahap dari interval waktu diskrit dengan jarak yang sama, dan dimana dan menunjukkan pendekatan diskrit untuk dan . Persamaan fungsional ini dikenal sebagai persamaan Bellman, yang dapat diselesaikan untuk solusi tepat dari pendekatan diskrit persamaan optimasi.[3]
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".[4] 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 p1 dari u ke w dan p2 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.
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[5] dan Georgii Gurskii dan Alexander Zasedatelev di Uni Soviet.[6] Baru-baru ini algoritma ini menjadi sangat populer dalam bioinformatika dan biologi komputasi, khususnya dalam studi tentang posisi nukleosom dan pengikatan faktor transkripsi.
Referensi
- ^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 0-262-03293-7 . pp. 344.
- ^ Kamien, M. I.; Schwartz, N. L. (1991). Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management (edisi ke-Second). New York: Elsevier. hlm. 261. ISBN 978-0-444-01609-6.
- ^ Kirk, Donald E. (1970). Optimal Control Theory: An Introduction. Englewood Cliffs, NJ: Prentice-Hall. hlm. 94–95. ISBN 978-0-13-638098-6.
- ^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 0-262-03293-7 . pp. 344.
- ^ DeLisi, Biopolymers, 1974, Volume 13, Issue 7, pages 1511–1512, July 1974
- ^ Gurskiĭ GV, Zasedatelev AS, Biofizika, 1978 Sep-Oct;23(5):932-46
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.
- Bellman, Richard (1954), "The theory of dynamic programming", 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), The Art and Theory of Dynamic Programming, Academic Press, ISBN 978-0-12-221860-6.
- Giegerich, R.; Meyer, C.; Steffen, P. (2004), "A Discipline of Dynamic Programming over Sequence Data" (PDF), Science of Computer Programming, 51 (3): 215–263, doi:10.1016/j.scico.2003.12.005.
- Meyn, Sean (2007), Control Techniques for Complex Networks, Cambridge University Press, ISBN 978-0-521-88441-9, diarsipkan dari versi asli tanggal 2010-06-19 .
- Sritharan, S. S. (1991). "Dynamic Programming of the Navier-Stokes Equations". Systems and Control Letters. 16 (4): 299–307. doi:10.1016/0167-6911(91)90020-f.
- Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989), Recursive Methods in Economic Dynamics, 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."
- Tutorial pemrograman dinamis
- Pengantar Lembut tentang Pemrograman Dinamis dan Algoritma Viterbi
- Prolog Tabel BProlog dan XSB
- IFORS online interactive dynamic programming modulestermasuk, jalur terpendek, penjual keliling, ransel, koin palsu, menjatuhkan telur, jembatan dan obor, penggantian, produk matriks yang dirantai, dan masalah jalur kritis.