Pendekatan bottom-up (untuk pemrograman dinamis) terdiri dari pertama-tama melihat subproblem "lebih kecil", dan kemudian menyelesaikan subproblem yang lebih besar menggunakan solusi untuk masalah yang lebih kecil.
The top-down terdiri dalam memecahkan masalah dalam "cara alami" dan centang jika Anda telah menghitung solusi untuk subproblem sebelumnya.
Saya agak bingung. Apa perbedaan antara keduanya?
Jawaban:
Rekap
Pemrograman dinamis adalah semua tentang memesan komputasi Anda dengan cara yang menghindari penghitungan ulang pekerjaan duplikat. Anda memiliki masalah utama (akar pohon submasalah Anda), dan submasalah (sub pohon). Submasalah biasanya berulang dan tumpang tindih .
Sebagai contoh, perhatikan contoh favorit Anda dari Fibonnaci. Ini adalah pohon penuh masalah, jika kami melakukan panggilan rekursif yang naif:
(Dalam beberapa masalah langka lainnya, pohon ini bisa menjadi tak terbatas di beberapa cabang, mewakili non-pemutusan, dan dengan demikian bagian bawah pohon mungkin sangat besar. Selanjutnya, dalam beberapa masalah Anda mungkin tidak tahu seperti apa bentuk pohon penuh di depan Oleh karena itu, Anda mungkin perlu strategi / algoritma untuk memutuskan subproblem mana yang akan diungkapkan.)
Memoisasi, Tabulasi
Setidaknya ada dua teknik utama pemrograman dinamis yang tidak saling eksklusif:
Memoisasi - Ini adalah pendekatan laissez-faire: Anda menganggap bahwa Anda telah menghitung semua sub-masalah dan bahwa Anda tidak tahu apa urutan evaluasi yang optimal. Biasanya, Anda akan melakukan panggilan rekursif (atau setara berulang) dari root, dan baik berharap Anda akan mendekati urutan evaluasi optimal, atau mendapatkan bukti bahwa Anda akan membantu Anda tiba di urutan evaluasi optimal. Anda akan memastikan bahwa panggilan rekursif tidak pernah menghitung ulang subproblem karena Anda men - cache hasil, dan dengan demikian duplikat sub-pohon tidak dihitung ulang.
fib(100)
, Anda hanya akan memanggil ini, dan itu akan memanggilfib(100)=fib(99)+fib(98)
, yang akan memanggilfib(99)=fib(98)+fib(97)
, ... dll ..., yang akan memanggilfib(2)=fib(1)+fib(0)=1+0=1
. Maka akhirnya akan menyelesaikanfib(3)=fib(2)+fib(1)
, tetapi tidak perlu menghitung ulangfib(2)
, karena kami menyimpannya.Tabulasi - Anda juga dapat menganggap pemrograman dinamis sebagai algoritma "pengisian tabel" (meskipun biasanya multidimensi, 'tabel' ini mungkin memiliki geometri non-Euclidean dalam kasus yang sangat jarang *). Ini seperti memoisasi tetapi lebih aktif, dan melibatkan satu langkah tambahan: Anda harus memilih, sebelumnya, urutan yang tepat di mana Anda akan melakukan perhitungan. Ini seharusnya tidak menyiratkan bahwa urutannya harus statis, tetapi Anda memiliki lebih banyak fleksibilitas daripada memoisasi.
fib(2)
,fib(3)
,fib(4)
... caching setiap nilai sehingga Anda dapat menghitung yang berikutnya lebih mudah. Anda juga dapat menganggapnya sebagai mengisi tabel (bentuk caching lainnya).(Pada umumnya, dalam paradigma "pemrograman dinamis", saya akan mengatakan programmer menganggap seluruh pohon, lalumenulis sebuah algoritma yang mengimplementasikan strategi untuk mengevaluasi subproblem yang dapat mengoptimalkan properti apa pun yang Anda inginkan (biasanya kombinasi dari kompleksitas waktu dan kompleksitas ruang). Strategi Anda harus dimulai di suatu tempat, dengan beberapa masalah tertentu, dan mungkin dapat menyesuaikan diri berdasarkan hasil evaluasi tersebut. Dalam pengertian umum "pemrograman dinamis", Anda mungkin mencoba untuk men-cache subproblem ini, dan lebih umum, cobalah menghindari mengunjungi kembali subproblem dengan perbedaan halus mungkin menjadi kasus grafik di berbagai struktur data. Sangat sering, struktur data ini pada intinya seperti array atau tabel. Solusi untuk submasalah dapat dibuang jika kita tidak membutuhkannya lagi.)
[Sebelumnya, jawaban ini membuat pernyataan tentang terminologi top-down vs bottom-up; jelas ada dua pendekatan utama yang disebut Memoisasi dan Tabulasi yang mungkin bertentangan dengan istilah-istilah tersebut (meskipun tidak sepenuhnya). Istilah umum yang digunakan kebanyakan orang adalah "Pemrograman Dinamis" dan beberapa orang mengatakan "Memoisasi" untuk merujuk pada subtipe khusus "Pemrograman Dinamis." Jawaban ini menolak untuk mengatakan mana yang top-down dan bottom-up sampai komunitas dapat menemukan referensi yang tepat dalam makalah akademik. Pada akhirnya, penting untuk memahami perbedaan daripada terminologi.]
Pro dan kontra
Kemudahan coding
Memoisasi sangat mudah untuk dikodekan (Anda biasanya dapat * menulis anotasi "memoizer" atau fungsi pembungkus yang secara otomatis melakukannya untuk Anda), dan harus menjadi garis pendekatan pertama Anda. Kelemahan dari tabulasi adalah Anda harus membuat pemesanan.
* (ini sebenarnya hanya mudah jika Anda menulis sendiri fungsinya, dan / atau mengkode dalam bahasa pemrograman yang tidak murni / tidak berfungsi ... misalnya jika seseorang sudah menulis
fib
fungsi yang dikompilasi , itu harus membuat panggilan rekursif untuk dirinya sendiri, dan Anda tidak dapat secara ajaib memoize fungsi tanpa memastikan panggilan rekursif itu memanggil fungsi memoized baru Anda (dan bukan fungsi yang tidak diememoasi asli))Kekambuhan
Perhatikan bahwa top-down dan bottom-up dapat diimplementasikan dengan rekursi atau pengisian tabel berulang, meskipun mungkin tidak alami.
Kekhawatiran praktis
Dengan memoisasi, jika pohonnya sangat dalam (mis.
fib(10^6)
), Anda akan kehabisan ruang stack, karena setiap perhitungan yang tertunda harus diletakkan di stack, dan Anda akan memiliki 10 ^ 6 dari mereka.Optimalitas
Salah satu pendekatan mungkin tidak optimal-waktu jika pesanan Anda (atau mencoba) mengunjungi subproblem tidak optimal, khususnya jika ada lebih dari satu cara untuk menghitung subproblem (biasanya caching akan menyelesaikan ini, tetapi secara teori dimungkinkan bahwa caching mungkin tidak dalam beberapa kasus eksotis). Memoisasi biasanya akan menambah kompleksitas waktu Anda ke kompleksitas ruang Anda (misalnya dengan tabulasi Anda memiliki lebih banyak kebebasan untuk membuang perhitungan, seperti menggunakan tabulasi dengan Fib memungkinkan Anda menggunakan ruang O (1), tetapi memoisasi dengan Fib menggunakan O (N) tumpukan ruang).
Optimalisasi tingkat lanjut
Jika Anda juga melakukan masalah yang sangat rumit, Anda mungkin tidak punya pilihan selain melakukan tabulasi (atau setidaknya mengambil peran lebih aktif dalam mengarahkan memoisasi ke tempat yang Anda inginkan). Juga jika Anda berada dalam situasi di mana optimasi benar-benar kritis dan Anda harus mengoptimalkan, tabulasi akan memungkinkan Anda untuk melakukan optimasi mana memoisasi tidak akan membiarkan Anda melakukannya dengan cara yang waras. Menurut pendapat saya yang sederhana, dalam rekayasa perangkat lunak normal, tak satu pun dari kedua kasus ini pernah muncul, jadi saya hanya akan menggunakan memoisasi ("fungsi yang menyimpan jawabannya") kecuali jika sesuatu (seperti ruang stack) membuat tabulasi diperlukan ... meskipun secara teknis untuk menghindari ledakan tumpukan Anda dapat 1) meningkatkan batas ukuran tumpukan dalam bahasa yang memungkinkannya, atau 2) memakan faktor konstan dari pekerjaan ekstra untuk memvirtualisasikan tumpukan Anda (ick),
Contoh yang lebih rumit
Di sini kami mendaftar contoh-contoh yang menarik, yang bukan hanya masalah DP umum, tetapi yang menarik membedakan memoisasi dan tabulasi. Misalnya, satu formulasi mungkin jauh lebih mudah daripada yang lain, atau mungkin ada optimasi yang pada dasarnya memerlukan tabulasi:
sumber
python memoization decorator
; beberapa bahasa akan memungkinkan Anda menulis makro atau kode yang merangkum pola memoisasi. Pola memoisasi tidak lebih dari "daripada memanggil fungsi, cari nilai dari cache (jika nilainya tidak ada, hitung dan tambahkan ke cache terlebih dahulu)".fib(513)
. Terminologi kelebihan beban yang saya rasakan menghambat di sini. 1) Anda selalu dapat membuang sub-masalah yang tidak lagi Anda perlukan. 2) Anda selalu dapat menghindari penghitungan masalah yang tidak Anda butuhkan. 3) 1 dan 2 mungkin jauh lebih sulit untuk dikodekan tanpa struktur data eksplisit untuk menyimpan subproblem, ATAU, lebih sulit jika aliran kontrol harus menenun antar panggilan fungsi (Anda mungkin perlu status atau kelanjutan).DP top-down dan bottom-up adalah dua cara berbeda untuk menyelesaikan masalah yang sama. Pertimbangkan solusi pemrograman memoized (atas ke bawah) vs dinamis (bawah ke atas) untuk menghitung angka fibonacci.
Saya pribadi menemukan memoisasi jauh lebih alami. Anda dapat mengambil fungsi rekursif dan memoize itu dengan proses mekanis (pertama mencari jawaban dalam cache dan mengembalikannya jika memungkinkan, jika tidak menghitungnya secara rekursif dan kemudian sebelum kembali, Anda menyimpan perhitungan dalam cache untuk digunakan di masa mendatang), sedangkan melakukan bottom up pemrograman dinamis mengharuskan Anda untuk menyandikan urutan solusi yang dihitung, sehingga tidak ada "masalah besar" yang dihitung sebelum masalah yang lebih kecil yang bergantung padanya.
sumber
Fitur utama dari pemrograman dinamis adalah adanya subproblem yang tumpang tindih . Yaitu, masalah yang Anda coba selesaikan dapat dipecah menjadi subproblem, dan banyak dari subproblem tersebut berbagi sub-masalah. Itu seperti "Membagi dan menaklukkan", tetapi Anda akhirnya melakukan hal yang sama berkali-kali. Contoh yang saya gunakan sejak 2003 ketika mengajar atau menjelaskan masalah ini: Anda dapat menghitung angka Fibonacci secara rekursif.
Gunakan bahasa favorit Anda dan coba jalankan untuk
fib(50)
. Ini akan memakan waktu yang sangat, sangat lama. Kira-kira sebanyak waktufib(50)
itu sendiri! Namun, banyak pekerjaan yang tidak perlu sedang dilakukan.fib(50)
akan memanggilfib(49)
danfib(48)
, tetapi kemudian keduanya akan berakhir memanggilfib(47)
, meskipun nilainya sama. Bahkan,fib(47)
akan dihitung tiga kali: dengan panggilan langsung darifib(49)
, dengan panggilan langsung darifib(48)
, dan juga dengan panggilan langsung dari yang lainfib(48)
, salah satu yang dihasilkan oleh perhitunganfib(49)
... Jadi Anda lihat, kami memiliki subproblem yang tumpang tindih .Berita bagus: tidak perlu menghitung nilai yang sama berkali-kali. Setelah Anda menghitungnya sekali, simpan hasilnya, dan lain kali gunakan nilai yang di-cache! Ini adalah inti dari pemrograman dinamis. Anda dapat menyebutnya "top-down", "memoization", atau apa pun yang Anda inginkan. Pendekatan ini sangat intuitif dan sangat mudah diimplementasikan. Cukup tulis solusi rekursif terlebih dahulu, ujilah pada tes kecil, tambahkan memoisasi (caching dari nilai yang sudah dihitung), dan --- bingo! --- kamu selesai.
Biasanya Anda juga dapat menulis program iteratif setara yang bekerja dari bawah ke atas, tanpa rekursi. Dalam hal ini ini akan menjadi pendekatan yang lebih alami: loop dari 1 hingga 50 menghitung semua angka Fibonacci saat Anda pergi.
Dalam skenario yang menarik, solusi dari bawah ke atas biasanya lebih sulit untuk dipahami. Namun, begitu Anda memahaminya, biasanya Anda akan mendapatkan gambaran besar yang lebih jelas tentang bagaimana algoritma bekerja. Dalam praktiknya, ketika memecahkan masalah nontrivial, saya sarankan terlebih dahulu menulis pendekatan top-down dan mengujinya pada contoh-contoh kecil. Kemudian tulis solusi bottom-up dan bandingkan keduanya untuk memastikan Anda mendapatkan hal yang sama. Idealnya, bandingkan dua solusi secara otomatis. Tulis rutin kecil yang akan menghasilkan banyak tes, idealnya - semuanyates kecil hingga ukuran tertentu --- dan memvalidasi bahwa kedua solusi memberikan hasil yang sama. Setelah itu gunakan solusi bottom-up dalam produksi, tetapi simpan kode top-bottom, berkomentar. Ini akan memudahkan pengembang lain untuk memahami apa yang Anda lakukan: kode bottom-up bisa sangat tidak bisa dimengerti, bahkan Anda yang menulisnya dan bahkan jika Anda tahu persis apa yang Anda lakukan.
Dalam banyak aplikasi pendekatan bottom-up sedikit lebih cepat karena overhead panggilan rekursif. Stack overflow juga bisa menjadi masalah dalam masalah-masalah tertentu, dan perhatikan bahwa ini sangat bergantung pada input data. Dalam beberapa kasus Anda mungkin tidak dapat menulis tes yang menyebabkan stack overflow jika Anda tidak memahami pemrograman dinamis dengan baik, tetapi suatu hari ini mungkin masih terjadi.
Sekarang, ada masalah di mana pendekatan top-down adalah satu-satunya solusi yang layak karena ruang masalah sangat besar sehingga tidak mungkin untuk menyelesaikan semua submasalah. Namun, "caching" masih berfungsi dalam waktu yang wajar karena input Anda hanya membutuhkan sebagian kecil dari subproblem yang harus dipecahkan --- tetapi terlalu sulit untuk secara eksplisit mendefinisikan, subproblem mana yang perlu Anda selesaikan, dan karenanya menulis bottom- solusi atas. Di sisi lain, ada situasi di mana Anda tahu Anda harus menyelesaikan semua submasalah. Dalam hal ini, lanjutkan dan gunakan bottom-up.
Saya pribadi akan menggunakan atas-bawah untuk optimasi Paragraf alias masalah optimasi bungkus kata (lihat algoritma pemecah garis Knuth-Plass; setidaknya TeX menggunakannya, dan beberapa perangkat lunak oleh Adobe Systems menggunakan pendekatan yang sama). Saya akan menggunakan bottom-up untuk Fast Fourier Transform .
sumber
Mari kita ambil seri fibonacci sebagai contoh
Cara lain untuk mengatakannya,
Dalam kasus lima nomor fibonacci pertama
Sekarang mari kita lihat algoritma seri Fibonacci rekursif sebagai contoh
Sekarang jika kita menjalankan program ini dengan perintah berikut
jika kita melihat dari dekat ke algoritma, untuk menghasilkan angka kelima diperlukan angka ke-3 dan ke-4. Jadi rekursi saya sebenarnya dimulai dari atas (5) dan kemudian berlanjut sampai ke angka bawah / bawah. Pendekatan ini sebenarnya adalah pendekatan top-down.
Untuk menghindari melakukan perhitungan yang sama beberapa kali, kami menggunakan teknik Pemrograman Dinamis. Kami menyimpan nilai yang dihitung sebelumnya dan menggunakannya kembali. Teknik ini disebut memoisasi. Ada lebih banyak untuk pemrograman dinamis selain memoisasi yang tidak diperlukan untuk membahas masalah saat ini.
Perintahkan ke bawah
Mari kita menulis ulang algoritma asli kita dan menambahkan teknik memoised.
Dan kami menjalankan metode ini seperti berikut
Solusi ini masih top-down sebagai algoritma mulai dari nilai teratas dan pergi ke bawah setiap langkah untuk mendapatkan nilai teratas kami.
Bawah ke Atas
Tapi, pertanyaannya adalah, bisakah kita mulai dari bawah, seperti dari nomor fibonacci pertama lalu berjalan ke atas. Mari kita menulis ulang menggunakan teknik ini,
Sekarang jika kita melihat algoritma ini sebenarnya dimulai dari nilai yang lebih rendah kemudian pergi ke atas. Jika saya membutuhkan nomor 5 fibonacci saya benar-benar menghitung 1, kemudian kedua lalu ketiga sampai ke nomor 5. Teknik ini sebenarnya disebut teknik bottom-up.
Terakhir dua, algoritma memenuhi persyaratan pemrograman dinamis. Tapi satu dari atas ke bawah dan satu lagi dari bawah ke atas. Kedua algoritma memiliki kompleksitas ruang dan waktu yang serupa.
sumber
Pemrograman Dinamis sering disebut Memoisasi!
1.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)
2.DP menemukan solusinya dengan mulai dari kasus dasar dan bekerja ke atas. DP menyelesaikan semua sub-masalah, karena ia melakukan bottom-up
DP memiliki potensi untuk mengubah solusi brute-force waktu eksponensial menjadi algoritma waktu polinomial.
DP mungkin jauh lebih efisien karena sifatnya yang berulang
Agar lebih sederhana, Memoization menggunakan pendekatan top-down untuk memecahkan 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
Cukup mengatakan pendekatan top-down menggunakan rekursi untuk memanggil masalah Sub berulang-ulang di
mana sebagai pendekatan bottom-up menggunakan single tanpa memanggil salah satu dan karenanya lebih efisien.
sumber
Berikut ini adalah solusi berbasis DP untuk masalah Edit Distance yang top-down. Saya harap ini juga akan membantu dalam memahami dunia Programming Dinamis:
Anda dapat memikirkan penerapannya secara rekursif di rumah Anda. Ini cukup bagus dan menantang jika Anda belum menyelesaikan sesuatu seperti ini sebelumnya.
sumber
Top-Down : Melacak nilai yang dihitung sampai sekarang dan mengembalikan hasilnya ketika kondisi dasar terpenuhi.
Bottom-Up : Hasil saat ini tergantung pada hasil dari sub-masalah.
sumber