Apa itu pemrograman dinamis?

Pemrograman dinamis, ketika mengacu pada bidang ilmu komputer, menggambarkan sekelompok algoritma komputer yang sama dimaksudkan untuk memecahkan masalah kompleks dengan memecah masalah menjadi set masalah yang lebih kecil.Pertama kali dibuat oleh Richard Bellman pada 1950 -an, pemrograman dinamis bekerja dengan masalah yang tumpang tindih subproblem atau substruktur optimal.Untuk memahami bagaimana pemrograman dinamis bekerja, yang terbaik untuk memahami konsep di balik kedua istilah ini.

Subproblem yang tumpang tindih menggambarkan persamaan rumit yang, ketika dipecah menjadi set persamaan yang lebih kecil, menggunakan kembali bagian -bagian dari persamaan yang lebih kecil lebih dari sekali untuk mencapai jawaban.Misalnya, persamaan matematika yang disuruh menghitung semua hasil yang mungkin menggunakan satu set angka dapat menghitung hasil yang sama beberapa kali sambil menghitung hasil lain hanya satu kali.Pemrograman dinamis akan menceritakan masalah ini bahwa setelah menghitung hasil pertama kali ia menyimpan hasil itu dan mencolokkan jawaban ke dalam persamaan nanti alih -alih menghitungnya lagi.Saat berhadapan dengan proses dan persamaan yang panjang, ini menghemat waktu dan menciptakan solusi yang lebih cepat menggunakan langkah -langkah yang jauh lebih sedikit.

substruktur optimal membuat solusi dengan menemukan jawaban terbaik untuk semua subproblem dan kemudian membuat jawaban keseluruhan terbaik.Setelah memecah masalah yang kompleks menjadi masalah yang lebih kecil, komputer kemudian menggunakan sistem matematika untuk menentukan apa jawaban terbaik untuk setiap masalah.Ini menghitung jawaban untuk masalah asli dari jawaban yang lebih kecil.Kelemahan memang ada dengan proses ini.Meskipun memberikan solusi yang bekerja secara matematis terbaik, itu mungkin atau mungkin bukan solusi terbaik dalam kehidupan nyata, tergantung pada jenis masalah dan bagaimana hubungannya dengan dunia nyata.

Selama salah satu operasi ini, pemrograman dinamisAlgoritma mencoba menemukan jalan terpendek ke solusi.Dibutuhkan satu dari dua pendekatan untuk melakukan ini.Pendekatan top-down memecah persamaan menjadi persamaan yang lebih kecil dan menggunakan kembali jawaban untuk persamaan ini bila perlu.Pendekatan bottom-up mencoba untuk memecahkan nilai matematika terkecil setelah memecah persamaan dan kemudian bekerja menuju yang terbesar dari sana.Kedua pendekatan menghemat waktu, tetapi pemrograman dinamis hanya berfungsi ketika masalah asli dapat dipecah menjadi persamaan yang lebih kecil yang pada titik tertentu digunakan kembali untuk menyelesaikan persamaan.