The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, such as aerospace engineering and economics.
Metode ini dikembangkan oleh Richard Bellman pada 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik kedirgantaraan hingga ekonomi.
In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner.
Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang rumit dengan memecahnya menjadi sub-masalah yang lebih sederhana secara rekursif.
While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively.
Meskipun beberapa masalah keputusan tidak dapat dipisahkan dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali pecah secara rekursif.
Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.
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.
If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.
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.
In the optimization literature this relationship is called the Bellman equation.
Dalam literatur optimasi, hubungan ini disebut persamaan Bellman.
Since Vi has already been calculated for the needed states, the above operation yields Vi−1 for those states.
Sejak Vi telah dihitung untuk keadaan yang diperlukan, hasil operasi di atas Vi−1 untuk keadaan tersebut.
Finally, V1 at the initial state of the system is the value of the optimal solution.
Akhirnya, V1 pada keadaan awal sistem adalah nilai solusi optimal.
The optimal values of the decision variables can be recovered, one by one, by tracking back the calculations already performed.
Nilai optimal dari variabel keputusan dapat dipulihkan, satu per satu, dengan melacak kembali perhitungan yang telah dilakukan.
In control theory, a typical problem is to find an admissible control u ∗ ^{\ast }} which causes the system x ˙ ( t )
Dalam teori kontrol, masalah tipikal adalah menemukan kontrol yang dapat diterima u ∗ ^{\ast }} yang menyebabkan sistem x ˙ ( t )
The latter obeys the fundamental equation of dynamic programming: − J t ∗min u { f ( x ( t ) , u ( t ) , t ) + J x ∗ T g ( x ( t ) , u ( t ) , 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\}} a partial differential equation known as the Hamilton–Jacobi–Bellman equation, in which J x ∗∂ J ∗ ∂ x[ ∂ J ∗ ∂ x 1 ∂ J ∗ ∂ x 2 … ∂ J ∗ ∂ x n ] T ^{\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}}} and J t ∗∂ J ∗ ∂ t ^{\ast }={\frac {\partial J^{\ast }}{\partial t}}} .
Yang terakhir mematuhi persamaan fundamental dari pemrograman dinamis: − J t ∗min u { f ( x ( t ) , u ( t ) , t ) + J x ∗ T g ( x ( t ) , u ( t ) , 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 ∗∂ J ∗ ∂ x[ ∂ J ∗ ∂ x 1 ∂ J ∗ ∂ x 2 … ∂ J ∗ ∂ x n ] T ^{\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 ∗∂ J ∗ ∂ t ^{\ast }={\frac {\partial J^{\ast }}{\partial t}}} .
One finds that minimizing u } in terms of t , x } , and the unknown function J x ∗ ^{\ast }} and then substitutes the result into the Hamilton–Jacobi–Bellman equation to get the partial differential equation to be solved with boundary condition J ( t 1 )
Salah satu menemukan meminimalkan u } istilah dari t , 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 ( t 1 )
Alternatively, the continuous process can be approximated by a discrete system, which leads to a following recurrence relation analog to the Hamilton–Jacobi–Bellman equation: J k ∗ ( x n − k )min u n − k { f ^ ( x n − k , u n − k ) + J k − 1 ∗ ( g ^ ( x n − k , u n − 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 {\mathbf {g} }}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}} at the k -th stage of n equally spaced discrete time intervals, and where f ^ }} and g ^ }}} denote discrete approximations to f and g } .
Atau, proses kontinu dapat didekati dengan sistem diskrit, yang mengarah ke analog relasi rekurensi berikut dengan persamaan Hamilton – Jacobi – Bellman: J k ∗ ( x n − k )min u n − k { f ^ ( x n − k , u n − k ) + J k − 1 ∗ ( g ^ ( x n − k , u n − 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 di mana f ^ }} dan g ^ }} menunjukkan pendekatan diskrit untuk f dan g } .
This functional equation is known as the Bellman equation, which can be solved for an exact solution of the discrete approximation of the optimization equation.
Persamaan fungsional ini dikenal sebagai persamaan Bellman, yang dapat diselesaikan untuk solusi tepat dari pendekatan diskrit persamaan optimasi.
There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.
Ada dua atribut utama yang harus dimiliki masalah agar pemrograman dinamis dapat diterapkan: substruktur yang optimal dan sub-masalah yang tumpang tindih.
If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead.
Jika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah tidak tumpang tindih, strateginya disebut "divide and conquer".
This is why merge sort and quick sort are not classified as dynamic programming problems.
Inilah sebabnya mengapa merge sort dan quick sort tidak diklasifikasikan sebagai masalah pemrograman dinamis.
Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems.
Substruktur optimal berarti bahwa solusi untuk masalah pengoptimalan yang diberikan dapat diperoleh dengan kombinasi solusi optimal untuk sub-masalahnya.
Such optimal substructures are usually described by means of recursion.
Substruktur optimal seperti itu biasanya dijelaskan melalui rekursi.
Hence, one can easily formulate the solution for finding shortest paths in a recursive manner, which is what the Bellman–Ford algorithm or the Floyd–Warshall algorithm does.
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.
For example, consider the recursive formulation for generating the Fibonacci sequence: FiFi−1 + Fi−2, with base case F1F21.
Misalnya, pertimbangkan formulasi rekursif untuk menghasilkan deret Fibonacci:
Then F43F42 + F41, and F42F41 + F40.
Lalu F43F42 + F41, dan F42F41 + F40.
Now F41 is being solved in the recursive sub-trees of both F43 as well as F42.
Sekarang F41 sedang diselesaikan di sub-pohon rekursif dari keduanya F43 sebaik F42.
Even though the total number of sub-problems is actually small (only 43 of them), we end up solving the same problems over and over if we adopt a naive recursive solution such as this.
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.
Dynamic programming takes account of this fact and solves each sub-problem only once.
Pemrograman dinamis memperhitungkan fakta ini dan memecahkan setiap sub-masalah hanya sekali.
If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memoize or store the solutions to the sub-problems in a table (often an array or hashtable in practice).
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.
Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved.
Setiap kali kita mencoba untuk memecahkan sub-masalah baru, pertama-tama kita memeriksa tabel untuk melihat apakah sudah terpecahkan.
If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.
Jika solusi telah dicatat, kita dapat menggunakannya secara langsung, jika tidak kita menyelesaikan sub-masalah dan menambahkan solusinya ke tabel.
Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems.
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.
This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems.
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.
For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.
Misalnya, jika kita sudah mengetahui nilai F41 dan F40, kita bisa langsung menghitung nilai F42.
Some programming languages can automatically memoize the result of a function call with a particular set of arguments, in order to speed up call-by-name evaluation (this mechanism is referred to as call-by-need).
Beberapa bahasa pemrograman dapat secara otomatis memoisasi hasil panggilan fungsi dengan sekumpulan argumen tertentu, untuk mempercepat evaluasi Call-by-name.
Some languages make it possible portably (e.g. Scheme, Common Lisp, Perl or D).
Beberapa bahasa membuatnya mungkin portabel (misalnya Scheme, Common Lisp, Perl atau D).
Some languages have automatic memoization built in, such as tabled Prolog and J, which supports memoization with the M. adverb.
Beberapa bahasa memiliki memoisasi otomatis bawaan, seperti tabel Prolog dan J, yang mendukung memoization dengan kata keterangan M. .
Memoization is also encountered as an easily accessible design pattern within term-rewrite based languages such as Wolfram Language.
Memoisasi juga ditemukan sebagai pola desain yang mudah diakses dalam bahasa berbasis penulisan-ulang istilah seperti Bahasa Wolfram.
Dynamic programming is widely used in bioinformatics for tasks such as sequence alignment, protein folding, RNA structure prediction and protein-DNA binding.
Pemrograman dinamis banyak digunakan dalam bioinformatika untuk tugas-tugas seperti penyelarasan urutan, pelipatan protein, prediksi struktur RNA, dan pengikatan protein-DNA.
The first dynamic programming algorithms for protein-DNA binding were developed in the 1970s independently by Charles DeLisi in the US and by Georgii Gurskii and Alexander Zasedatelev in the Soviet Union.
Algoritma 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.
Recently these algorithms have become very popular in bioinformatics and computational biology, particularly in the studies of nucleosome positioning and transcription factor binding.
Baru-baru ini algoritma ini menjadi sangat populer dalam bioinformatika dan biologi komputasi, khususnya dalam studi tentang posisi nukleosom dan pengikatan faktor transkripsi.
From a dynamic programming point of view, Dijkstra's algorithm for the shortest path problem is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.
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.
In fact, Dijkstra's explanation of the logic behind the algorithm, namely Problem 2.
Faktanya, penjelasan Dijkstra tentang logika di balik algoritma, dinamakan Masalah 2.
Find the path of minimum total length between two given nodes P and Q .
Temukan jalur dengan panjang total minimum antara dua node yang diberikan P dan Q .
We use the fact that, if R is a node on the minimal path from P to Q , knowledge of the latter implies the knowledge of the minimal path from P to R . is a paraphrasing of Bellman's famous Principle of Optimality in the context of the shortest path problem.
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 .
Using dynamic programming in the calculation of the nth member of the Fibonacci sequence improves its performance greatly.
Menggunakan pemrograman dinamis dalam perhitungan anggota ke-n deret Fibonacci meningkatkan kinerjanya secara signifikan.
Here is a naïve implementation, based directly on the mathematical definition: function fib(n)
Berikut adalah implementasi naif, berdasarkan langsung pada definisi matematis: function fib(n)
fib(n − 2) Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times: fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + (fib(2) + fib(1)) ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
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: fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + (fib(2) + fib(1)) ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
In particular, fib(2) was calculated three times from scratch.
Khususnya, fib(2) dihitung tiga kali dari awal.
In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time algorithm.
Dalam contoh yang lebih besar, lebih banyak nilai fib, atau subproblem, dihitung ulang, yang mengarah ke algoritma waktu eksponensial.
Now, suppose we have a simple map object, m, which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it.
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.
The resulting function requires only O(n) time instead of exponential time (but requires O(n) space): 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] This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.
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.
In the bottom-up approach, we calculate the smaller values of fib first, then build larger values from them.
Dalam pendekatan bottom-up, kita menghitung nilai fib yang lebih kecil terlebih dahulu, lalu buat nilai yang lebih besar darinya.
This method also uses O(n) time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the map. function fib(n)
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.
if n0 return 0 else var previousFib :0, currentFib :1 repeat n − 1 times // loop is skipped if n1 var newFib :previousFib + currentFib previousFib :currentFib currentFib :newFib return currentFib In both examples, we only calculate fib(2) one time, and then use it to calculate both fib(4) and fib(3), instead of computing it every time either of them is evaluated.
if n0 return 0 else var previousFib :0, currentFib :1 repeat n − 1 times // loop is skipped if n1 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.
Typically, the problem consists of transforming one sequence into another using edit operations that replace, insert, or remove an element.
Biasanya, masalahnya terdiri dari mengubah satu urutan menjadi urutan lain menggunakan operasi edit yang mengganti, menyisipkan, atau menghapus elemen.
The cost in cell (i,j) can be calculated by adding the cost of the relevant operations to the cost of its neighboring cells, and selecting the optimum.
Biaya dalam sel (i,j) dapat dihitung dengan menambahkan biaya operasi yang relevan dengan biaya sel tetangganya, dan memilih yang optimal.
Different variants exist, see Smith–Waterman algorithm and Needleman–Wunsch algorithm.
Ada varian yang berbeda, lihat algoritma Smith – Waterman dan algoritma Needleman – Wunsch.
" Adda, Jerome; Cooper, Russell (2003), Dynamic Economics, MIT Press, ISBN 9780262012010.
Adda, Jerome; Cooper, Russell (2003), Dynamic Economics, MIT Press.
Includes an extensive bibliography of the literature in the area, up to the year 1954.
Termasuk bibliografi literatur yang luas di daerah tersebut, hingga tahun 1954.
Dover paperback edition (2003), ISBN 0-486-42809-5. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 978-0-262-03293-3.
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 2nd), MIT Press & McGraw–Hill, ISBN 978-0-262-03293-3. Terutama hal.
Dreyfus, Stuart E.; Law, Averill M. (1977), The Art and Theory of Dynamic Programming, Academic Press, ISBN 978-0-12-221860-6.
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), "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.
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), Control Techniques for Complex Networks, Cambridge University Press, ISBN 978-0-521-88441-9, archived from the original on 2010-06-19.
Meyn, Sean (2007), Teknik Kontrol untuk Jaringan Kompleks, Cambridge University Press, ISBN 978-0-521-88441-9, diarsipkan dari asli tanggal 2010-06-19.
doi:10.1016/0167-6911(91)90020-f. Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989), Recursive Methods in Economic Dynamics, Harvard Univ.
doi:10.1016/0167-6911(91)90020-f. Stokey, Nancy; Lucas, Robert E.; Prescott, Edward (1989), Metode Rekursif dalam Dinamika Ekonomi, Harvard Univ.
An introduction to dynamic programming as an important tool in economic theory.
Pengantar pemrograman dinamis sebagai alat penting dalam teori ekonomi.