Apa itu Pemrograman Dinamis?

Dalam hal pemrograman komputer, pemrograman dinamis serba guna seperti halnya matematika. Richard Bellman menciptakan teknik ini di tahun 50-an, dan sejak itu ditemukan kegunaannya dalam segala hal mulai dari teknik penerbangan hingga ekonomi.

Dalam kedua konteks, kata tersebut mengacu pada penguraian topik yang rumit menjadi bagian-bagian yang dapat dikelola. Keputusan multi-tahun biasanya pecah secara rekursif. Dalam ilmu komputer, suatu isu memiliki substruktur yang optimal jika dapat ditangani secara optimal dengan membedahnya menjadi sub-masalah dan secara rekursif mencari solusi terbaik.

Ada hubungan antara nilai masalah utama dan nilai submasalah jika submasalah dapat disarangkan secara rekursif di dalam masalah utama dan teknik pemrograman dinamis dapat digunakan untuk menyelesaikan masalah utama. Di bidang pengoptimalan, persamaan Bellman adalah cara terkenal untuk membicarakan tautan khusus ini untuk strategi yang lebih baik.

Anda dapat mempelajari rekayasa perangkat lunak dengan bantuan kursus online.

Optimasi Matematika

Dengan mendekomposisi pilihan yang kompleks menjadi serangkaian pilihan inkremental, seperti yang dilakukan dalam pemrograman dinamis, masalah optimisasi matematis dapat dibuat jauh lebih mudah dikelola untuk operasi. Untuk mencapai ini, kita mendefinisikan sekumpulan fungsi nilai V1, V2,…, Vn yang masing-masing menggunakan y sebagai argumen untuk menjelaskan keadaan sistem pada saat tertentu dalam waktu I dari 0 sampai n. Vn(y) adalah nilai pada waktu n yang diperoleh dari keadaan y. Dengan menggunakan hubungan rekursif yang dikenal sebagai persamaan Bellman, kita dapat menentukan nilai Vi pada periode sebelumnya I = n1, n2,…, 2, 1. Dengan memaksimalkan fungsi sederhana (seringkali penjumlahan) dari manfaat pilihan pada waktu I 1 dan fungsi Vi pada keadaan sistem yang baru, kita dapat menurunkan Vi1 pada keadaan y manapun dari Vi, di mana I = 2,…, n. Prosedur ini mengembalikan Vi1 untuk keadaan yang diperlukan karena Vi telah dihitung untuk keadaan tersebut. Dan terakhir, nilai solusi optimal, V1, ditemukan pada kondisi awal sistem. Dengan menelusuri kembali langkah-langkah dari perhitungan sebelumnya, nilai optimal dari variabel pilihan dapat diambil satu per satu.

Agar pemrograman dinamis menjadi berguna, suatu masalah harus memiliki dua karakteristik: substruktur yang optimal dan sub-masalah yang tumpang tindih. Istilah "membagi dan menaklukkan" digunakan untuk merujuk pada teknik di mana kesulitan dipecah menjadi masalah yang lebih kecil dan independen dan kemudian diselesaikan dengan menggabungkan jawaban terbaik untuk masing-masing. Inilah sebabnya kami tidak menganggap jenis gabungan dan jenis cepat sebagai kesulitan pemrograman dinamis.

Program sertifikat rekayasa perangkat lunak dapat meningkatkan keterampilan Anda.

Masalah optimisasi dengan substruktur yang optimal dapat diselesaikan dengan menggabungkan solusi untuk submasalahnya. Substruktur ideal biasanya didefinisikan melalui rekursi. Setiap simpul perantara memenangkan jalur terpendek p dari simpul u ke simpul v dalam graf G=(V,E) adalah contoh substruktur optimal. Jika lintasan p adalah yang terpendek, ia dapat dibagi menjadi dua lintasan, p1 dari u ke w dan p2 dari w ke v, yang juga merupakan lintasan terpendek di antara pasangan simpulnya masing-masing. Dengan demikian, algoritma Bellman-Ford dan Floyd-Warshall menggunakan rekursi untuk menemukan jalur terpendek.

Apa Logika Di Balik Menggunakan Metode Pemrograman Dinamis?

Prosedur pemrograman dinamis adalah sebagai berikut:

1. Dengan demikian, ini mengurangi kompleksitas semua aspek dari masalah aslinya.
2. Untuk mengatasi masalah yang lebih kecil ini, ini menentukan jawaban terbaik yang mungkin.
3. Itu melacak solusi untuk tantangan yang lebih kecil (memoisasi). Menghafal adalah tindakan mengingat solusi untuk masalah yang lebih kecil.
4. Itu mendaur ulang mereka sedemikian rupa sehingga bagian yang sama dari masalah dapat diselesaikan beberapa kali.
5. Setelah semua itu, Anda perlu mencari tahu jawaban untuk masalah yang sulit.

1. Substruktur optimal dan masalah dengan submasalah yang tumpang tindih. Dalam konteks ini, istilah "substruktur optimal" mengacu pada metode di mana masalah optimisasi dapat diselesaikan dengan mengintegrasikan solusi terbaik ke submasalah konstituennya.
2. Karena hasil antara harus disimpan, kompleksitas ruang pemrograman dinamis meningkat bahkan ketika kompleksitas waktu menurun.