Dynamic Programming

Apa yang dimaksud dengan dynaming programming?

Program dinamis adalah suatatu teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Dalam hal ini program dinamis menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal. Tujuan utama model ini ialah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu

Tidak seperti pemrograman linier, tidak ada bentuk matematis standar untuk perumusan pemrograman dinamis. Akan tetapi, pemrograman dinamis adalah pendekatan umum untuk pemecahan masalah dan persamaan tertentu yang digunakan di dalamnya harus dibentuk sesuai dengan situasi masalah yang dihadapi.

Istilah yang biasa digunakan antara lain:

1.      Stage(tahap)  adalah bagian persoalan yang mengandung decision variable.

2.      Alternatif, pada setiap stage terdapat decision variable dan fungsi tujuan yang menentukan besarnya nilai setiap alternative.

3.      State, state menunjukkan kaitan satu stage dengan stage lainnya, sedemikian serupa sehingga setiap stage dapat dioptimisasikan secara terpisah sehingga hasil optimasi layak untuk seluruh psrsoalan.

.Program dinamis (dynamic programming) yang ditemukan oleh Richard Bell man pada tahun 1953 merupakan suatu metode penyelesaian masalah di mana solusi persoalan dapat dipandang sebagai serangkaian keputusan yang salinng berkaitan. Program dinamis merupakan salah satu metode yang yang biasanya digunakan untuk menyederhanakan persoalan-persoalan rekursif.

      Program dinamis fokus pada bagian permasalahan yang tumpang-tindih (overlapping subproblems). Rangkaian keputusan dibuat dennngan prinsip optimalitas (optimal substructure),dimana solusi optimal dari bagian solusi permasalahan  bisa digunakan untuk menemukan solusi optimal untuk masalah secara keseluruhan.

      Penerapan program dinamis ini sangat luas. Di antaranya, yang sederhana, adalah untung menghitung angka koefisien binominal. Juga terdapat sejumlah algoritma lain yang didasarkan pada program dinamis, seperti algoritma Cocke-Younger-Kasami (CYK) untuk menentukan  apakah string dapat diterima suatu context-free grammar, algoritma Viterbi untuk model hidden Markov, algoritma Earley untuk chart parser, algoritma Needleman-Wunsch yang dipakai dalam bionformatik, algoritma Floyd’s All-Pairs untuk mencari lintasan terpendek, algoritma Selinger untuk optimal query suatu basis data, algoritma De Boor untuk evaluasi kurva B-spline, dan lain-lain.