[algoritma|tek.inf|r408|pert.8]

Salah satu materi algoritma standar adalah pemrograman dinamis (Dynamic Programming). Walaupun ada kata “programming”-nya ternyata tidak ada hubungannya dengan kode/script. Ternyata istilah pemrogramannya karena teknik yang biasanya digunakan untuk optimalisasi ini memanggil suatu fungsi diri sendiri (rekursif) sebelum menentukan hasil-hasil yang optimal. Optimal di sini bisa maksimal atau minimal.

Pemotongan Batang (Rod Cutting)

Kasus ini contoh proses pemotongan bilah batang panjang agar dihasilkan margin keuntungan yang optimal. Misalnya batang baja sepanjang 10 inchi yang akan dipotong dengan potongan kelipatan 1 inchi.

Kombinasi dari ukuran potongan ternyata sangat menentukan keuntungan berdasarkan harga per potongnya. Misal, untuk baja sepanjang 4 inchi memiliki keuntungan dengan komposisi dua buah batang berukuran 2 inchi.

Selain dua buah potongan berukuran 2 inchi, panjang potongan menghasilkan harga 4, 7, dan 9. Sementara dua buah potongan 2 inchi menghasilkan harga 10 (tentu saja ini kasus bagi penjual, kalau pembeli tentu lebih menguntungkan beli potongan-potongan kecil satu inchi).

Memoization

Istilah ini saya fikir salah tulis, harusnya memorization, ternyata tidak. Istilah ini berasal dari kata “memo”, yaitu secarik surat/infor singkat. Misal untuk tiap-tiap panjang bilah akan dihasilkan nilai optimal sebagai berikut:

Perhatingan untuk baja sepanjang 1 sampai 3 inchi, optimalnya adalah tanpa dipotong, masing-masing berharga $1, $5, dan $8. Baja 2 in ada dua kemungkinan yaitu 1+1 atau 2 in tanpa dipotong. Karena 1in+1in menghasilkan hanya $2 maka yang dipilih 2 in tanpa dipotong, yaitu $5. Untuk baja berukuran 4 in ada beberapa kemungkinan seperti gambar batangan di atas dan dihitung semua kemungkinannya hingga diperoleh maksimal adalah dua potongan @2in. Pseucode-nya sebagai berikut:

Keterangan: baris ke-4 sampai 6 menghitung komposisi potongan baja. Misal untuk i=1, maka akan dicari maksimal dari 1 dan (n-1)-nya. Jika batang 4 in, maka 1 dan 3, berikutnya 2 dan 2 (dari n-2) dan seterusnya. Untuk kasus contoh di atas diperoleh nilai maks 10 (ketika i=2 dan satu potongan lainnya 2 in juga).

Karena potongan 2in sudah dihitung dari sebelumnya (batang ukuran 2in) maka ketika menghitung 4in tidak perlu menghitung kembali yang 2in hanya menggunakan riwayat yang lalu, alias dari “memo” sebelumnya. Di sinilah muncul istilah memoization, atau dalam bahasa Indonesianya mungkin memoisasi.

Top Down Memoization

Dengan rekursif, beberapa perhitungan dihitung berulang kali sehingga tidak efisien (naif). Oleh karena itulah pemrograman dinamis diterapkan untuk menggantikan proses rekursif berulang tersebut. Jadi sekali telah dihitung, maka jika akan menghitung proses yang sama hanya me-ngintip (lookup) hasil perhitungan yang lampau.

Untuk dengan memoization, ditambahkan arrah yang berisi nilai yang sudah dihitung dengan suatu routine yang disebut helper “Memouzed-Cut-Rod-Aux” (simbol minus tak hingga artinya unknown dan perlu dihitung):

Baris 1-3 mengecek apakah nilai sudah ada di array hasil perhitungan atau tidak. Jika tidak ada (else) masuk ke q yang unkhown (minus tak hingga) dengan baris 7 yang berisi maksimal komposisi-komposisi yang maksimal. Hanya saja di sini rekursif yang bekerja dengan mengecek hasil hitungan sebelumnya jika sudah ada di array hasil, langsung mengkopi saja tidak perlu menghitung lagi nilai r-nya (lihat r1 sampai r10 di contoh paling atas postingan ini untuk batang sepanjang 10 in).

Buttom Up Memoization

Teknik buttom up lebih sederhana karena tidak membutuhkan mekanisme rekursif, hanya dengan menghitung maksimal potongan-potongan dari terkecil hingga terbesarnya.

Keterangan: Seperti biasa array hasil dipersiapkan. Variabel j merupakan hasil optimal komposisi potongan yang bergerak dari kombinasi i dengan pasangannya. Misal ketika j=4 maka i bergerak dari i=1 dan r(3) mana yang lebih maksimal dibanding komposisi lainnya misal i=2 dan r(2), dan seterusnya. Baik buttom up ataupun top down memiliki running time yang kuadratik. Sekian, semoga bermanfaat.

Referensi:

Cormen, dkk. “intro to algorithms”, MIT Press: 2009.