Apa itu Pemrograman Dinamis? - IDS Digital College

Apa itu Pemrograman Dinamis?

Pemrograman Dinamis adalah teknik dalam pemrograman komputer yang membantu memecahkan masalah dalam sebuah class secara efisien yang memiliki sub-masalah tumpang tindih dan properti substruktur yang optimal.

Jika ada masalah yang dapat dibagi menjadi sub-masalah, yang pada akhirnya dibagi lagi menjadi sub-masalah yang lebih kecil, dan jika ada tumpang tindih di antara sub-masalah tersebut, maka solusi untuk sub masalah dapat disimpan untuk referensi di masa mendatang. Dengan cara ini, efisiensi CPU dapat ditingkatkan. Metode pemecahan solusi ini disebut sebagai pemrograman dinamis.

Masalah tersebut melibatkan penghitungan berulang kali nilai dari sub-masalah yang sama untuk menemukan solusi optimal.

Contoh Pemrograman Dinamis

Mari kita cari urutkan fibonacci hingga suku ke-5. Deret fibonacci adalah barisan bilangan yang setiap bilangannya merupakan jumlah dari dua bilangan sebelumnya. Misalnya, 0,1,1, 2, 3. Di sini, setiap angka adalah jumlah dari dua angka sebelumnya.

Algoritma

algoritma

 

 

  1. Suku pertama adalah 0.
  2. Suku kedua adalah 1.
  3. Suku ketiga adalah jumlah dari 0 (dari langkah 1) dan 1 (dari langkah 2), yaitu 1.
  4. Suku keempat adalah jumlah dari suku ketiga (dari langkah 3 ) dan suku kedua (dari langkah 2) yaitu 1 + 1 = 2.
  5. Suku kelima adalah jumlah dari suku keempat (dari langkah 4) dan suku ketiga (dari langkah 3) yaitu 2 + 1 = 3.

Jadi,urutan 0,1,1, 2, 3. Di sini, telah menggunakan hasil dari langkah-langkah sebelumnya seperti yang ditunjukkan di bawah ini. Ini disebut pendekatan pemrograman dinamis.

pendekatan pemrograman dinamis

Cara Kerja Pemrograman Dinamis Pemrograman

Pemrograman ini bekerja dengan menyimpan hasil dari sub masalah sehingga ketika solusi mereka perlukan, mereka sudah tersedia dan kita tidak perlu menghitung ulang.

Teknik menyimpan nilai sub-masalah ini disebut memoization. Dengan menyimpan nilai dalam array, kita menghemat waktu untuk perhitungan sub-masalah yang telah kita temui.

dynamic programming

Dinamis pemrograman dengan memoisasi adalah pendekatan top-down untuk pemrograman ini. Dengan membalikkan arah di mana algoritma bekerja yaitu dengan memulai dari kasus dasar dan bekerja menuju solusi, kita juga dapat mengimplementasikan secara bottom-up.

dynamic programming approach

Recursion vs Dynamic Programming Pemrograman

Dynamic Programming sebagian besar diterapkan pada rekursif algoritma. Ini bukan kebetulan, sebagian besar masalah optimasi memerlukan rekursi dan pemrograman dinamis digunakan untuk optimasi.

Namun tidak semua masalah yang menggunakan rekursi dapat menggunakan Dynamic Programming. Kecuali jika ada sub-masalah yang tumpang tindih seperti pada masalah deret fibonacci, rekursi hanya dapat mencapai solusi dengan menggunakan pendekatan pembagian dan penaklukkan.

Itulah alasan mengapa algoritma rekursif seperti Merge Sort tidak dapat menggunakan Pemrograman Dinamis, karena sub-masalah tidak tumpang tindih.

Algoritma Greedy vs Pemrograman Dinamis

Algoritma Greedy mirip dengan dynamic Programming dalam arti bahwa keduanya adalah alat untuk optimasi.

Namun, algoritma Greedy mencari solusi optimal lokal atau dengan kata lain, pilihan Greedy, dengan harapan menemukan optimal global. Oleh karena itu algoritma Greedy dapat membuat tebakan yang terlihat optimal pada saat itu tetapi menjadi mahal dan tidak menjamin optimal secara global.

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

Posted in: News



    WhatsApp chat