Sejarah Dynamic Programming

Richard Bellman

   Pemrograman dinamis istilah awalnya digunakan dalam 1940-an oleh Richard Bellman untuk menggambarkan proses pemecahan masalah dimana salah satu kebutuhan untuk menemukan satu keputusan terbaik demi satu. Dengan 1953, ia disempurnakan ini untuk makna modern, mengacu khusus untuk bersarang masalah keputusan kecil dalam keputusan yang lebih besar, dan lapangan itu kemudian diakui oleh IEEE sebagai topik analisis sistem dan rekayasa. Kontribusi Bellman adalah diingat dalam nama persamaan Bellman, hasil pusat pemrograman dinamis yang menyatakan kembali masalah optimasi dalam bentuk rekursif. Dinamika Kata dipilih oleh Bellman untuk menangkap aspek waktu bervariasi dari masalah, dan juga karena terdengar mengesankan Pemrograman kata mengacu pada penggunaan metode untuk menemukan program yang optimal, dalam arti militer. jadwal untuk pelatihan atau logistik. Penggunaan ini adalah sama seperti yang dalam pemrograman linear dan pemrograman frasa matematika, sebuah sinonim untuk optimasi matematika.

 Apa itu Dynamic Programming ? Dynamic Programming (biasa disingkat DP) adalah suatu teknik algoritma untuk memecahkan masalah dimana solusi optimal dari masalah tersebut dapat dipandang sebagai suatu deret keputusan. Persoalan partisi merupakan persoalan yang sering diterapkan dalam kehidupan sehari-hari seperti misalnya pada persoalan pembagian pekerjaan. Persoalan partisi sendiri memiliki banyak model dan karateristik. Persoalan yang dibahas dalam makalah ini adalah persoalan membagi pekerjaan untuk dikerjakan oleh N pekerja secara efisien sedemikian sehingga setiap pekerja mendapat pekerjaan yang relatif sama(perbedaan bobot yang diterima pekerja dibuat seminimum mungkin). Penyelesaian persoalan ini salah satunya adalah dengan menggunakan algoritma program dinamis (dynamic programming). Algoritma program dinamis adalah penyelesaian persoalan dengan cara menguraikan solusi menjadi sekumpulan langkah dan memandang solusi dari persoalan tersebut sebagai serangkaian keputusan yang saling berkaitan. 

 Suatu pekerjaan yang berskala besar seringkali  harus dikerjakan oleh banyak pekerja. Pekerjaan berskala besar itu biasanya dapat dibagi-bagi menjadi beberapa bagian pekerjaan yang masing-masing  bagian memiliki bobot tertentu. Pembagian bobot pekerjaan selayaknya relatif sama (perbedaaan bobot yang diterima setiap pekerja dibuat seminimum mungkin) untuk setiap pekerja.

Cara Pembagian pekerjaan  dengan memperhitungkan bobot tersebut dapat mengefisiensikan waktu pengerjaan dan juga mendapatkan hasil yang optimal.

  
Sebagai contoh, Misalnya :

Kita diberikan sebuah pekerjaan untuk melakukan pencarian informasi yang ada pada beberapa buku yang memiliki jumlah halaman berbeda kepada tiga pekerja. Buku-buku ini dibagi ke setiap pekerja dengan jumlah halaman buku relatif sama (perbedaan halaman yang diterima setiap pekerja dibuat seminimum mungkin). Untuk membagi jumlah halaman tersebut dengan perbedaan halaman seminimal mungkin  diperlukan sebuah metode pembagian partisi. Proses pembagian partisi ini dapat menerapkan berbagai algoritma salah satunya adalah menggunakan program dinamis.   

 Dalam matematika dan ilmu komputer, pemrograman dinamis adalah metode untuk memecahkan masalah yang kompleks dengan melanggar mereka ke dalam  subproblems yang lebih sederhana. Hal ini berlaku untuk masalah menunjukkan sifat overlapping subproblem yang hanya sedikit lebih kecil dan optimal substruktur (dijelaskan di bawah). Ketika diterapkan, metode ini membutuhkan waktu jauh lebih sedikit daripada metode naif.

 Ide kunci di balik pemrograman dinamis adalah cukup sederhana. Secara umum, untuk memecahkan persoalan yang diberikan, kita perlu untuk memecahkan berbagai masalah (submasalah), kemudian menggabungkan solusi dari submasalah untuk mencapai solusi secara keseluruhan. Seringkali, banyak dari submasalah ini benar-benar sama. Pendekatan pemrograman dinamis berusaha untuk memecahkan setiap subproblem hanya sekali, sehingga mengurangi jumlah perhitungan. Hal ini sangat berguna ketika jumlah subproblems mengulangi secara eksponensial besar.

Referensi :

- Dari berbagai sumber