Pengenalan Dynamic Programming
Pemrograman dinamis adalah metode optimasi matematis dan paradigma algoritmik. Metode ini dikembangkan oleh Richard Bellman pada tahun 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik dirgantara hingga ekonomi. Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang kompleks dengan memecahnya secara rekursif menjadi sub-masalah yang lebih sederhana. Meskipun beberapa masalah pengambilan keputusan tidak dapat diurai dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali diurai secara rekursif. Hal yang sama berlaku dalam ilmu komputer: Jika suatu masalah dapat diselesaikan secara optimal dengan membaginya menjadi sub-masalah dan kemudian secara rekursif mencari solusi optimal untuk sub-masalah tersebut, maka ini disebut substruktur optimal.Jika submasalah dapat disarangkan secara rekursif dalam masalah yang lebih besar sehingga metode pemrograman dinamis dapat diterapkan, maka terdapat hubungan antara nilai masalah yang lebih besar dan nilai submasalah tersebut. Dalam literatur optimasi, hubungan ini disebut persamaan Bellman.
Persamaan Matematis
Dalam optimasi matematis, pemrograman dinamis mengacu pada penyederhanaan keputusan dengan memecahnya menjadi serangkaian langkah keputusan dari waktu ke waktu. Proses ini melibatkan pendefinisian barisan fungsi nilai V1, V2, ..., Vn, yang mewakili keadaan sistem pada waktu i dari 1 sampai n, dimana Vn(y) adalah nilai dalam keadaan y pada saat terakhir. Utara.Nilai Vi pada waktu sebelumnya dapat dicari mundur dengan menggunakan persamaan Bellman. Untuk i = 2, ..., n, Vi-1 pada setiap state dihitung dari Vi dengan memaksimumkan fungsi keuntungan dari keputusan pada waktu i-1 dan fungsi Vi pada state baru pada saat pengambilan keputusan tersebut.Proses ini menghasilkan Vi-1 untuk status yang diperlukan. Pada keadaan awal sistem, V1 merupakan nilai solusi optimal. Nilai optimal dari variabel keputusan dapat dikembalikan secara individual setelah perhitungan dilakukan.
Computer Science
Ada dua atribut utama yang harus dimiliki suatu masalah agar pemrograman dinamis dapat diterapkan: substruktur optimal dan submasalah yang tumpang tindih. Ketika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah yang tidak tumpang tindih, strategi ini disebut “membagi dan menaklukkan.”Oleh karena itu, pengurutan gabungan dan pengurutan cepat tidak diklasifikasikan sebagai masalah pemrograman dinamis.
Substruktur optimal berarti bahwa solusi terhadap masalah optimasi tertentu dapat diperoleh dengan kombinasi solusi optimal dari submasalahnya. Substruktur optimal biasanya dijelaskan dengan rekursi.Misalnya, pada graf G = (V, E), jalur terpendek p dari simpul u ke simpul v mewakili substruktur optimal: ambil setiap simpul perantara w pada lintasan terpendek p. Jika p memang merupakan jalur terpendek, jalur tersebut dapat dibagi menjadi subjalur p1 dari u ke w dan p2 dari w ke v, sehingga jalur ini adalah yang terpendek di antara simpul-simpul yang bersesuaian (menggunakan metode potong-dan-tempel yang dijelaskan pada
argumen). Pengantar algoritma). Oleh karena itu, solusi dapat dengan mudah dirumuskan untuk mencari jalur terpendek secara rekursif, seperti halnya dengan algoritma Bellman-Ford atau algoritma Floyd-Warshall.
Tumpang tindih submasalah berarti ruang submasalah harus kecil, yaitu. H. algoritma rekursif apa pun yang menyelesaikan masalah harus menyelesaikan submasalah yang sama berulang kali, bukan membuat submasalah baru. Misalnya, perhatikan rumus rekursif untuk menghasilkan deret Fibonacci: Fi = Fi-1 + Fi-2, dengan kasus dasar F1 = F2 = 1. Maka F43 = F42 + F41 dan F42 = F41 + F40. Sekarang F41 diisi menjadi subpohon rekursif dari F43 dan juga F42. Meskipun jumlah totalsubmasalah sangat kecil (hanya 43), jika kita menggunakan solusi rekursif naif seperti ini, kita akan menyelesaikan masalah yang sama berulang kali.Pemrograman dinamis memperhitungkan fakta ini dan menyelesaikan setiap sub-masalah hanya satu kali.
Hal ini dapat dicapai dengan salah satu dari dua cara:
-
Top down approach: Ini adalah akibat langsung dari perumusan masalah secara rekursif. Jika solusi suatu masalah dapat dirumuskan secara rekursif menggunakan solusi dari submasalahnya dan submasalah tersebut tumpang tindih, kita dapat dengan mudah mencatat atau menyimpan solusi dari submasalah tersebut dalam sebuah tabel. Setiap kali kita mencoba memecahkan submasalah baru, pertama-tama kita memeriksa tabel untuk melihat apakah submasalah tersebut sudah terpecahkan. Jikasolusi telah dicatat, kita dapat menggunakannya secara langsung, jika tidak, kita selesaikan submasalah dan tambahkan solusinya ke tabel.
-
Bottom up approach: Setelah kita merumuskan solusi suatu masalah secara rekursif dalam bentuk submasalah, kita dapat mencoba merumuskan kembali masalah dari bawah ke atas: pertama-tama kita mencoba menyelesaikan submasalah terkecil dan membangun solusi berdasarkan solusinya. Sub-masalahnya adalah yang terbesar. Hal ini juga biasanya dilakukan dalam bentuk tabel, dengan menghasilkan solusi secara berulang untuk submasalah yang semakin besar menggunakan solusi
untuk submasalah yang lebih kecil. Misalnya kita sudah mengetahui nilai F41 dan F40, kita bisa langsung menghitung nilai F42.
Beberapa bahasa pemrograman dapat secara otomatis menyimpan hasil pemanggilan fungsi dengan serangkaian argumen tertentu untuk mempercepat evaluasi panggilan berdasarkan nama (mekanisme ini disebut panggilan demi permintaan). Beberapa bahasa mengizinkan hal ini secara portabel (misalnya Skema, Common Lisp, Perl, atau D). Beberapa bahasa memiliki hafalan otomatis, seperti: B. Prolog dan J Tabled, yang mendukung hafalan dengan kata keterangan M. Namun, ini hanya mungkin untuk fungsi yang transparan secara referensial. Penghafalan juga ditemukan sebagai pola desain yang mudah diakses dalam bahasa berbasis penulisan ulang seperti Bahasa Wolfram.
Contoh Algoritma :
- Algoritma Dijkstra untuk masalah jalur terpendek
- Deret Fibonacci
Disadur dari : en.wikipedia.org