Pemrograman dinamis

Gambar 1. Menemukan jalur terpendek dalam grafik menggunakan substruktur optimal; garis lurus menunjukkan satu sisi; garis bergelombang menunjukkan jalur terpendek antara dua sudut yang terhubung (di antara jalur lain, tidak ditampilkan, berbagi dua sudut yang sama); garis tebal adalah jalur terpendek keseluruhan dari awal sampai tujuan.

Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah metode pengoptimalan matematika dan metode pemrograman komputer. Metode ini dikembangkan oleh Richard Bellman pada 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik kedirgantaraan hingga ekonomi.

Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang rumit dengan memecahnya menjadi sub-masalah yang lebih sederhana secara rekursif. Meskipun beberapa masalah keputusan tidak dapat dipisahkan dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali pecah secara rekursif. Begitu pula dalam ilmu komputer, jika suatu masalah dapat diselesaikan secara optimal dengan memecahnya menjadi sub-sub masalah dan kemudian secara rekursif mencari solusi optimal untuk sub masalah tersebut, maka dikatakan memiliki substruktur yang optimal.

Jika sub-masalah dapat disarangkan secara rekursif di dalam masalah yang lebih besar, sehingga metode pemrograman dinamis dapat diterapkan, maka ada hubungan antara nilai masalah yang lebih besar dengan nilai-nilai sub-masalah tersebut. Dalam literatur optimasi, hubungan ini disebut persamaan Bellman.

Pranala luar

• Sebuah Tutorial tentang Pemrograman Dinamis
• MIT course on algorithms – Termasuk video kuliah tentang DP bersama dengan catatan kuliah, lihat lecture 15.
• Lebih banyak Catatan DP
• King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." Pengantar pemrograman dinamis sebagai alat penting dalam teori ekonomi.
• Dynamic Programming: from novice to advanced sebuah artikel TopCoder.com oleh Dumitru tentang Pemrograman Dinamis
• Algebraic Dynamic Programming – kerangka kerja formal untuk pemrograman dinamis, termasuk kursus tingkat awal kepada DP, University of Bielefeld
• Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming."
• Tutorial pemrograman dinamis
• Pengantar Lembut tentang Pemrograman Dinamis dan Algoritma Viterbi
• Prolog Tabel BProlog dan XSB
• IFORS online interactive dynamic programming modulestermasuk, jalur terpendek, penjual keliling, ransel, koin palsu, menjatuhkan telur, jembatan dan obor, penggantian, produk matriks yang dirantai, dan masalah jalur kritis.