Kapan saya bisa menggunakan pemrograman dinamis untuk mengurangi kompleksitas waktu dari algoritma rekursif saya?

Pemrograman dinamis dapat mengurangi waktu yang dibutuhkan untuk melakukan algoritma rekursif. Saya tahu bahwa pemrograman dinamis dapat membantu mengurangi kompleksitas waktu dari algoritma. Apakah kondisi umum sedemikian rupa sehingga jika puas dengan algoritma rekursif akan menyiratkan bahwa menggunakan pemrograman dinamis akan mengurangi kompleksitas waktu dari algoritma? Kapan saya harus menggunakan pemrograman dinamis?

algorithms dynamic-programming efficiency algorithm-design Anonim
sumber

Pertanyaan terkait: Menentukan Sub-Masalah untuk Pemrograman Dinamis

Raphael

Jawaban:

Pemrograman dinamis bermanfaat adalah algoritma rekursif Anda menemukan dirinya mencapai situasi yang sama (parameter input) berkali-kali. Ada transformasi umum dari algoritma rekursif ke pemrograman dinamis yang dikenal sebagai memoisasi , di mana ada tabel yang menyimpan semua hasil yang pernah dihitung oleh prosedur rekursif Anda. Ketika prosedur rekursif dipanggil pada set input yang sudah digunakan, hasilnya baru diambil dari tabel. Ini mengurangi Fibonacci rekursif ke Fibonacci berulang.

Pemrograman dinamis dapat menjadi lebih pintar, menerapkan optimasi yang lebih spesifik. Misalnya, kadang-kadang tidak perlu menyimpan seluruh tabel dalam memori pada waktu tertentu.

Yuval Filmus
sumber

Penghitung akan menjadi bahwa kapan pun kompleksitas ruang memoisasi lebih besar daripada data input (mungkin hanya> O (N)), kemungkinan pemrograman dinamis tidak akan membantu. Yaitu, ketika Anda jarang menghadapi situasi yang sama.

edA-qa mort-ora-y

Memoisation! = Pemrograman dinamis!

Raphael

Saya tidak berpikir kita mengatakan itu, tetapi pertanyaannya menunjukkan pengurangan kompleksitas waktu. Pemrograman dinamis dengan sendirinya hanya memecah masalah. Pemrograman dinamis + memoisasi adalah cara umum untuk meningkatkan kompleksitas waktu jika memungkinkan .

edA-qa mort-ora-y

@ edA-qamort-ora-y: Benar. Saya pikir penting untuk menunjukkan hal itu dengan jelas, karena OP tampaknya membingungkan / mencampur konsep.

Raphael

Jika Anda hanya ingin mempercepat algoritme rekursif Anda, memoisasi mungkin cukup. Ini adalah teknik menyimpan hasil panggilan fungsi sehingga panggilan di masa depan dengan parameter yang sama bisa menggunakan kembali hasilnya. Ini berlaku jika (dan hanya jika) fungsi Anda

tidak memiliki efek samping dan
tidak hanya tergantung pada parameternya (yaitu tidak pada beberapa negara).

Ini akan menghemat waktu Anda jika (dan hanya jika) fungsi dipanggil dengan parameter yang sama berulang-ulang. Contoh-contoh populer termasuk definisi rekursif dari angka-angka Fibonacci, yaitu

$\qquad \begin{align} f(0) &= 0 \\ f(1) &= 1 \\ f(n+2) &= f(n+1) + f(n) \qquad ,\ n \geq 0 \end{align}$

Ketika dievaluasi secara naif, sering disebut secara eksponensial. Dengan memoisasi, selalu dihitung dengan , sehingga hanya sejumlah panggilan linear yang tersisa. $f$ $f(n)$ $f(n+1)$

Perhatikan bahwa, sebaliknya, memoisasi hampir tidak berguna untuk algoritma seperti penggabungan: biasanya beberapa (jika ada) sebagian daftar identik, dan pemeriksaan kesetaraan mahal (pengurutan hanya sedikit lebih mahal!).

Dalam implementasi praktis, cara Anda menyimpan hasil sangat penting untuk kinerja. Menggunakan tabel hash mungkin merupakan pilihan yang jelas, tetapi mungkin merusak wilayah. Jika parameter Anda adalah bilangan bulat non-negatif, array adalah pilihan alami tetapi dapat menyebabkan overhead memori yang besar jika Anda hanya menggunakan beberapa entri. Oleh karena itu, memoisasi adalah pertukaran antara efek dan biaya; apakah itu terbayar tergantung pada skenario spesifik Anda.

Pemrograman dinamis adalah binatang yang sepenuhnya lain. Itu berlaku untuk masalah dengan properti itu

dapat dipartisi menjadi sub-masalah (mungkin lebih dari satu cara),
subproblem tersebut dapat diselesaikan secara mandiri,
solusi (optimal) dari subproblem tersebut dapat digabungkan ke (optimal) solusi dari masalah asli dan
subproblem memiliki properti yang sama (atau sepele).

Ini biasanya (secara implisit) tersirat ketika orang-orang menggunakan Bellman Principle of Optimality .

Sekarang, ini hanya menggambarkan kelas masalah yang dapat diekspresikan oleh jenis rekursi tertentu. Evaluasi hal-hal itu (sering) efisien karena memoisasi dapat diterapkan dengan efek yang besar (lihat di atas); biasanya, subproblem yang lebih kecil terjadi sebagai bagian dari banyak masalah yang lebih besar. Contoh populer termasuk jarak edit dan algoritma Bellman-Ford .

Raphael
sumber

Apakah Anda mengatakan ada kasus di mana pemrograman dinamis akan mengarah pada kompleksitas waktu yang lebih baik, tetapi memoisasi tidak akan membantu (atau setidaknya tidak sebanyak)? Apakah Anda punya contoh? Atau apakah Anda hanya mengatakan bahwa pemrograman dinamis hanya berguna untuk sebagian dari masalah di mana memoisasi itu?

svick

@vick: Pemrograman dinamis tidak mempercepat apa pun , hanya jika rekursi DP dievaluasi dengan memoisasi (yang biasanya (!) kasus). Sekali lagi: DP adalah cara untuk memodelkan masalah dalam hal rekursi, memoisasi adalah teknik untuk mempercepat algoritma rekursif yang sesuai (tidak peduli apakah DP). Tidak masuk akal untuk membandingkan keduanya secara langsung. Tentu saja Anda mencoba memodelkan masalah sebagai DP karena Anda berharap untuk menerapkan memoisasi dan karenanya menyelesaikannya lebih cepat daripada pendekatan naif (r). Tetapi sudut pandang DP tidak selalu mengarah pada algoritma yang paling efisien.

Raphael

Jika Anda memiliki banyak prosesor, pemrograman dinamis akan sangat meningkatkan kinerja di dunia nyata karena Anda dapat memparalelkan bagian-bagiannya. Itu sebenarnya tidak mengubah kompleksitas waktu.

edA-qa mort-ora-y

@ edA-qamort-ora-y: Itu benar untuk rekursi apa pun . Namun, tidak jelas apakah ini menciptakan percepatan yang baik, karena memoisasi kurang efisien di atas batas prosesor.

Raphael

Koreksi: evalutasi DP-kambuh secara naif masih dapat (banyak) lebih cepat dari brute force; lih. di sini .

Raphael