Dynamic Programming


Pengertian 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-3 adalah dasar dynamic-programming dalam menemukan solusi untuk suatu problem, Step 4 dapat dilakukan jika nilai solusi optimal diperlukan.

berikut contoh penerapan dynamic programming

Dynamic Programming Longest Common Susequence

Jika ada dua sekuen X dan Y maka Z merupakan common subsequence dari X dan Y jika Z adalah subsekuen dari X dan Y. misalnya X = (A,B,C,B,D,A,B) dan Y=(B,D,C,A,B,A), sekuen (B,C,A) adalah common subsequence dari X dan Y, tetapi sekuen (B,C,A) bukan merupakan longest common subsequence dari X dan Y karena hanya memiliki panjang 3. Dan sekuen (B,C,B,A) adalah LCS karena common subsequence dari X dan Y dan memiliki panjang 4.

Diberikan dua sekuen X = (x1,x2,x3,…,xm) dan Y = (y1 y2, y3, …, yn), kemudian dicari maximum-length common subsequence dari X dan Y. berikut ini akan diberikan langkah-langkah dimana permasalahan LCS dapat diselesaikan secara efisien menggunakan dynamic programming.

Langkah 1 : karakterisasi longest common subsequence

Teorema optimal substruktur dari LCS
Misal, X = (x1,x2,x3,…,xm) dan Y=(y1,y2,y3,…,yn) adalah sekuen dan Z = (z1,z2,z3,…,zk) merupakan LCS dari X dan Y.
1. if xm = yn, then zk=xm=yn and Zk-1 is an LCS of Xm-1 and Yn-1.
2. if xm = yn, then zk=xm implies that Z is an LCS of Xm-1 and Y.
3. if xm = yn, then zk=xm implies that Z is an LCS of Xm and Yn-1.

Langkah 2 : recursive solution

 c[I,j] merupakan length dari LCS pada sekuen Xi dan Yj, jika I = 0 atau j=0 maka LCS memiliki length 0. b[I,j] penanda asal dari suatu nilai didapatkan. Optimal substruktur dari permasalahan LCS dalam bentuk recursive formula.

s

Dengan kaitkata , ,

3 thoughts on “Dynamic Programming

  1. baday mengatakan:

    thks tlh bantu tgas saya

  2. faqihn mengatakan:

    BLOG YANG OKE, MOHON BERKUNJUNG KE BLOG SAYA, SAYA SANGAT BUTUH MATERI DINAMIK PROGRAMMING, TQ

  3. parhan mengatakan:

    Makasih bang atas info nya. Izin copy ni ya.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: