Beranda > Penelitian operasional > KARAKTERISTIK PROGRAMA DINAMIS

KARAKTERISTIK PROGRAMA DINAMIS

Algoritma Program Dinamis memiliki karakteristik sebagai berikut:
1. Persoalan dapat dibagi mejadi beberapa tahap, yang pada setiap tahap hanya diambil satu keputusan yang optimal.
2. Masing-masing tahap terdiri dari sejumlah status yang berhubungan dengan tahap tersebut.
3. Hasil keputusan yang diambil pada tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap sebelumnya dan meningkat secara teratur dengan bertambahnya jumlah tahapan
5. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan tahap sebelumnya.
6. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk tahap sebelumnya.

7. Prinsip optimalitas berlaku pada persoalan tersebut. Ciri utama dari Program Dinamis adalah prinsip optimalitas yang berbunyi : jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal .
Dari karakteristik poin ke-4 di atas, kita dapat menyimpulkan bahwa algoritma Program Dinamis dapat diaplikasikan apabila peningkatkan ongkos secara linear dan diskrit sehingga optimasi parsial dapat dilakukan. Dalam menyelesaikan persoalan dengan Program Dinamis, kita dapat menggunakan 2 pendekatan berbeda yaitu :
a. Maju (forward atau up-down) : bergerak mulai dari tahap 1, terus maju ke tahap 2,3,..,n. Urutan variabel keputusan adalah x1,x2,…,xn
b. Mundur(backward atau bottom-up) : bergerak mulai dari tahap n, terus mundur ke tahap n-1, n-2,..,2,1. Urutan variabel keputusan adalah xn xn-1,x2,x1. Adapun kompleksitas waktu pada algoritma ini adalah O(| s1|*|s2|), jika panjang kedua string adalah ‘n’. Kompleksitas ruangnya juga sama jika seluruh matriks disimpan untuk merunut balik untuk mencari optimal alignment. Jika nilai edit distance dibutuhkan, hanya dua baris dari matriks yang dialokasi; matriks tersebut dapat mengalami ‘daur ulang’, dan kompleksitas ruangnya jadi O(n)

http://bird-paskiacelva.blogspot.com/2009/02/algoritma-program-dinamis.html

  1. dessy
    20 April 2011 pukul 04:37

    boleh kah saya mendapatkan algoritma nya?? t’mkash

  1. No trackbacks yet.

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: