Menentukan Sub-Masalah untuk Pemrograman Dinamis

Saya telah menggunakan teknik pemrograman dinamis beberapa kali namun hari ini seorang teman bertanya kepada saya bagaimana saya mendefinisikan sub-masalah saya, saya menyadari bahwa saya tidak punya cara untuk memberikan jawaban formal yang objektif. Bagaimana Anda secara resmi mendefinisikan sub-masalah untuk masalah yang akan Anda selesaikan menggunakan pemrograman dinamis?

algorithms dynamic-programming Daniel Gratzer
sumber

Sepertinya tidak ada jawaban yang ada (per April, 2019) yang cukup baik, terutama untuk pemula. Saya akan merekomendasikan tutorial di situs lain.

Apass.Jack

Jawaban:

Prinsip pemrograman dinamis adalah untuk berpikir top-down (yaitu secara rekursif) tetapi menyelesaikan bottom up. Jadi strategi yang baik untuk merancang DP adalah merumuskan masalah secara rekursif dan menghasilkan sub-masalah seperti itu.

Suresh
sumber

Saya mengklaim itu satu - satunya strategi.

JeffE

@ Jeff Jeff Ya, saya membaca dan menggunakan catatan Anda ketika mengajar kelas algoritma saya dan itu efektif. Quote: "Dynamic bukan tentang mengisi tabel. Ini tentang rekursi yang cerdas!"

Dai

Pemahaman saya tentang cara mengajar DP sangat dipengaruhi oleh catatan @ JeffE :)

Suresh

Dimungkinkan juga untuk secara otomatis mengubah prosedur rekursif top-down menjadi algoritma pemrograman dinamis. Ketika Anda akan kembali, simpan jawabannya di tabel hash. Di awal setiap panggilan, periksa apakah jawabannya sudah ada di tabel hash, dan jika demikian, kembalikan segera. Banyak algoritma menjadi mudah dengan ide ini. Misalnya dengan tabel seperti itu, algoritme rekursif saat dicoba secara otomatis berfungsi pada DAWG. Dengan menyimpan nilai sentinel dalam tabel di awal panggilan, algoritma yang sama dapat bekerja bahkan pada DFA. Algoritma pada BDD menjadi sangat mudah untuk ditentukan secara rekursif.

Jules

Last but not least, ini dapat memiliki keunggulan kinerja yang sangat besar. Sebagai contoh, algoritma bottom up subset sum tradisional dapat menghitung banyak entri tabel yang tidak dibutuhkan. Dengan metode ini hanya entri tabel yang diperlukan akan dihitung.

Jules

Seperti yang ditunjukkan @Suresh, setelah Anda tahu bahwa masalah Anda dapat diselesaikan dengan DP (yaitu menunjukkan substruktur yang optimal dan subproblem yang tumpang tindih), Anda mungkin memikirkan solusi membagi dan menaklukkan rekursif.

Tentu saja, membagi dan menaklukkan akan sangat tidak efisien karena setiap masalah yang dihadapi dalam pohon rekursi yang terkait akan dipecahkan lagi bahkan jika sudah ditemukan dan dipecahkan. Di sinilah DP berbeda: setiap kali Anda menemukan subproblem, Anda menyelesaikannya dan menyimpan solusinya dalam sebuah tabel. Kemudian, ketika Anda menemukan lagi subproblem itu, Anda mengaksesnya di $\mathcal{O}(1)$ waktu solusinya daripada menyelesaikannya lagi. Karena jumlah subproblem yang tumpang tindih biasanya dibatasi oleh polinomial, dan waktu yang diperlukan untuk menyelesaikan satu subproblem juga polinomial (jika tidak, DP tidak dapat memberikan solusi yang hemat biaya), Anda mendapatkan secara umum solusi polinomial.

Karena itu, memikirkan solusi membagi dan menaklukkan akan memberi Anda wawasan tentang apa subproblem mungkin untuk masalah khusus Anda.

Massimo Cafaro
sumber

"substruktur optimal" (apa pun artinya) mungkin bukan kondisi yang cukup untuk solvabilitas DP. "Subproblem yang tumpang tindih" tentu bukan yang perlu.

Raphael

Substruktur optimal dan tumpang tindih masalah keduanya ditunjukkan oleh masalah yang dapat diselesaikan secara efisien oleh DP. Tentu saja substruktur optimal saja tidak cukup untuk solvabilitas DP. Namun, jika Anda tidak memiliki subproblem yang tumpang tindih, maka Anda dapat menyelesaikan masalah dengan pembagian biasa dan menaklukkan dengan biaya yang sama: memang, keuntungan DP lebih dari membagi suatu menaklukkan adalah bahwa setiap subproblem diselesaikan tepat sekali ketika ditemui di pohon rekursi .

Massimo Cafaro

Ini bukan formulasi saya: Anda akan menemukannya di "Pengantar algoritma" oleh Cormen, Leiserson, Rivest dan Stein dan pada banyak buku teks lain tentang algoritma.

Massimo Cafaro

Jup, dan sebagian besar setidaknya sebagian salah. Saya senang menguraikan jika Anda memposting pertanyaan yang cocok.

Raphael

Saya tidak yakin saya mengerti dengan benar komentar terakhir Anda. Untuk menunjukkan bahwa jenis karakterisasi ini salah (tidak dapat sebagian salah: baik benar atau salah), Anda dapat dengan sederhana menunjukkan sebagai sampel tandingan, masalah yang tidak menunjukkan substruktur optimal dan subproblem yang tumpang tindih, namun setuju dengan solusi DP polinomial. Tetapi perhatikan bahwa, dalam konteks ini, itu berarti solusi yang terbukti lebih baik daripada membagi dan menaklukkan biasa.

Massimo Cafaro

Pengalaman saya adalah menemukan cara untuk "mengurangi penghitungan berlebihan dengan bantuan menyimpan nilai berguna yang telah disebutkan". Omong-omong, Pemrograman Dinamis sangat populer di ICPC (International Collegiate Programming Contest. Siapa pun dapat memiliki perasaannya sendiri tentang DP setelah melakukan beberapa masalah ICPC.

Peng Zhang
sumber