Struktur Data - Pemrograman Dinamis

Pendekatan pemrograman dinamis mirip dengan membagi dan menaklukkan dalam memecah masalah menjadi masalah yang lebih kecil namun lebih kecil. Tetapi tidak seperti, bagi dan taklukkan, sub-masalah ini tidak diselesaikan secara mandiri. Sebaliknya, hasil dari sub-masalah yang lebih kecil ini diingat dan digunakan untuk sub-masalah yang serupa atau tumpang tindih.

Pemrograman dinamis digunakan di mana kita memiliki masalah, yang dapat dibagi menjadi sub-sub masalah yang serupa, sehingga hasilnya dapat digunakan kembali. Sebagian besar, algoritma ini digunakan untuk pengoptimalan. Sebelum menyelesaikan sub-masalah yang ada, algoritma dinamis akan mencoba untuk memeriksa hasil dari sub-masalah yang telah diselesaikan sebelumnya. Solusi dari sub-masalah digabungkan untuk mencapai solusi terbaik.

Jadi kami dapat mengatakan bahwa -

• Masalah harus dapat dibagi menjadi sub-masalah kecil yang tumpang tindih.

• Solusi optimal dapat dicapai dengan menggunakan solusi optimal dari sub-masalah yang lebih kecil.

• Algoritma dinamis menggunakan Memoization.

Perbandingan

Berbeda dengan algoritme serakah, di mana pengoptimalan lokal ditangani, algoritme dinamis dimotivasi untuk pengoptimalan masalah secara keseluruhan.

Berbeda dengan algoritma membagi dan menaklukkan, di mana solusi digabungkan untuk mencapai solusi keseluruhan, algoritma dinamis menggunakan keluaran dari sub-masalah yang lebih kecil dan kemudian mencoba untuk mengoptimalkan sub-masalah yang lebih besar. Algoritme dinamis menggunakan Memoisasi untuk mengingat keluaran dari sub-masalah yang sudah terpecahkan.

Contoh

Masalah komputer berikut ini dapat diselesaikan dengan menggunakan pendekatan pemrograman dinamis -

• Deret angka Fibonacci
• Masalah ransel
• Menara Hanoi
• Semua pasangan jalur terpendek oleh Floyd-Warshall
• Jalur terpendek oleh Dijkstra
• Penjadwalan proyek

Pemrograman dinamis dapat digunakan dengan cara top-down dan bottom-up. Dan tentu saja, seringkali, mengacu pada keluaran solusi sebelumnya lebih murah daripada menghitung ulang dalam hal siklus CPU.