DYNAMIC PROGRAMMING

(PEMROGRAMAN DINAMIS)

1.1 DEFINISI DYNAMIC PROGRAMMING

Suatu Perancangan algoritma, dengan solusi optimalnya diperoleh
berdasarkan rangkaian keputusan sebelumnya yang dilakukan secara simultan
disebut dengan Dynamic Programming (Pemrograman Dinamis).
Pada metode/algoritma Greedy, solusi optimalnya hanya dapat diperoleh
pada satu rangkaian keputusan, sedangkan pada Dynamic Programming solusi
optimalnya dapat diperoleh dari banyak rangkaian keputusan yang mungkin
menghasilkan.
Satu cara untuk memecahkan masalah-masalah, yang mana ini tidak
mungkin untuk membuat sebuah rangkaian dari langkah-langkah keputusan yang
dapat dilakukan mengacu (mengarah) pada rangkaian keputusan optimal, adalah
untuk mencoba semua kemungkinan rangkaian-rangkaian keputusan. Kita dapat
memberikan nomor (angka) semua rangkaian keputusan dan kemudian memilih
yang terbaik. Dynamic Programming seringkali secara spontan mengurangi
jumlah pembilangan dengan menghindari pembilangan dari beberapa rangkaian
keputusan yang tidak memungkinkan menjadi optimal. Di dalam Dynamic
Programming hubungan-hubungan keputusan optimal didapat dengan membuat
prinsip optimalitas secara explisit. Pernyataan prinsip itu merupaka rangkaian
keputusan optimal yang memiliki sesuatu yang dinyatakan dengan initial dan
keputusan, dalam mengambil keputusan harus menyusun suatu keputusan optimal
dengan memperhatikan hasil pernyataan dari keputusan pertama. Di dalam
dynamic programming, banyak rangkaian keputusan yang mungkin menghasilkan.
Tetapi, rangkaian yang berisi sub-sub rangkaian optimal tidak dapat optimal jika
prinsip berpengaruh pada optimasi dan pasti tidak akan menghasilkan.
Dalam menyelesaikan persoalan, algoritma Dynamic Programming
menggunakan teknik rekursif. Dalam merumuskan hubungan-hubungan kembali
Dynamic Programming yang harus dipecahkan, seseorang dapat menggunakan 1
dari 2 pendekatan yang berbeda yaitu forward atau backward. Anggap x1, x2, …,
xn, sebagai variabel-variabel dimana suatu hubungan dari keputusan-keputusan
harus dibuat. Dalam pendekatan forward, untuk keputusan x i dibuat dengan
batasan hubungan keputusan optimal untuk xi+1, …, xn. Dalam pendekatan
backward, untuk keputusan xi dibuat dengan batasan hubungan keputusan optimal
untuk xn, …, xi-1.
Dynamic Programming merupakan suatu teknik analisa kuantitatif untuk
membuat tahapan keputusan yang saling berhubungan. Teknik ini menghasilkan
prosedur yang sistematis untuk mencari keputusan dengan kombinasi yang
optimal.
Program Dinamis (Dynamic Programming) adalah metode pemecahan
masalah dengan cara menguraikan solusi menjadi sekumpulan (stage), sedemikian
sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang
saling berkaitan.
Dynamic Programming adalah prosedur matematis yang terutama
dirancang untuk memperbaiki efisiensi perhitungan masalah pemrograman
matematis tertentu dengan menguraikannya menjadi bagian masalah yang lebih
kecil. Dynamic Programming pada umumnya menjawab masalah dalam tahap-
tahap dengan setiap tahap meliputi tepat satu variable optimasi. Perhitungan
ditahap yang berbeda-beda dihubungkan melalui perhitungan rekursi dengan cara
yang menghasilkan pemecahan optimal bagi seluruh masalah.
Istilah Program Dinamis muncul karena kecenderungan penggunaan
metode ini dalam menganalisa dan mendokumentasikan hasil perhitungan pada
setiap tahapnya melibatkan pengambilan keputusan yang berkaitan dengan waktu.
Tetapi, situasi lain dimana waktu bukan merupakan factor juga dipecahakan oleh
Dynamic Programming dimana prosedur itu pada umumnya menentukan
pemecahan dalam tahap-tahap.
Teori utama dalam Dynamic Programming adalah prinsip optimalitas.
Prinsip itu pada dasarnya menentukan bagaimana suatu masalah yang diuraikan
dengan benar dapat dijawab dalam tahap-tahap.

Pemecahan masalah dengan menggunakan Dynamic Programming

mempunyai empat tahapan, yaitu :
a. Memecah permasalahan asli menjadi bagian permasalahan yang juga
disebut sebagai tahapan dengan aturan keputusan ditiap-tiap tahapan.
b. Memecahkan tahapan terakhir dari permasalahan dengan semua kondisi
dan keadaan yang memungkinkan.
c. Bekerja mundur dari tahapan terakhir dan memecahkan tiap tahap. Hal ini
dikerjakan dengan mencari keputusan optimal dari tahap tersebut sampai
dengan tahap terakhir.
d. Solusi optimal dari permasalahan didapatkan jika semua tahap sudah
terpecahkan.

1.2 Model Dynamic Programming

Dalam Dynamic Programming perhitungan dilakukan dalam tahap-tahap

dengan memerincikan masalah menjadi beberapa bagian masalah. Setiap bagian
masalah kemudian dipertimbangkan secara terpisah dengan tujuan untuk
mengurangi jumlah dan kerumitan perhitungan. Tetapi karena semua maslah
salaing bergantung, harus dipikirkan sebuah prosedur untuk menghubungkan
perhitungan dengan cara yang menjamin bahwa pemecahan yang layak untuk tiap-
tiap tahap juga layak untuk keseluruhan masalah.

Sebuah tahap dalam Dynamic Programming didefinisikan sebagai bagian

dari masalah yang memiliki beberapa alternative yang saling menggantikan yang
darinya alternatif terbaik akan dipilih. Gagasan dasar Dynamic Programming
adalah secara praktis menghilangkan pengaruh saling ketergantungan antar tahap-
tahap dengan menghubungkan definisi suatu keadaan dengan setiap tahap. Suatu
keadaan biasanya didefinisikan untuk menunjukkan suatu batasan yang mengikat
semua tahap secara bersama-sama.

Semua keputusan dimasa yang akan datang dipilih secara optimal tanpa
melihat keputusan yang diambil sebelumnya. Sifat khusus ini merupakan prinsip
optimalitas yang merupakan dasar bagi keabsahan perhitungan dynamic
programming.
Dynamic Programming mirip seperti metode divide-and-conquer yang
menyelesaikan suatu problem dengan mengkombinasikan solusi menjadi
subproblem. Divide-and-conquer membagi problem menjadi subproblem yang
independen. kemudian menyelesaikan subproblem secara rekursif dan
mengkombinasikan solusi tersebut untuk menyelesaikan problem utama.
Sedangkan Dynamic Programming cocok digunakan ketika subproblem tidak
indepen-den, jadi ketika subproblem terbagi menjadi subsubproblem.
Dynamic Programming biasanya digunakan untuk masalah optimisasi. Dimana
suatu permasalahan memiliki banyak solusi. Setiap solusi memiliki nilai masing-
masing. Dan ingin ditemukan solusi dengan nilai yang optimum (maksimal atau
mininal).
Dynamic Programming dapat dibagi menjadi empat tahap yang berurutan
sebagai berikut :
1. Karakterisasi struktur pada solusi optimasi
2. Mendefinisikan nilai solusi optimal secara rekursif
3. Menghitung nilai solusi optimal pada model bottom-up
4. Menyusun solusi optimal dari informasi hasil perhitungan
Langkah 1 sampai langkah 3 adalah dasar dynamic-programming dalam
menemukan solusi untuk suatu problem, langkah ke-4 dapat dilakukan jika nilai
solusinya optimal diperlukan.
Dynamic Programming sebagai suatu pendekatan matematik memiliki
beberapa prinsip dasar yang terkait erat satu sama lain. Prinsip-prinsip dasar
tersebut, yaitu :
Prinsip pertama dalam model Dynamic Programming adalah bahwa
masalah dapat dibagi menjadi bagian-bagian masalah yang lebih kecil. Masalah
yang lebih kecil atau sub masalah ini tersebut sebagai tahap keputusan (stage).
Setiap masalah uang akan diselesaikan, terlebih dahulu dibagi-bagi menjadi
beberapa masalah kecil dengan maksud memudahkan evaluasi masalah untuk
mendapatkan keputusan optimal dari tiap-tiap tahap yang pada akhirnya akan
menghasilkan satu keputusan yang optimal. Oleh karena itu model Dynamic
Programming disebut juga model multi stage programming (model multi tahap).

Proses urutan pembagian masalah dalam model Dynamic Programming

ditunjukan pada gambar berikut :
 Gambar 1.1 Hubungan Status Input Dengan Tahap Keputusan

Status Status Status

Input Input Input
Tahap 3 Tahap 2 Tahap 1

Tahap Tahap Tahap

Keputusa Keputusan
n3 2 Keputusan 1

Status
Status output output
Tahap3 Tahap 2
Prinsip kedua dalam model Dynamic Programming adalah tentang status
(state). Pengertian status (state) dalam Dynamic Programming adalah arus
informasi dari suatu tahap ke tahap berikutnya. Arus informasi yang masuk ke
suatu tahap disebut status input, sedangkan arus informasi yang keluar dari suatu
tahap diseebut stats output. Status input penting, karena keputusan pada tahap
berikutnya tergantung dari status input sebelumnya. Jadi, status input untuk tahap
keputusan n-1 merupakan status output dari tahap keputusan sebelumnya, yaitu
tahap keputusan n. Sedangkan status output dari tahao keputusan n akan menjadi
status input untuk tahap kepututsan berikutnya, yaitu tahap keputusan n-1.
Prinsip ketiga dalam model Dynamic Programming adalah tentang
variabel keputusan. Variabel keputusan dalam Dynamic Programming
dainyatakan dalam berbagai bentuk keputusan alternatif yang dapat dipilih pada
saat pengambilan keputusan pada tahap tertentu. Berbagai alternatif keputusan
yang dapat diambil dalam setiap tahap keputusan dapat dibatasi dengan sejumlah
persyaratan yang dikenalkan dalam struktur masalah.
Prinsip keempat dalam model Dynamic Programming adalah tentang
fungsi transformasi. Fungsi transformasi memberikan penjelasan tentang
bagaimana hubungan antara tahap keputusan yang satu dengan tahap keputusan
yang lain dalam Dynamic Programming diformulasikan. Selain itu fingsi
transformasi juga menyatakan tentang hubungan fungsional nilai status pada
setiaptahap keputusan. Hubngan status dalam tahap keputusan yang berurutan
bersifat berulang, artinya jika terdapat tahap keputusan n dalam hubungannya
dengan thap keputusan n-1 maka perhitungan untuk nilai status n-1 menggunakan
nilai status n dari keputusan pada tahap n.
Ada 2 (dua) Pendekatan pada Program dinamis, yaitu :

1. Program Dinamis Maju ( forward atau up-down)

2. Program Dinamis Mundur (Bacward atau button-up)

Misalkan x1,x2, …., xn menyaatakan peubah (variable) keputusan yang

dibuat masing-masing untuk tahap 1,2,…, n. Maka ,

1. Program dinamis maju. Program dinamis bergerak mulai dari tahap 1,

terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. runtunan peubah
keputusan adalah x1, x2, .., xn .
2. Program dinamis mundur. Program dinamis bergerak mulai dari tahap n ,
terus mundur ke tahap n-1, n-2, dan seterusnya sampai atahap 1. Runtunan
peubah keputusan adalah xn, xn-1, …, x1.
 Dengan demikian, Prinsip optimalitas pada program dinamis maju adalah
ongkos pada tahap k +1 = (ongkos yang dihasilkan pada tahap k) + (ongkos dari
tahap k ke tahap k + 1), k = 1, 2, …, n – 1
Sedangkan prinsip optimalitas pada program dinamis mundur adalah
ongkos pada tahap k = (ongkos yang dihasilkan pada tahap k + 1) + ( ongkos dari
tahap k + 1 ke tahap k), k = n, n – 1,…, 1.
Pada prinsipnya Program Dinamis berdasarkan pada Graf multitahap
(multistage graph). Tiap simpul didalam garaf tersebut menyatakan status,
sedanagkan V1,V2,… menyatakan tahap.

Gambar 1.2 Garph multitahap

Pada Persoalan Graph Multitaphap dikaitkan dengan program dinamis,

dikenal :
1. Tahap (k) adalah proses memilih simpul tujuan berikutnya (Gambar 1, ada
5 tahap).
2. Status (s) yang berhubungan dengan masing-masing tahap adalah simpul-
simpul di dalam garaf.

Relasi rekurens berikut menyatakan lintasan terpendek dari status s ke x4

pada tahap k :
 Tujuan Program Dinamis Maju mendapatkan dengan cara mencari

terlebih dahulu.

1.3 Karakteristik dan Konsep Dasar Dynamic Programming

1.3.1 Karakteristik Dynamic Programming:

 Permasalahan dibagia menjadi stage, dengan keputusan diperlukan pada

tiap stage.

 Tiap stage punya nomor stage berhubungan dengan awal dari stage. Hasil
dari setiap stage ditransformasikan pada stage yang lainnya.

 Prosedur penyelesaiannya dirancang untuk mendapatkan hasil yang

optimal.

 Hasil optimal dari suatu stage tidak berhubungan dengan stage

sebelumnya.
 Prosedur penyelesaiannya diawali dari stage terakhir.
 Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan
dengan tahap tersebut. Secara umum, status merupakan bermacam
kemungkinan masukan yang ada pada tahap tersebut. Jumlahnya bisa
berhingga atau tak berhingga.
 Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan
dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
 Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan
bertambahnya jumlah tahapan.
 Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah
berjalan dan ongkos pada tahap tersebut.
 Keputusan terbaik pada suatu tahap bersifat independen terhadap
keputusan yang dilakukan pada tahap sebelumnya.
 Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik
untuk setiap status pada tahap k memberikan keputusan terbaik untuk
setiap status pada tahap k + 1.
 Prinsip optimalitas berlaku pada persoalan tersebut.
1.3.2 Konsep dasar Dynamic Programming
 Dekomposisi
Persoalan Dynamic Programming dapat dipecah-pecah menjadi
subpersoalan atau tahapan ayang lebih kecil dan berurutan. Setiap tahap
disebut juga sebagai titik keputusan. Setiap keputusan yang dibuat pada
suatu tahap akan mempengaruhi keputusan-keputusan pada atahap
berikutnya.
 Status
Status adalah kondisi awal dan kondisi akhir pada setiap tahap, dimana
pada atahap tersebut keputusan dibuat. Status akhir pada sebuah tahap
tergantung keadaan status awal dan keputusan ayang dibuat pada tahap
yang bersangkutan. Status akhir pada suatu tahap merupakan input bagi
tahap berikutnya.
 Variable Keputusan dan Hasil
Keputusan yang dibuat pada setiap atahap merupakan keputusan yang
berorientasi kepada return yang diakibatkannya, tingkat maksimal atau
minimal.
 Fungsi Transisi
Fungsi transisi menjelaskan secara pasti bagaimana tahap-tahap saling
berhubungan. Fungsi ini berbentuk fungsi hubungan antar status pada
setiap tahap yang berurutan.
 Gambar 1.3 Fungsi Transisi

 Optimasi Tahap
Optimasi tahap dalam Dynamic
Programming adalah menentukan
keputusan optimal pada setiap tahap dari bebagai kemungkinan nilai status
inputnya.
 Fungsi Rekursif
Fungsi rekursif biasanya digunakan pada berbagai program computer,
dimana nilai sebuah variable pada fungsi itu merupakan nilai kumulatif
dari nilai variable tersebut pada tahap sebelumnya.
Dynamic Programming (DP) merupakan salah satu teknik perancangan
algoritma yang dikembangkan untuk menyelesaikan permasalahan yang sangat
kompleks dengan memecah permasalahan tersebut menjadi banyak sub-
permasalahan. Perbedaan utama DP dengan Divide and Conquer (D&C) adalah
pada DP kita menggunakan kembali Perbedaan utama dari DP dengan D&C
adalah DP melakukan penyimpanan hasil penyelesaian sub-masalah sehingga kita
tidak perlu menyelesaikan sub-masalah yang sama berulang kali.

Contoh :
Perbedaan Dynamic Programming dan Divide and Conquer (D&C) dalam
perhitungan bilangan fibonacci. Algoritma untuk menyelesaikan perhitungan
fibonacci secara naif adalah seperti berikut:
 Gambar 1.4 Algoritma untuk menyelesaikan perhitungan fibonacci
Algoritma fibonacci sederhana seperti di atas dapat dikatakan sebagai
algoritma D&C, karena kita membagikan perhitungan fibonacci ke dua fungsi
fibonacci, sampai didapatkan nilai hasil terkecilnya. Pemanggilan fungsi fibonacci
di atas dapat digambarkan seperti berikut:

Gambar 1.5 Pemanggilan Fungsi Fibonacci

Perhatikan bagaimana f(n−2) dan f(n−3) dikalkulasikan sebanyak dua kali,
dan semakin kita masuk ke dalam pohon pemanggilan, kita akan melihat semakin
banyak fungsi-fungsi yang dipanggil berkali-kali. Pendekatan DP menghindari
kalkulasi fungsi yang berulang kali seperti ini dengan melakukan memoization,
yaitu menyimpan hasil kalkulasi fungsi tersebut dan menggunakan nilai yang
disimpan ketika perhitungan yang sama dibutuhkan kembali. Dengan menyimpan
hasil kalkulasi seperti ini, tentunya jumlah total langkah perhitungan yang harus
dilakukan menjadi berkurang.
Misalnya, kita dapat menyimpan hasil kalkulasi dari fungsi fibonacci
tersebut pada sebuah dictionary, seperti berikut:
 Gambar 1.6 Hasil Kalkulasi Dari Fungsi Fibonacci
Dengan menyimpan hasil kalkulasi dari fungsi yang telah ada, maka proses
pemanggilan fungsi akan menjadi seperti berikut:

Gambar 1.7 Pemanggilan Fungsi Fibonacci Dynamic Programming

Seperti yang dapat dilihat, pohon pemanggilan fungsi terpotong
setengahnya! Tentunya perhitungan fibonacci akan menjadi sangat efisien dengan
menggunakan fungsi yang baru ini.
Pendekatan lain dalam menghitung fibonacci lagi, yang masih adalah DP,
yaitu dengan menghitung nilai fibonacci dari bawah pohon (pada kode
sebelumnya kita melakukan perhitungan dari atas pohon):

Gambar 1.8 Pendekatan Lain Dalam Menghitung fibonacci

Untuk ketiga fungsi tersebut, ketika ketiga fungsi tersebut dijalankan
untuk n yang sama, akan tampak perbedaan waktu eksekusinya.

1.4 Kelebihan dan kekurangan System Dynamic Programming

1.4.1 Kelebihan Dynamic Programming
Terdapat beberapa kelebihan pada Dynamic Programming, diantaranya :
a. Mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan
menjadi sub-submasalah yang lebih kecil yang terkait satu sama lain
dengan tetap memperhatikan kondisi dan batasan permasalahan tersebut.

b. Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah

yang lebih kecil membuat sumber permasalahan dalam rangkaian proses
masalah tersebut menjadi lebih jelas untuk diketahui.

c. Pendekatan Dynamic Programming dapat diaplikasikan untuk berbagai

macam masalah pemrograman matematik, karena Dynamic Programming
cenderung lebih fleksibel daripada teknik optimasi lain.

d. Prosedur perhitungan Dynamic Programming juga memperkenankan

bentuk analisissensitivitas terdapat pada setiap variabel status (state)
maupun pada variabel yang ada di masing-masing tahap keputusan (stage).

1.4.2 Kelemahan Dynamic Programming

a. Disamping memiliki kelebihan, Dynamic Programming juga memiliki
beberapa kekurangan, diantaranya :

b. Penggunaan Dynamic Programming jika tidak dilakukan secara tepat, akan

mengakibatkan ketidakefisienan biaya maupun waktu. Karena dalam
menggunakan Dynamic Programming diperlukan keahlian, pengetahuan,
dan seni untuk merumuskansuatu masalah yang kompleks, terutama yang
berkaitan dengan penetapan fungsi transformasi dari permasalahan
tersebut.

c. Penggunaan Dynamic Programming jjika tidak dilakukan secara tepat,

akan mengakibatkan ketidakefisienan biata maupun waktu. Karena dalam
menggunakan Dynamic Programming diperlukan keahlian, pengetahuan,
dan seni untuk merumuskan suatu masalah yang kompleks, terutama yang
berkaitan dengan penetapan fungsi transformasi dari permasalahan
tersebut.
d. Dynamic Programmingtidak memiliki suatu bentuk formulasi matematik
yang baku untuk digunakan secara konsekuen, sehingga perhitungan untuk
menghasilkan keputusan optimal yang dilakukan terbatas pada kondisi
tertentu.

e. Hambatan terbesar pada Dynamic Programming adalah masalah

dimensionalitas, yaitu masalah dimana peningkatan variabel keadaan yang
digunakan dalam perhitungan pemrograman dinamis akan menambah
beban memory komputer serta menambah lama waktu perhiutngan.