Wikipedia

Pemrograman dinamis: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
need more veritification
k Membatalkan 1 suntingan oleh 223.255.229.13 (bicara) ke revisi terakhir oleh InternetArchiveBot
Tag: Pembatalan
 
(6 revisi perantara oleh 4 pengguna tidak ditampilkan)
Baris 2:
'''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 [[Rekursi|rekursifrekursi]]f. 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 optimal|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.<ref name=":002">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.</ref> 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''<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''&nbsp;=&nbsp;''n''&nbsp;&#x2212;1,&nbsp;''n''&nbsp;&#x2212;&nbsp;2,&nbsp;...,&nbsp;2,&nbsp;1 dapat ditemukan dengan bekerja mundur, menggunakan hubungan [[Rekursi|rekursifrekursi]]f yang disebut [[persamaan Bellman]]. untuk ''i''&nbsp;=&nbsp;2,&nbsp;...,&nbsp;''n'', ''V<sub>i</sub>''<sub>&#x2212;1</sub> di setiap keadaan ''y'' dihitung dari ''V<sub>i</sub>'' dengan memaksimalkan fungsi sederhana (biasanya jumlah) keuntungan dari keputusan pada saat itu ''i''&nbsp;&#x2212;&nbsp;1 dan fungsi ''V<sub>i</sub>'' di keadaan baru sistem jika keputusan ini dibuat. Sejak ''V<sub>i</sub>'' telah dihitung untuk keadaan yang diperlukan, hasil operasi di atas ''V<sub>i</sub>''<sub>&#x2212;1</sub> untuk keadaan tersebut. Akhirnya, ''V''<sub>1</sub> 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 ===
Baris 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">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.</ref> Inilah sebabnya mengapa [[merge sort]] dan [[Quicksort|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<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]].
Baris 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 kita memodifikasi fungsi kita untuk menggunakannya dan memperbaruinya. Fungsi yang dihasilkan hanya membutuhkan [[Notasi O besar|O]](''n'') waktu, bukan waktu eksponensial (tetapi membutuhkan [[Notasi O besar|O]](''n'') ruang):
Baris 93:
 
=== 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:
Baris 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=TheTeori theorypemrograman of dynamic programmingdinamis|journal=[[Bulletin of the American Mathematical Society]]|year=1954|volume=60|pages=503–516|doi=10.1090/S0002-9904-1954-09848-8|mr=0067459|issue=6|doi-access=free}}. Termasuk bibliografi literatur yang luas di daerah tersebut, hingga tahun 1954.
* {{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.&nbsp;323–69.
* {{citation|first1=Stuart E.|last1=Dreyfus|first2=Averill M.|last2=Law|year=1977|title=TheSeni Artdan andTeori TheoryPemrograman of Dynamic ProgrammingDinamis|publisher=Academic Press|isbn=978-0-12-221860-6}}.
* {{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=ASebuah DisciplineDisiplin ofPemrograman DynamicDinamis Programmingatas overData Sequence DataUrutan|journal=Science of Computer Programming|volume=51|pages=215–263|issue=3|doi=10.1016/j.scico.2003.12.005}}.
* {{citation|first=Sean|last=Meyn|url=https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html|title=ControlTeknik TechniquesKontrol foruntuk ComplexJaringan NetworksKompleks|publisher=Cambridge University Press|year=2007|isbn=978-0-521-88441-9|url-status=dead|archiveurl=https://web.archive.org/web/20100619011046/https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html|archivedate=2010-06-19|df=}}.
* {{cite journal|last1=Sritharan|first1=S. S.|date=|year=1991|title=DynamicPemrograman ProgrammingDinamis of thePersamaan Navier-Stokes Equations|url=|journal=Systems and Control Letters|volume=16|issue=4|pages=299–307|doi=10.1016/0167-6911(91)90020-f}}
* {{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=RecursiveMetode MethodsRekursif indalam EconomicDinamika DynamicsEkonomi|publisher=Harvard Univ. Press|isbn=978-0-674-75096-8}}.
 
== Pranala luar ==
Baris 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]
Diperoleh dari "https://wiki-indonesia.club/wiki/Pemrograman_dinamis"