Apa perbedaan antara memoisasi dan pemrograman dinamis? Saya pikir pemrograman dinamis adalah bagian dari memoisasi. Apakah tepat?
dynamic-programming
terminology
difference
memoization
Sanghyun Lee
sumber
sumber
Jawaban:
Artikel yang relevan tentang Pemrograman.Guide: Pemrograman dinamis vs memoisasi vs tabulasi
Memoisasi adalah istilah yang menggambarkan teknik pengoptimalan tempat Anda menyimpan hasil yang dihitung sebelumnya, dan mengembalikan hasil yang di-cache ketika perhitungan yang sama diperlukan lagi.
Pemrograman dinamis adalah teknik untuk memecahkan masalah yang bersifat rekursif, iteratif dan dapat diterapkan ketika perhitungan subproblem tumpang tindih.
Pemrograman dinamis biasanya diimplementasikan menggunakan tabulasi, tetapi juga dapat diimplementasikan menggunakan memoisasi. Jadi seperti yang Anda lihat, tidak ada yang merupakan "bagian" dari yang lain.
Pertanyaan tindak lanjut yang masuk akal adalah: Apa perbedaan antara tabulasi (teknik pemrograman dinamis yang khas) dan memoisasi?
Saat Anda memecahkan masalah pemrograman dinamis menggunakan tabulasi, Anda memecahkan masalah " bottom up ", yaitu dengan menyelesaikan semua sub-masalah terkait terlebih dahulu, biasanya dengan mengisi tabel n- dimensi. Berdasarkan hasil dalam tabel, solusi untuk masalah "atas" / asli kemudian dihitung.
Jika Anda menggunakan memoisasi untuk menyelesaikan masalah Anda melakukannya dengan mempertahankan peta sub masalah yang sudah diselesaikan. Anda melakukannya " top down " dalam arti bahwa Anda memecahkan masalah "top" terlebih dahulu (yang biasanya berulang untuk memecahkan sub-masalah).
Slide yang bagus dari
sini(tautannya sudah mati, slide tetap bagus):Sumber daya tambahan:
sumber
http://www.geeksforgeeks.org/dynamic-programming-set-1/
Memoisasi adalah metode mudah untuk melacak solusi yang dipecahkan sebelumnya (sering diimplementasikan sebagai pasangan nilai kunci hash, sebagai lawan dari tabulasi yang sering didasarkan pada array) sehingga mereka tidak dihitung ulang ketika mereka ditemui lagi. Ini dapat digunakan dalam metode bottom-up atau top-down.
Lihat diskusi ini tentang memoisasi vs tabulasi.
Jadi pemrograman Dinamis adalah metode untuk memecahkan kelas masalah tertentu dengan memecahkan hubungan perulangan / rekursi dan menyimpan solusi yang sebelumnya ditemukan baik melalui tabulasi atau memoisasi. Memoisasi adalah metode untuk melacak solusi untuk masalah yang dipecahkan sebelumnya dan dapat digunakan dengan fungsi apa pun yang memiliki solusi deterministik unik untuk serangkaian input yang diberikan.
sumber
Pemrograman Dinamis sering disebut Memoisasi!
Memoisasi adalah teknik top-down (mulai memecahkan masalah yang diberikan dengan memecahnya) dan pemrograman dinamis adalah teknik bottom-up (mulai pemecahan dari sub-masalah sepele, hingga masalah yang diberikan)
DP menemukan solusinya dengan mulai dari kasing dan bekerja ke atas. DP menyelesaikan semua sub-masalah, karena ia melakukan bottom-up
DP memiliki potensi untuk mengubah solusi brute-force eksponensial-waktu menjadi algoritma polinomial-waktu.
DP mungkin jauh lebih efisien karena sifatnya yang berulang
Agar lebih sederhana, Memoization menggunakan pendekatan top-down untuk menyelesaikan masalah yaitu mulai dengan masalah inti (utama) kemudian memecahnya menjadi sub-masalah dan menyelesaikan sub-masalah ini dengan cara yang sama. Dalam pendekatan ini sub-masalah yang sama dapat terjadi beberapa kali dan mengkonsumsi lebih banyak siklus CPU, karenanya menambah kompleksitas waktu. Sedangkan dalam pemrograman dinamis, sub-masalah yang sama tidak akan diselesaikan beberapa kali tetapi hasil sebelumnya akan digunakan untuk mengoptimalkan solusi.
sumber
(1) Memoisasi dan DP, secara konseptual , benar-benar sama. Karena: pertimbangkan definisi DP: "subproblem yang tumpang tindih" "dan substruktur optimal". Memoisasi sepenuhnya memiliki 2 ini.
(2) Memoisasi adalah DP dengan risiko stack overflow adalah rekursi yang dalam. DP bottom up tidak memiliki risiko ini.
(3) Memoisasi membutuhkan tabel hash. Jadi ruang tambahan, dan beberapa waktu pencarian.
Jadi untuk menjawab pertanyaan:
- Secara konseptual , (1) berarti mereka adalah hal yang sama.
-Mengambil (2) ke akun, jika Anda benar-benar ingin, memoisasi adalah bagian dari DP, dalam arti bahwa masalah dipecahkan oleh memoisasi akan dipecahkan oleh DP, tetapi masalah yang dipecahkan oleh DP mungkin tidak dapat dipecahkan dengan memoisasi (karena itu mungkin menumpuk overflow).
-Mengambil (3) akun, mereka memiliki perbedaan kecil dalam kinerja.
sumber
Dari wikipedia:
Memoisasi
Pemrograman Dinamis
Saat memecah masalah menjadi subproblem yang lebih kecil / sederhana, kami sering menghadapi subproblem yang sama lebih dari satu kali - jadi kami menggunakan Memoisasi untuk menyimpan hasil perhitungan sebelumnya sehingga kami tidak perlu mengulanginya.
Pemrograman dinamis sering menghadapi situasi di mana masuk akal untuk menggunakan memoisasi tetapi Anda dapat menggunakan kedua teknik tanpa harus menggunakan yang lain.
sumber
Baik Memoization dan Dynamic Programming hanya memecahkan satu masalah saja.
Memoisasi menggunakan rekursi dan bekerja dari atas ke bawah, sedangkan pemrograman Dinamis bergerak ke arah yang berlawanan memecahkan masalah dari bawah ke atas.
Di bawah ini adalah analogi yang menarik -
Top-down - Pertama, Anda mengatakan saya akan mengambil alih dunia. Bagaimana Anda akan melakukannya? Anda mengatakan saya akan mengambil alih Asia lebih dulu. Bagaimana Anda akan melakukannya? Saya akan mengambil alih India terlebih dahulu. Saya akan menjadi Ketua Menteri Delhi, dll.
Bottom-up - Anda mengatakan saya akan menjadi CM Delhi. Kemudian akan mengambil alih India, lalu semua negara lain di Asia dan akhirnya aku akan mengambil alih dunia.
sumber
Saya ingin memberikan contoh ;
Masalah:
Rekursi dengan Memoisasi
Dengan cara ini kita memangkas (menghilangkan material berlebih dari pohon atau pohon perulangan) dengan bantuan array memo dan mengurangi ukuran pohon rekursi hingga akhir.
Pemrograman Dinamis
Seperti yang kita lihat masalah ini dapat dipecah menjadi subproblem, dan itu berisi properti substruktur yang optimal yaitu solusi optimalnya dapat dibangun secara efisien dari solusi optimal subproblemnya, kita dapat menggunakan pemrograman dinamis untuk menyelesaikan masalah ini.
Contoh mengambil dari https://leetcode.com/problems/climbing-stairs/
sumber
Pikirkan dua cara,
Dalam Memoization kita pergi dengan (1.) di mana kita menyimpan setiap panggilan fungsi dalam cache dan memanggil kembali dari sana. Agak mahal karena melibatkan panggilan rekursif.
Dalam Dynamic Programming kita pergi dengan (2.) di mana kita memelihara tabel, bottom-up dengan menyelesaikan subproblem menggunakan data yang disimpan dalam tabel, biasanya disebut sebagai dp-table.
catatan:
Keduanya berlaku untuk masalah dengan sub-masalah yang Tumpang tindih.
Memoisasi berperforma buruk untuk DP karena overhead yang terlibat selama panggilan fungsi rekursif.
sumber
Dalam Pemrograman Dinamis ,
Dalam Penghafalan ,
sumber