Dynamic Programming Contoh Kasus dan Penjelasan

  • by

Dynamic Programming

Pemrograman dinamis (dynamic programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian rupa sehingga solusi dari permasalahan ini dapat dipandang dari serangkaian keputusan-keputusan kecil yang saling berkaitan satu dengan yang lain. Penyelesaian persoalan dengan pemrograman dinamis ini akan menghasilkan sejumlah berhingga pilihan yang mungkin dipilih, lalu solusi pada setiap tahap-tahap yang dibangun dari solusi pada tahap sebelumnya, dan dengan metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

Dynamic programming memiliki dua macam pendekatan, yaitu gerak maju (forward) dan gerak mundur(backward).
Contoh pada kasus multi stage graph berikut dapat diselesaikan dengan dynamic programming melalui dua pendekatan.
Pendekatan dengan Dynamic programming :
a.       Gerak Maju (forward)
Stage I:          fdist(B) = 1,    fpath(B) = {(A,B)}
                      fdist(C) = 2,    fpath(C) = {(A,C)}
                      fdist(D) = 3,    fpath(D) = {(A,D)}
Stage II :        fdist(E) = 4,    fpath(E) = {(D,E)}
                      fdist(F) = 4,     fpath(F) = {(B,F), (C,F)}
Stage III :      fdist(G) = 6,    fpath(G) = {(E,G)}
Path(AàG) = {(A,D), (D,E), (E,G)}
a.       Gerak Mundur  (Backward)
Stage I :         bdist(E) = 2,    bpath(E) = {(E,G)}
                      bdist(F) = 4,    bpath(F) = {(F,G)}
Stage II :        bdist(B) = 7,    bpath(B) = {(B,E), (B,F)}
                      bdist(C) = 5,    bpath(C) = {(C,E)}
                      bdist(D) = 3,   bpath(C) = {(D,E)}
stage III :       bdist(A) = 6,   Bpath(A) = {(A,D)}
Path(AàG) = {(A,D), (D,E), (E,G)}
Kasus multistage graph tersebut juga dapat dapat diselesaikan dengan algoritma Greedy     melalui gerak maju atau gerak mundur, yakni sebagai berikut;
·         Gerak Maju
·         Gerak Mundur

Leave a Reply

Your email address will not be published. Required fields are marked *