Saya akan mengatakan pemrograman dinamis adalah pemrograman dinamis. Itu konsep yang terpisah dari algoritma. Jika Anda akan bertanya "aplikasi algoritmik pemrograman dinamis", itu akan lebih masuk akal bagi saya.
Yoshio Okamoto
1
Tentu saja dp adalah dp, tetapi pemrograman dan dinamis keduanya berarti sesuatu yang berbeda hari ini, jadi ketika saya mengajar pemrograman dinamis, saya berharap itu memiliki nama yang berbeda.
Jack
4
Maaf, saya tidak cukup jelas. Apakah Anda tertarik pada pemrograman dinamis secara umum, termasuk penggunaan kontrol dan perencanaan kebijakan, dll., Dan bahkan pemrograman dinamis stokastik, atau hanya dalam pemrograman dinamis sebagai metode untuk desain algoritma? Audiens utama di sini hanya akan mengetahui yang terakhir, tetapi pertanyaan Anda cukup umum yang akan mencakup yang pertama.
Yoshio Okamoto
1
Yoshio, saya pikir Anda harus menjelaskan konsep yang lebih umum tentang perbedaan dalam sebuah jawaban karena itu dapat menerangi banyak dari kita.
Raphael
2
Gagasan lain yang tidak sepenuhnya menjebak: "hal yang memberi Anda pekerjaan di Google" - berdasarkan pengalaman yang dimiliki siswa saya :)
Suresh Venkat
Jawaban:
50
Otobiografi Richard Bellman menunjukkan bahwa ia memilih istilah "pemrograman dinamis" untuk sengaja dikacaukan.
Tahun 1950 bukanlah tahun yang baik untuk penelitian matematika. Kami memiliki seorang pria yang sangat menarik di Washington bernama Wilson. Dia adalah sekretaris Pertahanan, dan dia benar-benar memiliki ketakutan dan kebencian patologis terhadap kata 'penelitian'. Saya tidak menggunakan istilah ini dengan ringan; Saya menggunakannya dengan tepat. Wajahnya akan suffuse, dia akan memerah, dan dia akan menjadi kejam jika orang menggunakan istilah 'penelitian' di hadapannya. Anda dapat membayangkan bagaimana perasaannya, kemudian, tentang istilah 'matematika'. RAND Corporation dipekerjakan oleh Angkatan Udara, dan Angkatan Udara memiliki Wilson sebagai bosnya, pada dasarnya. Oleh karena itu, saya merasa harus melakukan sesuatu untuk melindungi Wilson dan Angkatan Udara dari kenyataan bahwa saya benar-benar mengerjakan matematika di dalam RAND Corporation.
Judul apa, nama apa, yang bisa saya pilih? Pertama-tama saya tertarik dalam perencanaan, pengambilan keputusan, dan pemikiran. Namun perencanaan, bukan kata yang baik karena berbagai alasan. Karena itu saya memutuskan untuk menggunakan kata 'pemrograman'. Saya ingin menyampaikan gagasan bahwa ini dinamis, ini multistage, ini beragam waktu — saya pikir, mari kita bunuh dua burung dengan satu batu. Mari kita ambil sebuah kata yang memiliki makna yang sangat tepat, yaitu 'dinamis', dalam pengertian fisik klasik. Ia juga memiliki sifat yang sangat menarik sebagai kata sifat, dan tidak mungkin menggunakan kata 'dinamis' dalam arti merendahkan. Coba pikirkan beberapa kombinasi yang mungkin akan memberinya makna merendahkan. Tidak mungkin. Jadi, saya pikir "pemrograman dinamis" adalah nama yang bagus. Itu adalah sesuatu yang bahkan tidak bisa ditolak oleh anggota Kongres.
(Seperti yang ditunjukkan Russell dan Norvig dalam buku teks AI mereka, cerita ini harus menjadi hiasan kreatif dari kebenaran. Bellman pertama kali menggunakan frasa "pemrograman dinamis" pada tahun 1952 , dan Charles Erwin Wilson tidak menjadi Sekretaris Pertahanan sampai tahun 1953. )
Bagaimanapun, motivasi asli Bellman menyarankan perencanaan multistage , tetapi setidaknya untuk tujuan algoritmik, saya lebih suka sesuatu seperti rekursi bottom-up yang hemat , hanya dengan suku kata yang lebih sedikit.
Tentu saja, apa yang benar - benar ingin saya lakukan adalah mengganti nama "Persamaan Bellman", atau seperti yang disebut para ilmuwan komputer, "perulangan apa pun".
Ada dua aspek penting dari DP: (1) mendefinisikan subproblem (yaitu, menyiapkan "tabel", yang bisa berupa array multidimensi yang mungkin diindeks oleh bilangan bulat, simpul, subset simpul dll.) Dan (2) memecahkan secara rekursif submasalah. Saya mengusulkan "rekursi tabular / tabulasi" sebagai nama yang merujuk pada kedua aspek.
Persis. Memoisasi adalah pemrograman dinamis secara tidak sengaja.
Jeffε
@professor erickson - kata sangat bagus. aku tak bisa berhenti tertawa.
Akash Kumar
7
Namun, jika kita bisa memilih nama baru untuk DP, maka menggunakan memoisasi akan cukup pas untuk itu. Misalnya "jarak edit dapat dihitung dalam waktu-poli menggunakan memoisasi".
Noam
Pemrograman dinamis adalah kasus khusus dari memoisasi, ditambah secara eksplisit mengarahkan aliran kontrol daripada mengikuti urutan evaluasi aplikatif alami. Ini memalukan itu biasanya diajarkan seperti itu, karena terlalu banyak menekankan pada mengisi tabel, bukan spesifikasi rekursif. Muncul sebagai ajaib.
Neil Toronto
8
Untuk pergi dengan memecah-dan-menaklukkan , saya akan mengatakan sambatan-dan-gabungkan.
Saya biasanya menggunakan kedua kata, sambatan dan menggabungkan saat mengajar / menjelaskan DP; tetapi tidak digunakan sambatan-dan-gabungkan secara eksplisit. Kadang-kadang saya menggunakan tumpang tindih-divide-and-conquer untuk membandingkan kedua paradigma tersebut.
Setelah kuliah terakhir saya tentang pemrograman dinamis dalam desain algoritma, saya telah meminta siswa untuk menyarankan nama baru untuk teknik ini. Sementara saya merasa geli dengan "pemrograman Tough," saya menginginkan sesuatu yang mungkin membuat teknik lebih berkesan. Setelah diskusi di sini, saya dapat mengusulkan dua nama, satu untuk top-down dan satu untuk bottom-up:
Multiway-Divide dan Memoized-Conquer (alias Divide ^ M & Conquer ^ M), dan
Gabungkan semua submasalah (alias Merge_all)
Saya tidak berpikir bahwa menciptakan hubungan yang kuat dengan membagi & menaklukkan yang biasa (seperti dalam Mergesort) adalah ide yang bagus. Di sana, submasalah diselesaikan secara independen dan hanya dua hasil yang digabungkan. Dalam DP, subproblem yang diperiksa tidak independen dan semua kombinasi diperiksa. (keduanya secara kasar). Karena itu saya pikir nama harus menyoroti perbedaan daripada menciptakan rasa kesamaan.
Raphael
@ Raphael, saya berbagi keprihatinan tentang bahaya menciptakan asosiasi yang kuat, tetapi tidak setuju dengan pernyataan Anda tentang perbedaan. Di DP sangat penting bahwa submasalah yang "diselesaikan secara independen" meskipun solusi untuk subsubproblems bersama. Saya biasanya menunjukkan bahwa jika beberapa oracle memberi tahu Anda pembagian yang tepat, itu akan memecah belah dan menaklukkan, tetapi karena saya tidak berbicara bahasa Yunani (tidak seperti penasihat PhD saya), saya harus mencoba semua divisi yang mungkin.
Jack
2
Ya, submasalah secara konseptual independen. Namun, saya berhubungan dengan mereka menggunakan hasil parsial yang sama, seperti yang Anda tunjukkan. Ini memisahkan DP dari D&C, karena dimungkinkan untuk memparalelkan yang terakhir tanpa menghitung subproblem berkali-kali (atau mengkomunikasikan hasilnya) sebagai lawan dari yang sebelumnya. Analogi Anda bagus tetapi tidak menjamin nama dalam kasus ini karena menemukan divisi yang tepat adalah bagian penting dari masalah. Saya kira Anda bisa mengatakan bahwa DP adalah generalisasi D&C berdasarkan alasan itu.
Raphael
@ Raphael, maaf karena bertele-tele, tetapi karena ini adalah pertanyaan tentang mengajar, saya ingin gagasan kemandirian sub-masalah menjadi jelas, dan hanya mengatakan "secara konseptual independen" tidak tepat. Ketika Anda mencoba suatu divisi, subproblem yang Anda hasilkan mungkin tidak memiliki dependensi. Komentar Anda yang lain fokus pada langkah-langkah algoritma DP; Saya lebih suka fokus dulu pada mendefinisikan masalah secara tepat untuk diselesaikan. Contoh favorit saya: triangulasi min berat dan dekomposisi min cembung poligon sederhana ( cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html )
Jack
Tidak apa-apa untuk menjadi pendantic. Tetapi pertimbangkan impor didaktik dari pilihan kata-kata: Anda memberi tahu para siswa bahwa subproblem adalah independen dan kemudian memberi mereka algoritma yang tidak memisahkan perhitungan mereka, tetapi pada kenyataannya sangat bergantung pada perhitungan "interleaved". Saya pikir itu bisa sangat membingungkan. Oleh karena itu, Anda benar-benar harus memisahkan konseptual / matematis / optimisasi / ... dan independensi komputasi di beberapa titik.
Raphael
4
Makalah ini ( paywalled doi ) menyebut masalah yang dapat diserang menggunakan DP "decomposable".
itu terdengar seperti sesuatu yang Anda lakukan di call center outsourcing;)
Suresh Venkat
2
Saya akan menyarankan nama Pemrograman Induktif - sebagai semacam jembatan seperti dari zaman kita ke masa-masa indah Euler, Kepler et al. Atau mungkin bahkan Pemrograman Induktif Balik . Dan ya, bagi saya DP sangat terkait dengan Induksi, dalam pengertian lama yang baik. Memoisasi, cache, tabel dll hanyalah elemen teknik, bukan inti dari pendekatan untuk memecahkan masalah.
Bah Pemrograman dinamis bukan tentang tabel ; ini tentang rekursi yang cerdas.
Jeffε
3
Saya merasa lebih baik untuk memisahkan dua aspek: "Mengekstraksi struktur rekursif dari masalah, dan menuliskannya sebagai perulangan" (pemodelan) dan "Memecahkan perulangan yang diperoleh dengan cara bottom-up" (algoritma). Saya merasa pemrograman dinamis (dalam algoritma) mengacu pada keduanya, dan ini juga merupakan kasus untuk pemrograman linier, pemrograman integer, pemrograman semidefinite, dll.
Yoshio Okamoto
1
Meja terkadang digunakan. Pemrograman dinamis di atas pohon (misalnya: himpunan independen maksimum) biasanya tidak menggunakan tabel [= array] untuk memoise pengulangan; ia menggunakan pohon, atau dalam beberapa kasus pohon array, atau susunan pohon, atau dalam beberapa kasus produk Cartesian dari pohon. Demikian pula untuk pemrograman dinamis pada dags atau pemrograman dinamis pada dekomposisi pohon untuk grafik treewidth terikat.
Jeffε
1
JeffE, nama untuk teknik hampir tidak pernah mencakup semua aplikasi. Ambil "diagonisasi", misalnya; dalam aplikasi tingkat lanjut, tidak ada diagonale di mana pun terlihat (atau setidaknya bukan area tindakan eksklusif). Tapi saya tidak terlalu suka dengan "mengisi meja", bagaimanapun, sementara saya pikir itu bisa menjadi nama yang masuk akal untuk pemula.
Raphael
3
2 sen saya pada topik ini. Pemrograman dinamis memiliki dua aspek berbeda untuk merancang algoritma. Pertama adalah memahami mekanisme dp seperti pada: rekursi pintar plus memoisasi yang mengarah ke algoritma yang lebih cepat. Aspek kedua adalah bagaimana mengenali bahwa suatu masalah dapat mengakui rekursi yang cerdas dan mengatasinya. Keduanya penting untuk diajarkan. Untuk yang terakhir, kasus umum adalah memecah dan menaklukkan dengan interaksi terbatas dan dalam pandangan saya bermanfaat untuk secara eksplisit menyoroti.
Jawaban:
Otobiografi Richard Bellman menunjukkan bahwa ia memilih istilah "pemrograman dinamis" untuk sengaja dikacaukan.
(Seperti yang ditunjukkan Russell dan Norvig dalam buku teks AI mereka, cerita ini harus menjadi hiasan kreatif dari kebenaran. Bellman pertama kali menggunakan frasa "pemrograman dinamis" pada tahun 1952 , dan Charles Erwin Wilson tidak menjadi Sekretaris Pertahanan sampai tahun 1953. )
Bagaimanapun, motivasi asli Bellman menyarankan perencanaan multistage , tetapi setidaknya untuk tujuan algoritmik, saya lebih suka sesuatu seperti rekursi bottom-up yang hemat , hanya dengan suku kata yang lebih sedikit.
sumber
Ada dua aspek penting dari DP: (1) mendefinisikan subproblem (yaitu, menyiapkan "tabel", yang bisa berupa array multidimensi yang mungkin diindeks oleh bilangan bulat, simpul, subset simpul dll.) Dan (2) memecahkan secara rekursif submasalah. Saya mengusulkan "rekursi tabular / tabulasi" sebagai nama yang merujuk pada kedua aspek.
sumber
Memoisasi adalah varian yang cukup umum.
sumber
Untuk pergi dengan memecah-dan-menaklukkan , saya akan mengatakan sambatan-dan-gabungkan.
Saya biasanya menggunakan kedua kata, sambatan dan menggabungkan saat mengajar / menjelaskan DP; tetapi tidak digunakan sambatan-dan-gabungkan secara eksplisit. Kadang-kadang saya menggunakan tumpang tindih-divide-and-conquer untuk membandingkan kedua paradigma tersebut.
sumber
Setelah kuliah terakhir saya tentang pemrograman dinamis dalam desain algoritma, saya telah meminta siswa untuk menyarankan nama baru untuk teknik ini. Sementara saya merasa geli dengan "pemrograman Tough," saya menginginkan sesuatu yang mungkin membuat teknik lebih berkesan. Setelah diskusi di sini, saya dapat mengusulkan dua nama, satu untuk top-down dan satu untuk bottom-up:
Multiway-Divide dan Memoized-Conquer (alias Divide ^ M & Conquer ^ M), dan
Gabungkan semua submasalah (alias Merge_all)
sumber
Makalah ini ( paywalled doi ) menyebut masalah yang dapat diserang menggunakan DP "decomposable".
sumber
Saya membahas hal ini dengan beberapa rekan baru-baru ini, dan setelah diskusi panas kami menemukan caching panggilan tabular .
sumber
Saya akan menyarankan nama Pemrograman Induktif - sebagai semacam jembatan seperti dari zaman kita ke masa-masa indah Euler, Kepler et al. Atau mungkin bahkan Pemrograman Induktif Balik . Dan ya, bagi saya DP sangat terkait dengan Induksi, dalam pengertian lama yang baik. Memoisasi, cache, tabel dll hanyalah elemen teknik, bukan inti dari pendekatan untuk memecahkan masalah.
sumber
Mungkin sesuatu yang memasukkan kata-kata tabel dan isi , karena inilah yang terjadi.
sumber
Tampilan rekursif atau cakrawala rekursif
sumber
Saya akan menyebutnya "Teruskan rekursi dengan memoisasi".
sumber