Algoritma - Dynamic Program

Pada materi lalu sudah kita bahas tentang divide dan conquer, dan beberapa contoh aplikasi darinya, namun dalam algoritma ada juga yang biasa disebut Dynamic programming approach atau Pendekatan pemrograman dinamis. Teknik perancangan algoritma ini mempunyai kemiripan dengan divide dan conquer yaitu menyelesaikan permasalahan yang begitu kompleks dengan cara memecah permasalahan tersebut menjadi banyak sub-permasalahan namun bedanya sub-masalah ini tidak terpecahkan secara mandiri, hasil dari sub-masalah yang lebih kecil ini diingat dan digunakan untuk sub-masalah yang sama atau tumpang tindih. Sehingga dapat disimpulkan dynamic programming menggunakan kembali hasil kalkulasi sub-masalah yang telah dilakukan sebelumnya.

Sebagian besar dari algoritma ini digunakan untuk optimasi sehingga ketika akan menyelesaikan sub-masalah, algoritma dinamis akan mencoba memeriksa hasil dari sub-masalah yang dipecahkan sebelumnya. Solusi dari sub-masalah digabungkan untuk mencapai solusi terbaik.

Urutan pelaksanaan teknik ini terlebih dahulu masalahnya harus dapat dibagi menjadi sub-masalah yang tumpang tindih yang lebih kecil. Kemudian solusi optimal dapat dicapai dengan menggunakan solusi optimal dari sub-masalah yang lebih kecil. Disini algoritma dinamis menggunakan output dari sub-masalah yang lebih kecil tadi dan kemudian mencoba untuk mengoptimalkan sub-masalah yang lebih besar. Algoritma dinamis menggunakan Memoization untuk mengingat output dari sub-masalah yang sudah dipecahkan.

Kompleksitas waktu pada algoritma ini:

  • Jika ada jumlah sub-masalah polinomial.
  • Jika setiap sub-masalah dapat dihitung dalam waktu polinomial.
  • Maka solusinya dapat ditemukan dalam waktu polinomial.

Masalah komputer berikut dapat diselesaikan dengan menggunakan pendekatan pemrograman dinamis antara lain Fibonacci number series, Knapsack problem, Tower of Hanoi. Pemrograman dinamis dapat digunakan dengan cara top-down dan bottom-up. Dan tentu saja, sebagian besar waktu, mengacu pada output solusi sebelumnya lebih murah daripada recomputing dalam hal siklus CPU.

Selesaikan secara rekursif masalah - top-down berdasarkan solusi untuk sub-masalah. Temukan urutan bottom-up untuk menghitung semua sub-masalah. Maka Time complexity atau Kompleksitas waktu:

  • Jika ada jumlah sub-masalah polinomial.
  • Jika setiap sub-masalah dapat dihitung dalam waktu polinomial.
  • Maka solusinya dapat ditemukan dalam waktu polinomial.

Namun Penggunaan Dynamic Programming ini jika tidak dilakukan secara tepat berakibat ketidakefisienan biaya atau waktu sehingga dalam penggunaan Dynamic Programming diperlukan keahlian, pengetahuan, ataupun teknik dalam merumuskan suatu masalah yang kompleks, terutama yang berkaitan dengan penetapan fungsi transformasi dari permasalahan tersebut. Selain itu masalah dimensionalitas menjadi masalah pokok karena akan terjadi peningkatan variabel keadaan yang digunakan dalam perhitungan pemrograman dinamis akan menambah beban memori komputer serta menambah lama waktu perhitungan.

Untuk mempermudah penjelasan, mari kita selesaikan masalah sederhana yang telah kita bahas berkali-kali: perhitungan bilangan fibonacci. Algoritma untuk menyelesaikan perhitungan Fibonacci

Bilangan Fibonacci adalah bilangan dari deret bilangan berikut 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…

Definisi Rekursif:

Algoritma dibuat dengan menggunakan Metode Rekursif + Program Dinamis dimana spesifikasi bilangan fibonacci yang telah disebutkan sebelumnya. Dengan menggunakan rumus fn = fn -1 + fn-2 dan nilai awal f0 = 0 dan f1 = 1 maka dapat disusun beberapa algoritma untuk menghasilkan bilangan Fibonacci.

images1

penggunaan program seperti ini:

def fibonacci(n):
    if n <= 2:
        hasil = 1
    else:
        hasil = fibonacci(n - 1) + fibonacci(n - 2)

    return hasil

Komputasi Rekursif Top-Down:

Function Fibo(n)
If n = 0 then return (0)
If n = 1 then return (1)
return ( Fibo( n-1)+Fibo(n-2))

Algoritma diatas menerima input berupa urutan suatu bilangan pada deret bilangan Fibonacci. Jika input yang dimasukkan adalah 0 atau bilangan Fibonacci ke-0 maka akan langsung mengembalikan nilai 0, jika input yang dimasukkan adalah 1 maka akan langsung mengembalikan nilai 1.

Maka input selain kedua nilai 0 dan 1, maka fungsi diatas mengembalikan bilangan Fibonacci ke-(input - 1) ditambah bilangan Fibonacci ke(input – 2), di bagian inilah metoda rekursif digunakan yaitu dengan memanggil fungsi yang merupakan dirinya sendiri. Dengan mencoba menelusuri algoritma diatas dengan contoh yaitu fibo(5) maka hasilnya seperti recursion tree berikut:

images1

Perhatikan f3, f2, . …………… dikalkulasikan berulang kali dimana semakin kita masuk ke dalam pohon pemanggilan maka semakin banyak fungsi-fungsi yang dipanggil berkali-kali. Pendekatan dynamic program memang menghindari kalkulasi fungsi yang berulang kali seperti ini dengan melakukan memorization yang maksudnya menyimpan hasil kalkulasi fungsi tersebut sehingga nantinya menggunakan nilai yang disimpan ketika perhitungan yang sama dibutuhkan kembali. Dengan menyimpan hasil kalkulasi seperti ini maka jumlah total langkah perhitungan yang harus dilakukan menjadi berkurang. Maka pohon pemanggilan fungsi nantinya terpotong setengahnya sehingga perhitungan fibonacci akan menjadi sangat efisien dengan menggunakan fungsi yang baru ini. Seperti data F3, data yang sudah dikelola dan hasilnya disimpan tidak akan dilakukan kalkulasi ulang melainkan menggunakan data sebelumnya.