PEMROGRAMAN DINAMIS: KARAKTERISTIK, CONTOH, KELEBIHAN, KEKURANGAN - TEKNOLOGI - 2024

The pemrograman dinamis adalah algoritma model yang memecahkan masalah yang kompleks dengan membagi itu menjadi submasalah, menyimpan hasil daripadanya untuk menghindari harus menghitung ulang hasil.

Jadwal ini digunakan ketika Anda memiliki masalah yang dapat dibagi menjadi subproblem serupa, sehingga hasilnya dapat digunakan kembali. Sebagian besar, jadwal ini digunakan untuk pengoptimalan.

Pemrograman dinamis. Sub masalah ditumpangkan dalam deret Fibonacci. Sumber: Wikimedia commons, en: Pengguna: Dcoatzee, dilacak oleh Pengguna: Stannered / Domain publik

Sebelum menyelesaikan subproblem yang tersedia, algoritme dinamis akan mencoba memeriksa hasil dari subproblem yang diselesaikan sebelumnya. Solusi untuk submasalah digabungkan untuk mencapai solusi terbaik.

Daripada menghitung subproblem yang sama berulang kali, Anda dapat menyimpan solusi Anda di beberapa memori, saat Anda pertama kali menemukan subproblem ini. Ketika muncul lagi selama solusi dari subproblem lain, solusi yang sudah disimpan di memori akan diambil.

Ini adalah ide bagus untuk memperbaiki waktu memori, di mana menggunakan ruang tambahan dapat meningkatkan waktu yang dibutuhkan untuk menemukan solusi.

Fitur pemrograman dinamis

Karakteristik penting berikut adalah masalah yang harus Anda hadapi sebelum pemrograman dinamis dapat diterapkan:

Substruktur yang optimal

Karakteristik ini menyatakan bahwa masalah optimasi dapat diselesaikan dengan menggabungkan solusi optimal dari masalah sekunder yang menyusunnya. Substruktur optimal ini dijelaskan dengan rekursi.

Misalnya, dalam grafik, substruktur optimal akan disajikan di jalur terpendek r yang beranjak dari simpul s ke simpul t:

Artinya, dalam jalur terpendek ini r setiap simpul antara i dapat diambil. Jika r benar-benar merupakan rute terpendek, maka dapat dibagi menjadi subroute r1 (dari s ke i) dan r2 (dari i ke t), sedemikian rupa sehingga ini pada gilirannya merupakan rute terpendek antara simpul yang sesuai.

Oleh karena itu, untuk menemukan jalur terpendek, solusinya dapat dengan mudah diformulasikan secara rekursif, yang dilakukan oleh algoritma Floyd-Warshall.

Submasalah yang tumpang tindih

Ruang subproblem harus kecil. Artinya, algoritme rekursif apa pun yang memecahkan masalah harus menyelesaikan subproblem yang sama berulang kali, alih-alih membuat subproblem baru.

Sebagai contoh, untuk menghasilkan deret Fibonacci, rumus rekursif ini dapat digunakan sebagai berikut: Fn = F (n - 1) + F (n - 2), dengan asumsi bahwa F1 = F2 = 1. Maka kita akan mendapatkan: F33 = F32 + F31, dan F32 = F31 + F30.

Seperti yang Anda lihat, F31 sedang diselesaikan menjadi subpohon rekursif dari F33 dan F32. Meskipun jumlah total subproblem sangat kecil, jika Anda mengadopsi solusi rekursif seperti ini, Anda akan menyelesaikan masalah yang sama berulang kali.

Ini diperhitungkan oleh pemrograman dinamis, sehingga menyelesaikan setiap subproblem hanya sekali. Ini dapat dilakukan dengan dua cara:

Pendekatan atas ke bawah

Jika solusi untuk masalah apa pun dapat dirumuskan secara rekursif menggunakan solusi subproblemnya, dan jika subproblem ini tumpang tindih, solusi untuk subproblem tersebut dapat dengan mudah diingat atau disimpan dalam tabel.

Setiap kali solusi subproblem baru dicari, tabel akan diperiksa untuk melihat apakah solusi tersebut telah diselesaikan sebelumnya. Jika suatu solusi disimpan, itu akan digunakan alih-alih menghitungnya lagi. Jika tidak, submasalah akan diselesaikan, dengan menyimpan solusi dalam tabel.

Pendekatan bottom-up

Setelah solusi dari suatu masalah dirumuskan secara rekursif dalam subproblemnya, adalah mungkin untuk mencoba merumuskan kembali masalah dengan cara ke atas: pertama, kita akan mencoba untuk memecahkan subproblem dan menggunakan solusinya untuk sampai pada solusi untuk submasalah yang lebih besar.

Ini juga umumnya dilakukan dalam bentuk tabel, yang secara berulang menghasilkan solusi untuk sub masalah yang lebih besar dan lebih besar dengan menggunakan solusi untuk sub masalah yang lebih kecil. Misalnya jika nilai F31 dan F30 sudah diketahui maka nilai F32 bisa langsung dihitung.

Perbandingan dengan teknik lain

Salah satu fitur penting dari masalah yang dapat diselesaikan dengan pemrograman dinamis adalah bahwa subproblem harus tumpang tindih. Inilah yang membedakan pemrograman dinamis dari teknik divide and conquer, di mana tidak perlu menyimpan nilai yang paling sederhana.

Ini mirip dengan rekursi, karena saat menghitung kasus dasar, nilai akhir dapat ditentukan secara induktif. Pendekatan bottom-up ini bekerja dengan baik ketika nilai baru hanya bergantung pada nilai yang dihitung sebelumnya.

Contoh

Langkah minimum untuk mencapai 1

Untuk setiap bilangan bulat positif "e" salah satu dari tiga langkah berikut dapat dilakukan.

- Kurangi 1 dari angka tersebut. (e = e-1).

- Jika habis dibagi 2, dibagi 2 (jika e% 2 == 0, maka e = e / 2).

- Jika habis dibagi 3, dibagi 3 (jika e% 3 == 0, maka e = e / 3).

Berdasarkan langkah-langkah di atas, jumlah minimum dari langkah-langkah ini harus ditemukan untuk membawa e ke 1. Misalnya:

- Jika e = 1, hasil: 0.

- Jika e = 4, hasilnya: 2 (4/2 = 2/2 = 1).

- Saat e = 7, hasil: 3 (7-1 = 6/3 = 2/2 = 1).

Fokus

Orang mungkin berpikir untuk selalu memilih langkah yang membuat n serendah mungkin dan terus seperti ini, hingga mencapai 1. Namun, terlihat bahwa strategi ini tidak berhasil di sini.

Misalnya, jika e = 10, langkah-langkahnya adalah: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 langkah). Namun, bentuk optimalnya adalah: 10-1 = 9/3 = 3/3 = 1 (3 langkah). Oleh karena itu, semua kemungkinan langkah yang dapat dilakukan untuk setiap nilai n yang ditemukan harus dicoba, memilih jumlah minimum dari kemungkinan ini.

Semuanya dimulai dengan rekursi: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} if e> 1, mengambil kasus dasar: F (1) = 0. Memiliki persamaan pengulangan, Anda dapat mulai membuat kode rekursi.

Namun, terlihat bahwa subproblemnya tumpang tindih. Lebih lanjut, solusi optimal untuk masukan yang diberikan bergantung pada solusi optimal dari submasalahnya.

Seperti dalam menghafal, di mana solusi dari submasalah yang diselesaikan disimpan untuk digunakan nanti. Atau seperti dalam pemrograman dinamis, Anda mulai dari bawah, bekerja sampai ke e yang diberikan. Lalu kedua kode tersebut:

Hafalan

Pemrograman bottom-up yang dinamis

Keuntungan

Salah satu keuntungan utama menggunakan pemrograman dinamis adalah mempercepat pemrosesan, karena digunakan referensi yang telah dihitung sebelumnya. Karena ini adalah teknik pemrograman rekursif, ini mengurangi baris kode dalam program.

Algoritme yang rakus vs pemrograman dinamis

Algoritme serakah mirip dengan pemrograman dinamis karena keduanya adalah alat untuk pengoptimalan. Namun, algoritme greedy mencari solusi optimal di setiap langkah lokal. Artinya, ia mencari pilihan rakus dengan harapan menemukan optimal global.

Oleh karena itu, algoritma greedy dapat membuat asumsi yang terlihat optimal pada saat itu, tetapi menjadi mahal di masa mendatang dan tidak menjamin optimal secara global.

Di sisi lain, pemrograman dinamis menemukan solusi optimal untuk sub-masalah dan kemudian membuat pilihan yang tepat dengan menggabungkan hasil dari sub-masalah tersebut untuk benar-benar menemukan solusi yang paling optimal.

Kekurangan

- Banyak memori diperlukan untuk menyimpan hasil kalkulasi dari setiap subproblem, tanpa dapat menjamin bahwa nilai yang disimpan akan digunakan atau tidak.

- Sering kali, nilai keluaran disimpan tanpa pernah digunakan di subproblem berikut selama eksekusi. Ini menyebabkan penggunaan memori yang tidak perlu.

- Dalam pemrograman dinamis, fungsi dipanggil secara rekursif. Ini membuat memori tumpukan terus meningkat.

Pemrograman rekursi vs dinamis

Jika Anda memiliki memori terbatas untuk menjalankan kode dan kecepatan pemrosesan tidak menjadi perhatian, Anda dapat menggunakan rekursi. Misalnya, jika Anda mengembangkan aplikasi seluler, memori sangat terbatas untuk menjalankan aplikasi.

Jika Anda ingin program berjalan lebih cepat dan tidak memiliki batasan memori, sebaiknya gunakan pemrograman dinamis.

Aplikasi

Pemrograman dinamis adalah metode efektif untuk memecahkan masalah yang mungkin tampak sangat sulit dipecahkan dalam waktu yang wajar.

Algoritma yang didasarkan pada paradigma pemrograman dinamis digunakan di banyak bidang sains, termasuk banyak contoh dalam kecerdasan buatan, dari perencanaan pemecahan masalah hingga pengenalan ucapan.

Algoritma berdasarkan pemrograman dinamis

Pemrograman dinamis cukup efektif dan bekerja dengan sangat baik untuk berbagai masalah. Banyak algoritma dapat dilihat sebagai aplikasi algoritma serakah, seperti:

- Deret angka Fibonacci.

- Menara Hanoi.

- Semua pasang rute yang lebih pendek melalui Floyd-Warshall.

- Masalah ransel.

- Penjadwalan proyek.

- Jalan terpendek melalui Dijkstra.

- Kontrol penerbangan dan kontrol robotika.

- Masalah pengoptimalan matematika.

- Timeshare: jadwalkan pekerjaan untuk memaksimalkan penggunaan CPU.

Deret angka Fibonacci

Angka Fibonacci adalah angka-angka yang ditemukan dalam urutan berikut: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, dll.

Dalam terminologi matematika, urutan Fn dari bilangan Fibonacci ditentukan oleh rumus pengulangan: F (n) = F (n -1) + F (n -2), di mana F (0) = 0 dan F ( 1) = 1.

Pendekatan atas ke bawah

Dalam contoh ini, larik pencarian dengan semua nilai awal diinisialisasi dengan -1. Kapan pun solusi untuk subproblem diperlukan, matriks pencarian ini akan dicari terlebih dahulu.

Jika nilai yang dihitung ada, maka nilai itu akan dikembalikan. Jika tidak, hasilnya akan dihitung untuk disimpan dalam larik pencarian sehingga dapat digunakan kembali nanti.

Pendekatan bottom-up

Dalam hal ini, untuk deret Fibonacci yang sama, f (0) dihitung terlebih dahulu, kemudian f (1), f (2), f (3), dan seterusnya. Jadi, solusi dari submasalah sedang dibangun dari bawah ke atas.

Referensi

1. Vineet Choudhary (2020). Pengantar Pemrograman Dinamis. Developer Insider Diambil dari: developerinsider.co.
2. Alex Allain (2020). Pemrograman Dinamis di C ++. Pemrograman C. Diambil dari: cprogramming.com.
3. After Academy (2020). Ide Pemrograman Dinamis. Diambil dari: afteracademy.com.
4. Aniruddha Chaudhari (2019). Pemrograman dan Rekursi Dinamis - Perbedaan, Keuntungan dengan Contoh. CSE Stack. Diambil dari: csestack.org.
5. Code Chef (2020). Tutorial Untuk Pemrograman Dinamis. Diambil dari: codechef.com.
6. Programiz (2020). Pemrograman Dinamis. Diambil dari: programiz.com.