Pemrograman dinamis, prinsip-prinsip dasar

Untuk memilih solusi optimal saat melakukan tugas-tugas pemrograman kadang-kadang diperlukan untuk memilah jumlah besar kombinasi data yang memuat memori dari komputer pribadi. metode tersebut meliputi, misalnya, metode pemrograman "memecah dan menguasai". Dalam hal ini algoritma memberikan masalah pemisahan menjadi sub-tugas yang lebih kecil yang terpisah. Metode ini hanya berlaku dalam kasus-kasus di mana subtugas kecil yang saling independen. Untuk menghindari melakukan pekerjaan yang tidak perlu jika saling bergantung sub-tugas, menggunakan metode pemrograman dinamis yang diusulkan Amerika R.Bellmanom tahun 50-an.

metode

pemrograman dinamis adalah untuk menentukan solusi optimal masalah n-dimensi, berbagi n tahap yang terpisah nya. Masing-masing adalah sub-tugas sehubungan dengan satu variabel.

Keuntungan utama dari pendekatan ini dapat dianggap bahwa pengembang yang terlibat dalam masalah optimasi satu dimensi subtugas bukan masalah n-dimensi, dan tujuan utama kami akan "bottom-up".

Dianjurkan untuk menerapkan pemrograman dinamis dalam kasus-kasus di mana sub-tugas saling terkait, yaitu berbagi modul umum. algoritma memberikan keputusan dari masing-masing subtasks sekali, dan tanggapan penghematan dilakukan di meja khusus. Hal ini memungkinkan tidak untuk menghitung jawaban ketika mereka bertemu lagi dengan sub-tugas yang sama.

tugas pemrograman dinamis memecahkan masalah optimasi. Penulis metode ini dirumuskan oleh R. Bellman optimalitas prinsip: apa pun adalah keadaan awal dari setiap langkah-langkah dan solusi didefinisikan dalam langkah ini, semua berikut untuk memilih yang optimal dalam kaitannya dengan negara, yang menerima sistem pada akhir langkah.

Metode ini meningkatkan kinerja tugas-tugas diselesaikan dengan cara varian, atau rekursi.

algoritma tugas Building

algoritma pemrograman dinamis melibatkan pembangunan tugas-tugas seperti bahwa tugas sehingga dibagi menjadi dua atau lebih sub-tugas untuk solusinya terdiri dari solusi optimal untuk semua sub-tugas, itu termasuk. Selanjutnya, perlu untuk menulis sebuah relasi rekurensi, dan menghitung nilai parameter optimal untuk tugas secara keseluruhan.

Kadang-kadang, pada langkah ke-3 adalah untuk menghafal beberapa informasi latar belakang tambahan tentang kemajuan tugas masing-masing. Ini disebut stroke kembali.

metode aplikasi

pemrograman dinamis diterapkan ketika ada dua fitur karakteristik:

• optimal untuk subtasks;
• Kehadiran dalam masalah tumpang tindih submasalah.

Memecahkan masalah optimasi dengan pemrograman dinamis, Anda harus terlebih dahulu menggambarkan struktur dari solusi. Tugas harus optimal jika solusi terdiri dari keputusan terbaik dari subtasks nya. Dalam hal ini, disarankan untuk menggunakan pemrograman dinamis.

Sifat kedua dari masalah, yang penting dalam metode ini, - sejumlah kecil sub-tugas. solusi rekursif dari masalah menggunakan tumpang tindih sub-masalah yang sama, jumlah yang tergantung pada ukuran informasi awal. Jawabannya disimpan dalam sebuah tabel khusus, program ini menghemat waktu dengan menggunakan data ini.

Terutama efektif adalah penggunaan pemrograman dinamis ketika tugas pada dasarnya diperlukan untuk membuat keputusan secara bertahap. Sebagai contoh, pertimbangkan contoh sederhana dari masalah penggantian dan perbaikan peralatan. Katakanlah pada pabrik mesin pengecoran untuk produksi ban pada saat yang sama membuat ban dalam dua bentuk yang berbeda. Dalam hal salah satu bentuk gagal, perlu membongkar mesin. Hal ini dimengerti bahwa kadang-kadang lebih menguntungkan untuk mengganti dan bentuk kedua untuk membongkar mesin dalam kasus dan formulir ini akan bisa dijalankan di tahap berikutnya. Terutama karena lebih mudah untuk mengganti kedua bentuk kerja sebelum mereka mulai gagal. Metode pemrograman dinamis menentukan strategi terbaik dalam hal penggantian formulir ini, dengan mempertimbangkan semua faktor: manfaat dari bentuk melanjutkan eksploitasi, kehilangan downtime mesin, biaya ban dibuang dan banyak lagi.