Pemrograman Dinamis
- Diperkenalkan oleh
- Richard Bellman
- Tahun
- 1957
- Jenis
- Exact combinatorial optimization via recursive decomposition
- Keluarga
- Mathematical programming
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Dinamis (DP) adalah teknik optimasi eksak yang diperkenalkan oleh Richard Bellman pada tahun 1957 untuk memecahkan masalah keputusan multi-tahap.
Teknik ini menguraikan masalah kompleks menjadi submasalah yang lebih sederhana dan tumpang tindih, memecahkan setiap submasalah sekali, dan menyimpan hasilnya untuk menghindari komputasi yang berulang. Berlandaskan Prinsip Optimalitas, DP menjamin solusi optimal global kapan pun masalah menunjukkan submasalah yang tumpang tindih dan substruktur optimal.
Intuisi di balik metode
Bayangkan merencanakan rute terpendek melintasi kota dengan terlebih dahulu mencari jalur terpendek antara setiap pasangan persimpangan yang berdekatan, kemudian menggabungkan solusi-solusi kecil tersebut ke atas. Alih-alih menjelajahi kembali setiap kemungkinan rute lengkap dari awal, Anda menggunakan kembali jawaban lokal yang telah dihitung sebelumnya. Pemrograman Dinamis bekerja dengan cara yang sama: ia menyimpan solusi untuk submasalah kecil sehingga membangun jawaban lengkap hanya memerlukan pencarian tabel daripada komputasi berat yang berulang.
Sejarah
Richard Bellman menciptakan istilah 'pemrograman dinamis' pada tahun 1957 saat bekerja di RAND Corporation, sengaja memilih kata 'pemrograman' untuk merujuk pada perencanaan daripada pengkodean komputer. Prinsip Optimalitas yang ia nyatakan menjadi landasan teoretis untuk teori kontrol, riset operasi, dan kemudian pembelajaran penguatan. Algoritma DP klasik — jalur terpendek Dijkstra, algoritma Viterbi, dan penyelarasan urutan Needleman-Wunsch — semuanya berasal langsung dari kerangka kerja Bellman.
Kapan digunakan
Pemrograman Dinamis sesuai ketika suatu masalah memiliki submasalah yang tumpang tindih dan substruktur optimal — properti yang umum dalam pengambilan keputusan sekuensial, alokasi sumber daya, penjadwalan, dan tugas penyelarasan string. Teknik ini memerlukan ruang keadaan yang sepenuhnya dapat dihitung dan berukuran terkelola; metode ini menderita kutukan dimensionalitas ketika variabel keadaan banyak atau kontinu. Untuk masalah dengan ruang keadaan yang sulit dipecahkan, DP perkiraan atau pembelajaran penguatan adalah alternatif yang lebih disukai.
Batasan dan pertimbangan
- Menderita kutukan dimensionalitas: persyaratan memori dan waktu tumbuh secara eksponensial dengan jumlah variabel keadaan.
- Memerlukan pengetahuan awal yang lengkap tentang struktur transisi dan fungsi imbalan; tidak dapat diterapkan pada lingkungan yang tidak diketahui tanpa perkiraan.
- Ruang keadaan harus diskrit atau dapat didiskritisasi; masalah berdimensi tinggi yang kontinu menuntut skema perkiraan yang mengorbankan keeksakan.
- Merumuskan representasi keadaan dan relasi rekurensi yang benar memerlukan wawasan spesifik masalah yang substansial.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menjamin solusi optimal global yang eksak untuk masalah yang memenuhi Prinsip Optimalitas.
- Menghilangkan komputasi berulang melalui memoization, mencapai waktu polinomial dalam jumlah keadaan.
- Menghasilkan kebijakan optimal yang eksplisit, bukan hanya nilai optimal, memungkinkan dukungan keputusan yang mudah.
- Dapat diterapkan secara luas di berbagai domain termasuk teori kontrol, bioinformatika, ekonomi, dan riset operasi.
Penerapan
- Masalah jalur terpendek dan perutean dalam jaringan (varian Bellman-Ford, Dijkstra).
- Penyelarasan urutan dalam biologi komputasi (algoritma Needleman-Wunsch, Smith-Waterman).
- Alokasi sumber daya optimal dan masalah kombinatorial tipe ransel dalam riset operasi.
- Pengenalan ucapan dan tulisan tangan melalui algoritma Viterbi pada Model Markov Tersembunyi.
- Kontrol optimal dan optimasi portofolio multi-periode dalam ekonomi dan teknik.
Cara kerjanya
Cara kerjanya
Masalah optimasi keseluruhan diekspresikan sebagai relasi rekurensi. Untuk setiap keadaan s dan tahap keputusan n, fungsi nilai V_n(s) sama dengan imbalan langsung terbaik ditambah nilai diskonto dari keadaan berikutnya yang dihasilkan. Persamaan Bellman ini memformalkan Prinsip Optimalitas: setiap sub-jalur dari jalur optimal haruslah optimal.
Rumus
V_n(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V_{n-1}(T(s,a)) \right]Rekurensi diselesaikan secara iteratif atau rekursif. Dalam iterasi nilai, V^*(s) diperbarui berulang kali di semua keadaan hingga konvergensi, menggunakan perkiraan nilai keadaan tetangga saat ini. Setiap pembaruan menggantikan nilai lama dengan imbalan terbaik yang dapat dicapai ditambah nilai masa depan, menyebarkan informasi optimalitas melalui ruang keadaan.
Rumus
V^*(s) = \max_{a \in A(s)} \left[ r(s,a) + \gamma V^*(s') \right], \quad s' = T(s,a)Nilai yang dihitung disimpan dalam tabel yang diindeks berdasarkan keadaan. Keadaan terminal menerima nilai dasar nol (atau imbalan yang diketahui), dan semua entri lainnya diisi saat submasalah diselesaikan. Memoization memastikan setiap keadaan dievaluasi paling banyak sekali, mengurangi pencarian rekursif eksponensial menjadi waktu polinomial dalam jumlah keadaan dan tahapan.
Rumus
\text{Table}[s] = \begin{cases} 0 & \text{if } s \in S_{\text{terminal}} \\ V^*(s) & \text{otherwise} \end{cases}Setelah tabel nilai lengkap, kebijakan optimal pi^*(s) dipulihkan melalui lintasan serakah sederhana: untuk setiap keadaan, pilih tindakan yang memaksimalkan imbalan langsung ditambah nilai tersimpan dari keadaan penerus. Ekstraksi satu lintasan ini murah secara komputasi dan menghasilkan aturan keputusan deterministik yang optimal secara global.
Rumus
\pi^*(s) = \arg\max_{a \in A(s)} \left[ r(s,a) + \gamma \, \text{Table}[T(s,a)] \right]Kesalahan umum
- Mendefinisikan representasi keadaan yang kurang ekspresif mengarah pada rekurensi yang salah dan solusi suboptimal.
- Mencampuradukkan memoization top-down dengan tabulasi bottom-up dapat menghasilkan kesalahan luapan tumpukan atau urutan evaluasi submasalah yang salah.
- Menerapkan DP pada masalah yang tidak memiliki substruktur optimal (misalnya, jalur terpanjang dalam graf umum) menghasilkan hasil yang salah tanpa peringatan.
- Mengabaikan presisi numerik dalam komputasi imbalan kumulatif dapat menyebabkan kesalahan optimalitas halus dalam implementasi floating-point.
Pertanyaan yang sering diajukan
Apa perbedaan antara pemrograman dinamis dan divide-and-conquer?
Keduanya menguraikan masalah menjadi submasalah, tetapi divide-and-conquer mengasumsikan submasalah independen yang hanya dipecahkan sekali secara alami. Pemrograman dinamis menargetkan submasalah yang tumpang tindih — submasalah yang sama muncul di banyak cabang — dan menyimpan hasil untuk menghindari pekerjaan yang berulang. Tanpa submasalah yang tumpang tindih, DP tidak menawarkan keuntungan komputasi dibandingkan rekursi langsung.
Kapan saya harus menggunakan memoization top-down versus tabulasi bottom-up?
Memoization top-down lebih mudah diimplementasikan langsung dari rekurensi dan hanya menghitung submasalah yang diperlukan, menguntungkan ruang keadaan yang jarang. Tabulasi bottom-up menghindari overhead rekursi dan batas tumpukan, cocok untuk ruang keadaan yang padat, dan seringkali lebih cepat dalam praktik. Pilih top-down ketika himpunan submasalah yang diperlukan sulit diprediksi, bottom-up ketika semua submasalah akan diperlukan.
Bagaimana pemrograman dinamis berhubungan dengan pembelajaran penguatan?
DP klasik memerlukan model Proses Keputusan Markov (probabilitas transisi dan imbalan) yang sepenuhnya diketahui. Pembelajaran penguatan memperluas ide DP ke pengaturan di mana model tidak diketahui, menggunakan pengalaman sampel sebagai gantinya. Algoritma seperti Q-learning dan metode gradien kebijakan adalah prosedur DP perkiraan yang mempelajari fungsi nilai dari interaksi daripada dari model eksplisit.
Metode terkait
Sumber
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
ISBN: 978-0-691-07951-6Disalin.