Pemrograman dinamis: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Still need veritification and progress |
k Membatalkan 1 suntingan oleh 223.255.229.13 (bicara) ke revisi terakhir oleh InternetArchiveBot Tag: Pembatalan |
||
(17 revisi perantara oleh 4 pengguna tidak ditampilkan) | |||
Baris 1:
[[Berkas:Shortest_path_optimal_substructure.svg|jmpl|200x200px|'''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.]]
'''Pemrograman dinamis''' ({{lang-en|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 [[
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.<ref name=":
== 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''<sub>1</sub>, ''V''<sub>2</sub>, ..., ''V<sub>n</sub>'' mengambil ''y'' sebagai argumen yang mewakili [[Keadaan variabel|'''keadaan''']] sistem pada waktu ''i'' dari 1 sampai ''n''. Definisi ''V<sub>n</sub>''(''y'') adalah nilai yang diperoleh di keadaan ''y'' terakhir kali ''n''. Nilai ''V<sub>i</sub>'' di waktu sebelumnya ''i'' = ''n'' −1, ''n'' − 2, ..., 2, 1 dapat ditemukan dengan bekerja mundur, menggunakan hubungan [[
=== Teori kontrol ===
Baris 29 ⟶ 28:
=== Pemrograman komputer ===
Ada dua atribut utama yang harus dimiliki masalah agar pemrograman dinamis dapat diterapkan: [[Substruktur optimal|substruktur yang optimal]] dan [[Sub-masalah tumpang tindih|sub-masalah yang tumpang tindih]]. Jika suatu masalah dapat diselesaikan dengan menggabungkan solusi optimal untuk sub-masalah ''tidak tumpang tindih'', strateginya disebut "[[Algoritma Divide-and-conquer|divide and conquer]]".<ref name=":02"
''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]].
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<sub>i</sub>'' = ''F<sub>i</sub>''<sub>−1</sub> + ''F<sub>i</sub>''<sub>−2</sub>, dengan kasus dasar ''F''<sub>1</sub> = ''F''<sub>2</sub> = 1. Lalu ''F''<sub>43</sub> = ''F''<sub>42</sub> + ''F''<sub>41</sub>, dan ''F''<sub>42</sub> = ''F''<sub>41</sub> + ''F''<sub>40</sub>. Sekarang ''F''<sub>41</sub> sedang diselesaikan di sub-pohon rekursif dari keduanya ''F''<sub>43</sub> sebaik ''F''<sub>42</sub>. 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.
[[Berkas:Fibonacci_dynamic_programming.svg|jmpl|149x149px|'''Gambar''' '''2.''' Grafik sub-masalah untuk deret Fibonacci. Fakta bahwa ini bukan [[Struktur pohon|pohon]] menunjukkan sub-masalah yang tumpang tindih.]]
Ini dapat dicapai dengan salah satu dari dua cara:
* ''[[Desain top-down dan bottom-up|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.
* ''[[Desain top-down dan bottom-up|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''<sub>41</sub> dan ''F''<sub>40</sub>, kita bisa langsung menghitung nilai ''F''<sub>42</sub>.
Beberapa [[bahasa pemrograman]] dapat secara otomatis [[memoisasi]] hasil panggilan fungsi dengan sekumpulan argumen tertentu, untuk mempercepat evaluasi [[Strategi evaluasi#Call by name|Call-by-name]]. (mekanisme ini disebut sebagai ''[[call-by-need]]''). Beberapa bahasa membuatnya mungkin portabel (misalnya [[Scheme (bahasa pemrograman)|Scheme]], [[Common Lisp]], [[Perl]] atau [[D (bahasa pemrograman)|D]]). Beberapa bahasa memiliki [[memoisasi]] otomatis <!-- masih bukan salah ketik untuk "memor-" --> bawaan, seperti tabel [[Prolog]] dan [[J (programming language)|J]], yang mendukung memoization dengan kata keterangan ''M''. .<ref>{{cite web|title=M. Memo|url=http://www.jsoftware.com/help/dictionary/dmcapdot.htm|work=J Vocabulary|publisher=J Software|accessdate=28 October 2011}}</ref> 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 ===
Baris 52 ⟶ 59:
'''if''' n <= 1 '''return''' n
'''return''' fib(n − 1) + fib(n − 2)
Perhatikan bahwa jika kita sebut, katakanlah, <code>fib(5)</code>,
# <code>fib(5)</code>
Baris 60 ⟶ 67:
# <code>(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>
Khususnya, <code>fib(2)</code> dihitung tiga kali dari awal. Dalam contoh yang lebih besar, lebih banyak nilai <code>fib</code>, atau ''subproblem'', dihitung ulang, yang mengarah ke algoritme waktu eksponensial.
Sekarang, misalkan kita memiliki objek [[Array asosiatif|peta]] sederhana, ''m'', yang memetakan setiap nilai <code>fib</code> yang telah dihitung ke hasilnya, dan
'''var''' m := '''''map'''''(0 → 0, 1 → 1)
'''function''' fib(n)
Baris 70 ⟶ 77:
Teknik menyimpan nilai yang telah dihitung ini disebut ''[[Memoisasi|memoization]]''; <!-- Ya, memoisasi, bukan memorization. Bukan salah ketik. -->ini adalah pendekatan top-down, karena kita pertama kali memecah masalah menjadi subproblem lalu menghitung dan menyimpan nilai.
Dalam pendekatan '''bottom-up''',
'''function''' fib(n)
'''if''' n = 0
Baris 81 ⟶ 88:
currentFib := newFib
'''return''' currentFib
Dalam kedua contoh tersebut,
Metode di atas sebenarnya membutuhkan <math>\Omega(n^2) </math> waktu untuk n besar karena penjumlahan dua bilangan bulat dengan <math>\Omega(n)</math> bit masing-masing mengambil <math>\Omega(n)</math> waktu. (Nomor ''n''<sup>th</sup> fibonacci memiliki <math>\Omega(n)</math> bit.) Juga, ada bentuk tertutup untuk deret Fibonacci, [[Jacques Philippe Marie Binet#Rumus angka Fibonacci Binet|yang dikenal sebagai rumus Binet]], yang darinya suku <math>n</math>-th [[Kompleksitas komputasi operasi matematika|dihitung]] kira-kira <math>O(n(\log n)^2)</math> waktu, yang lebih efisien daripada teknik pemrograman dinamis di atas. Namun, pengulangan sederhana secara langsung memberikan [[Angka Fibonacci#Bentuk matriks|bentuk matriks]] yang mengarah ke perkiraan <math>O(n\log n)</math> algoritma dengan [[
=== Perataan urutan ===
Dalam genetika, [[perataan urutan]] adalah aplikasi penting di mana pemrograman dinamis sangat penting.<ref name="Eddy" /> 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 [[Edit jarak|urutan pengeditan dengan total biaya terendah]].
Masalahnya dapat dinyatakan secara alami sebagai rekursi, urutan A diedit secara optimal menjadi urutan B dengan baik:
# memasukkan karakter pertama B, dan melakukan penyelarasan optimal A dan ekor B
# menghapus karakter pertama A, dan melakukan penyelarasan optimal pada ekor A dan B
# 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.]]
▲Metode di atas sebenarnya membutuhkan <math>\Omega(n^2) </math> waktu untuk n besar karena penjumlahan dua bilangan bulat dengan <math>\Omega(n)</math> bit masing-masing mengambil <math>\Omega(n)</math> waktu. (Nomor ''n''<sup>th</sup> fibonacci memiliki <math>\Omega(n)</math> bit.) Juga, ada bentuk tertutup untuk deret Fibonacci, [[Jacques Philippe Marie Binet#Rumus angka Fibonacci Binet|yang dikenal sebagai rumus Binet]], yang darinya suku <math>n</math>-th [[Kompleksitas komputasi operasi matematika|dihitung]] kira-kira <math>O(n(\log n)^2)</math> waktu, yang lebih efisien daripada teknik pemrograman dinamis di atas. Namun, pengulangan sederhana secara langsung memberikan [[Angka Fibonacci#Bentuk matriks|bentuk matriks]] yang mengarah ke perkiraan <math>O(n\log n)</math> algoritma dengan [[eksponen matriks]] cepat.
== Referensi ==
Baris 90 ⟶ 110:
== Bacaan lanjutan ==
* {{citation|last1=Adda|first1=Jerome|last2=Cooper|first2=Russell|year=2003|url=https://mitpress.mit.edu/books/dynamic-economics|title=Dynamic Economics|publisher=MIT Press}}. Pengenalan yang dapat diakses untuk pemrograman dinamis di bidang ekonomi. [https://sites.google.com/site/coopereconomics/matlab-programs MATLAB code for the book] {{Webarchive|url=https://web.archive.org/web/20201009085820/https://sites.google.com/site/coopereconomics/matlab-programs |date=2020-10-09 }}.
* {{citation|first=Richard|last=Bellman|authorlink=Richard Bellman|title=
* {{citation|first=Richard|last=Bellman|authorlink=Richard Bellman|year=1957|title=Dynamic Programming|publisher=Princeton University Press}}. Edisi paperback Dover (2003), {{isbn|0-486-42809-5}}.
* {{citation|last1=Cormen|first4=Clifford|isbn=978-0-262-03293-3|publisher=MIT Press & McGraw–Hill|edition=2nd|title=Introduction to Algorithms|year=2001|author4-link=Clifford Stein|last4=Stein|first1=Thomas H.|author3-link=Ronald L. Rivest|first3=Ronald L.|last3=Rivest|author2-link=Charles E. Leiserson|first2=Charles E.|last2=Leiserson|author1-link=Thomas H. Cormen|title-link=Introduction to Algorithms}}. Terutama hal. 323–69.
* {{citation|first1=Stuart E.|last1=Dreyfus|first2=Averill M.|last2=Law|year=1977|title=
* {{citation|last1=Giegerich|first1=R.|last2=Meyer|first2=C.|last3=Steffen|first3=P.|year=2004|url=http://bibiserv.techfak.uni-bielefeld.de/adp/ps/GIE-MEY-STE-2004.pdf|title=
* {{citation|first=Sean|last=Meyn|url=https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html|title=
* {{cite journal|last1=Sritharan|first1=S. S.|date=|year=1991|title=
* {{citation|last1=Stokey|first1=Nancy|author1-link=Nancy Stokey|last2=Lucas|first2=Robert E.|author2-link=Robert E. Lucas|last3=Prescott|first3=Edward|author3-link=Edward Prescott|year=1989|title=
== Pranala luar ==
Baris 108 ⟶ 128:
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Dynamic Programming: from novice to advanced] sebuah artikel TopCoder.com oleh Dumitru tentang Pemrograman Dinamis
* [https://bibiserv.cebitec.uni-bielefeld.de/adp/welcome.html Algebraic Dynamic Programming] – kerangka kerja formal untuk pemrograman dinamis, termasuk [https://bibiserv.cebitec.uni-bielefeld.de/cgi-bin/dpcourse kursus tingkat awal] kepada DP, University of Bielefeld
* Dreyfus, Stuart, "[http://www.cas.mcmaster.ca/~se3c03/journal_papers/dy_birth.pdf Richard Bellman on the birth of Dynamic Programming.] {{Webarchive|url=https://web.archive.org/web/20201013233916/http://www.cas.mcmaster.ca/~se3c03/journal_papers/dy_birth.pdf |date=2020-10-13 }}"
* [https://web.archive.org/web/20080626183359/http://www.avatar.se/lectures/molbioinfo2001/dynprog/dynamic.html Tutorial pemrograman dinamis]
* [http://www.cambridge.org/resources/0521882672/7934_kaeslin_dynpro_new.pdf Pengantar Lembut tentang Pemrograman Dinamis dan Algoritma Viterbi]
* Prolog Tabel [http://www.probp.com BProlog] dan [http://xsb.sourceforge.net/ XSB]
* [https://ifors.ms.unimelb.edu.au/tutorial/
{{Authority control}}
|