Apa itu pemrograman dinamis ?
Apa bedanya dengan rekursi, memoisasi, dll?
Saya telah membaca artikel wikipedia di dalamnya, tetapi saya masih belum benar-benar memahaminya.
algorithm
dynamic-programming
smac89
sumber
sumber
Jawaban:
Pemrograman dinamis adalah saat Anda menggunakan pengetahuan masa lalu untuk membuat penyelesaian masalah di masa depan lebih mudah.
Contoh yang baik adalah memecahkan urutan Fibonacci untuk n = 1.000,002.
Ini akan menjadi proses yang sangat panjang, tetapi bagaimana jika saya memberi Anda hasil untuk n = 1.000.000 dan n = 1.000.001? Tiba-tiba masalahnya menjadi lebih mudah dikelola.
Pemrograman dinamis banyak digunakan dalam masalah string, seperti masalah mengedit string. Anda memecahkan sebagian masalah dan kemudian menggunakan informasi itu untuk menyelesaikan masalah asli yang lebih sulit.
Dengan pemrograman dinamis, Anda menyimpan hasil Anda di semacam tabel secara umum. Ketika Anda membutuhkan jawaban untuk suatu masalah, Anda mereferensikan tabel dan melihat apakah Anda sudah tahu apa itu. Jika tidak, Anda menggunakan data di meja Anda untuk memberi diri Anda batu loncatan menuju jawabannya.
Buku Cormen Algorithms memiliki bab yang bagus tentang pemrograman dinamis. DAN gratis di Google Buku! Lihat di sini.
sumber
Pemrograman dinamis adalah teknik yang digunakan untuk menghindari komputasi beberapa kali dari subproblem yang sama dalam algoritma rekursif.
Mari kita ambil contoh sederhana dari angka Fibonacci: menemukan angka Fibonacci ke- n yang ditentukan oleh
F n = F n-1 + F n-2 dan F 0 = 0, F 1 = 1
Pengulangan
Cara yang jelas untuk melakukan ini adalah rekursif:
Pemrograman Dinamis
Rekursi melakukan banyak perhitungan yang tidak perlu karena angka Fibonacci yang diberikan akan dihitung beberapa kali. Cara mudah untuk meningkatkan ini adalah dengan meng-cache hasil:
Cara yang lebih baik untuk melakukan ini adalah dengan menyingkirkan rekursi bersama-sama dengan mengevaluasi hasil dalam urutan yang benar:
Kami bahkan dapat menggunakan ruang konstan dan hanya menyimpan hasil parsial yang diperlukan di sepanjang jalan:
Bagaimana menerapkan pemrograman dinamis?
Pemrograman dinamis umumnya bekerja untuk masalah yang memiliki urutan inheren dari kiri ke kanan seperti string, tree atau integer sequence. Jika algoritma rekursif naif tidak menghitung subproblem yang sama beberapa kali, pemrograman dinamis tidak akan membantu.
Saya membuat kumpulan masalah untuk membantu memahami logika: https://github.com/tristanguigue/dynamic-programing
sumber
if n in cache
seperti contoh dari atas ke bawah atau saya kehilangan sesuatu.Memoisasi adalah ketika Anda menyimpan hasil sebelumnya dari panggilan fungsi (fungsi nyata selalu mengembalikan hal yang sama, diberi input yang sama). Itu tidak membuat perbedaan untuk kompleksitas algoritmik sebelum hasilnya disimpan.
Rekursi adalah metode pemanggilan fungsi itu sendiri, biasanya dengan dataset yang lebih kecil. Karena sebagian besar fungsi rekursif dapat dikonversi ke fungsi iteratif yang serupa, ini tidak membuat perbedaan untuk kompleksitas algoritme.
Pemrograman dinamis adalah proses pemecahan sub-masalah yang lebih mudah untuk diselesaikan dan membangun jawabannya. Sebagian besar algoritma DP akan berjalan antara algoritma Greedy (jika ada) dan algoritma eksponensial (sebutkan semua kemungkinan dan temukan yang terbaik).
sumber
Ini merupakan pengoptimalan dari algoritme Anda yang memotong waktu berjalan.
Sementara Greedy Algorithm biasanya disebut naif , karena dapat berjalan beberapa kali pada set data yang sama, Dynamic Programming menghindari jebakan ini melalui pemahaman yang lebih dalam tentang hasil parsial yang harus disimpan untuk membantu membangun solusi akhir.
Contoh sederhana adalah melintasi pohon atau grafik hanya melalui node yang akan berkontribusi dengan solusi, atau menempatkan ke dalam tabel solusi yang telah Anda temukan sejauh ini sehingga Anda dapat menghindari melintasi node yang sama berulang-ulang.
Berikut adalah contoh masalah yang cocok untuk pemrograman dinamis, dari juri online UVA: Edit Steps Ladder.
Saya akan membuat pengarahan singkat tentang bagian penting dari analisis masalah ini, diambil dari buku Programming Challenges, saya sarankan Anda memeriksanya.
Di sini, analisis yang sangat khusus tentang apa yang diperlukan untuk mengumpulkan hasil parsial paling optimal, adalah apa yang membuat solusi itu "dinamis".
Inilah alternatif, solusi lengkap untuk masalah yang sama. Ini juga "dinamis" walaupun eksekusinya berbeda. Saya sarankan Anda memeriksa seberapa efisien solusinya dengan mengirimkannya ke juri online UVA. Saya merasa luar biasa bagaimana masalah yang sedemikian berat ditangani dengan sangat efisien.
sumber
Bit kunci dari pemrograman dinamis adalah "sub-masalah yang tumpang tindih" dan "substruktur optimal". Sifat-sifat masalah ini berarti bahwa solusi optimal terdiri dari solusi optimal untuk sub-masalahnya. Misalnya, masalah jalur terpendek menunjukkan substruktur optimal. Jalur terpendek dari A ke C adalah jalur terpendek dari A ke beberapa simpul B diikuti oleh jalur terpendek dari simpul B ke C.
Secara lebih rinci, untuk memecahkan masalah jalur terpendek Anda akan:
Karena kami bekerja dari bawah ke atas, kami sudah memiliki solusi untuk sub-masalah ketika tiba saatnya untuk menggunakannya, dengan memoise mereka.
Ingat, masalah pemrograman dinamis harus memiliki sub-masalah yang tumpang tindih, dan substruktur yang optimal. Menghasilkan urutan Fibonacci bukanlah masalah pemrograman yang dinamis; menggunakan memoisasi karena memiliki sub-masalah yang tumpang tindih, tetapi tidak memiliki substruktur yang optimal (karena tidak ada masalah optimasi yang terlibat).
sumber
Pemrograman Dinamis
Definisi
Dynamic programming (DP) adalah teknik desain algoritma umum untuk menyelesaikan masalah dengan sub-masalah yang tumpang tindih. Teknik ini ditemukan oleh ahli matematika Amerika "Richard Bellman" pada 1950-an.
Ide Kunci
Gagasan utamanya adalah menyimpan jawaban yang tumpang tindih dengan sub-masalah yang lebih kecil untuk menghindari perhitungan ulang.
Properti Pemrograman Dinamis
sumber
Saya juga sangat baru dalam Dynamic Programming (algoritma yang kuat untuk jenis masalah tertentu)
Dengan kata paling sederhana, anggap saja pemrograman dinamis sebagai pendekatan rekursif dengan menggunakan pengetahuan sebelumnya
Pengetahuan sebelumnya adalah yang terpenting di sini, Lacak solusi sub-masalah yang sudah Anda miliki.
Pertimbangkan ini, contoh paling mendasar untuk dp dari Wikipedia
Menemukan urutan fibonacci
Mari kita memecah panggilan fungsi dengan mengatakan n = 5
Secara khusus, fib (2) dihitung tiga kali dari awal. Dalam contoh yang lebih besar, lebih banyak nilai fib, atau sub-masalah, dihitung ulang, yang mengarah ke algoritma waktu eksponensial.
Sekarang, mari kita coba dengan menyimpan nilai yang sudah kita temukan dalam struktur data katakanlah Peta
Di sini kita menyimpan solusi sub-masalah di peta, jika kita belum memilikinya. Teknik menyimpan nilai-nilai yang sudah kami hitung ini disebut sebagai Memoisasi.
Akhirnya, Untuk suatu masalah, pertama-tama cobalah untuk menemukan status (kemungkinan sub-masalah dan coba pikirkan pendekatan rekursi yang lebih baik sehingga Anda dapat menggunakan solusi sub-masalah sebelumnya menjadi lebih lanjut).
sumber
Pemrograman dinamis adalah teknik untuk memecahkan masalah dengan sub masalah yang tumpang tindih. Algoritma pemrograman dinamis memecahkan setiap sub masalah hanya sekali dan kemudian Menyimpan jawabannya dalam tabel (array). Menghindari pekerjaan komputasi ulang jawaban setiap kali masalah sub ditemui. Gagasan mendasar dari pemrograman dinamis adalah: Hindari menghitung hal yang sama dua kali, biasanya dengan menyimpan tabel hasil yang diketahui dari sub masalah.
Tujuh langkah dalam pengembangan algoritma pemrograman dinamis adalah sebagai berikut:
sumber
6. Convert the memoized recursive algorithm into iterative algorithm
langkah wajib? Ini berarti bahwa bentuk akhirnya adalah non-rekursif?singkatnya perbedaan antara memoisasi rekursi dan pemrograman Dinamis
Pemrograman dinamis sesuai dengan namanya menggunakan nilai yang dihitung sebelumnya untuk secara dinamis membangun solusi baru berikutnya
Di mana menerapkan pemrograman dinamis: Jika solusi Anda didasarkan pada substruktur yang optimal dan sub masalah yang tumpang tindih, maka dalam hal itu menggunakan nilai yang dihitung sebelumnya akan berguna sehingga Anda tidak perlu menghitungnya kembali. Ini adalah pendekatan dari bawah ke atas. Misalkan Anda perlu menghitung fib (n) dalam hal itu yang perlu Anda lakukan adalah menambahkan nilai terhitung sebelumnya dari fib (n-1) dan fib (n-2)
Rekursi: Pada dasarnya membagi masalah Anda menjadi bagian yang lebih kecil untuk menyelesaikannya dengan mudah tetapi perlu diingat itu tidak menghindari perhitungan ulang jika kita memiliki nilai yang sama dihitung sebelumnya dalam panggilan rekursi lainnya.
Memoisasi: Pada dasarnya menyimpan nilai rekursi yang dihitung lama dalam tabel dikenal sebagai memoisasi yang akan menghindari komputasi ulang jika sudah dihitung oleh beberapa panggilan sebelumnya sehingga nilai apa pun akan dihitung satu kali. Jadi sebelum menghitung kita memeriksa apakah nilai ini sudah dihitung atau belum jika sudah dihitung maka kita mengembalikan yang sama dari tabel alih-alih menghitung ulang. Ini juga merupakan pendekatan top-down
sumber
Berikut ini adalah contoh sederhana kode python dari
Recursive
,Top-down
,Bottom-up
pendekatan untuk seri Fibonacci:Rekursif: O (2 n )
Top-down: O (n) Efisien untuk input yang lebih besar
Bottom-up: O (n) Untuk kesederhanaan dan ukuran input yang kecil
sumber