Bagaimana pemrograman dinamis berbeda dari Brute force

19

Saya membaca tentang Pemrograman Dinamis ketika saya menemukan kutipan berikut

Algoritma pemrograman dinamis akan memeriksa semua cara yang mungkin untuk menyelesaikan masalah dan akan memilih solusi terbaik. Oleh karena itu, kita dapat secara kasar menganggap pemrograman dinamis sebagai metode yang cerdas dan kasar yang memungkinkan kita untuk melalui semua solusi yang memungkinkan untuk memilih yang terbaik . Jika ruang lingkup masalahnya sedemikian rupa sehingga melalui semua solusi yang mungkin adalah mungkin dan cukup cepat, pemrograman dinamis menjamin menemukan solusi optimal

Contoh berikut diberikan

Misalnya, katakanlah Anda harus pergi dari titik A ke titik B secepat mungkin, di kota tertentu, selama jam sibuk. Algoritma pemrograman dinamis akan melihat ke seluruh laporan lalu lintas, melihat ke semua kombinasi jalan yang mungkin Anda ambil, dan hanya akan memberi tahu Anda jalan mana yang paling cepat. Tentu saja, Anda mungkin harus menunggu beberapa saat hingga algoritma selesai, dan baru setelah itu Anda dapat mulai mengemudi. Jalur yang akan Anda ambil akan menjadi yang tercepat (dengan asumsi bahwa tidak ada yang berubah di lingkungan eksternal)

Brute Force sedang mencoba setiap solusi yang mungkin sebelum memutuskan solusi terbaik.

Bagaimana Pemrograman Dinamis berbeda dari Brute Force jika juga melewati semua solusi yang mungkin sebelum memilih yang terbaik , satu -satunya perbedaan yang saya lihat adalah Pemrograman Dinamis memperhitungkan faktor-faktor tambahan (kondisi lalu lintas dalam kasus ini).

Apakah saya benar mengatakan bahwa Pemrograman Dinamis adalah bagian dari metode Brute Force ??

Kutu buku komputer
sumber
1
Kondisi lalu lintas adalah herring merah. Anda dapat mempertimbangkannya dalam algoritma apa pun.
Yuval Filmus
Jawaban terkait .
Raphael
Kutipan pertama Anda tidak mendefinisikan pemrograman dinamis.
reinierpost
@reinierpost Yah, ia mencoba untuk sampai ke sana intelligent, brute force, tetapi kemudian lupa untuk menggambarkan bagian "cerdas"
Izkata
@Izkata Dengan alasan itu, setiap algoritma adalah "kekuatan kasar yang cerdas" (yang merupakan sebuah oxymoron, toh).
Raphael

Jawaban:

17

Algoritma pemrograman dinamis akan memeriksa semua cara yang mungkin untuk menyelesaikan masalah dan akan memilih solusi terbaik.

Pernyataan ini benar-benar salah.

Perulangan pemrograman dinamis melakukan (sering) mempertimbangkan semua cara yang mungkin untuk membagi contoh masalah yang diberikan menjadi contoh yang lebih kecil menurut beberapa skema. Namun, itu tidak akan menggabungkan semua solusi untuk semua masalah parsial satu sama lain dan memilih yang terbaik - hanya menggabungkan solusi parsial yang optimal (dan mengambil yang terbaik dari semua itu).

Fakta bahwa ini menghasilkan solusi optimal untuk masalah asli tidak sepele dan, pada kenyataannya, hanya berlaku untuk beberapa masalah. Yaitu yang memenuhi prinsip optimalitas Bellman (salah satu "definisi" paling mencurigakan yang disalahpahami yang secara teratur dikutip). Lihat di sini untuk beberapa pemikiran tentang itu.

Sebagai contoh konkret, mempertimbangkan algoritma Bellman-Ford pada graf lengkap dengan satuan bobot: itu hanya pernah menganggap jalan panjang satu dan dua (yaitu Θ ( n 2 ) banyak) karena mereka menggunakan salah satu ujung semua optimal . Tetapi ada banyak solusi tak terhingga jika Anda tidak mengikat jumlah tepi maksimum yang diizinkan, dan masih ( n - 1 ) ! banyak jika Anda mengizinkan setiap simpul hanya digunakan satu kali. Jadi jelas, Bellman-Ford - algoritma pemrograman dinamis - tidak melakukan pencarian kasar.KnΘ(n2)(n-1)!

Raphael
sumber
"Pernyataan ini benar-benar salah" - Perbaiki .
nmclean
4
@nmclean Pengalaman saya dengan mengedit artikel terkait algoritma di Wikipedia kurang menyenangkan, jadi tidak. Saya lebih suka menginvestasikan waktu saya di sini.
Raphael
Saya mencoba keberuntungan saya dan mengedit artikel itu. Berharap itu agak salah sekarang.
C4stor
9

Pemrograman Dinamis pintar karena menggunakan kembali komputasi, sementara brute force tidak. Misalkan untuk menyelesaikan, f (6), Anda harus menyelesaikan 2 sub-masalah yang keduanya disebut f (3). Metode brute force akan menghitung f (3) dua kali sehingga membuang-buang upaya sementara pemrograman dinamis akan memanggilnya sekali, simpan hasilnya jika perhitungan di masa depan perlu menggunakannya. Dalam banyak masalah, dinamis meningkatkan kompleksitas eksponensial dari brute force ke kompleksitas polinomial.

Tushar
sumber
9
Itu memoisasi , yang hanya salah satu dari banyak trik yang digunakan DP.
Ben Voigt
4
Kekuatan kasar dengan memoisasi masih belum efisien; hanya struktur / pemangkasan tambahan yang disediakan oleh pengulangan DP yang membuat memoisasi terbayar.
Raphael
3
Saya tidak tahu apa-apa tentang pemrograman dinamis, tapi saya cukup yakin ada lebih dari itu daripada hanya menambahkan cache ke algoritma brute-force. Saya pikir pemrograman dinamis menghindari pengujian setiap kombinasi yang mungkin dengan membagi ruang masalah, menemukan solusi optimal untuk setiap subdivisi kecil, dan kemudian menggabungkan mereka untuk membuat solusi terbaik secara keseluruhan. (Ini mungkin melakukan ini secara rekursif, sub-menyelam sub-divisi.) Ini hanya berfungsi jika Anda dapat mengungkapkan masalah dengan cara yang memungkinkan untuk kombinasi solusi seperti ini dan masih mendapatkan keseluruhan optimal.
Jonathan Hartley
1
Jawaban ini sebenarnya cukup akurat. Saya menyarankan untuk membaca buku teks seperti Cormen et al: "Pengantar Algoritma" untuk mempelajari lebih lanjut tentang pemrograman dinamis, buku ini memiliki bab yang cukup baik. Singkatnya, pemrograman dinamis yang efisien memanfaatkan dua sifat masalah (pengoptimalan) yang ingin Anda selesaikan: solusi optimal dapat dibangun dari solusi optimal sub-masalah yang lebih kecil, dan jumlah total sub-masalah yang lebih kecil sebenarnya agak kecil. Kemudian, Anda dapat membangun semua solusi sub-masalah dari bawah ke atas, mempercepat perhitungan dengan biaya memori.
MRA
Atau, untuk membuatnya lebih sederhana: Jika Anda tahu bagaimana menghitung koefisien binomial menggunakan segitiga Pascal maka Anda tahu semua yang perlu Anda ketahui tentang pemrograman dinamis.
MRA
3

Perbedaan yang mungkin dibuat oleh artikel Wikipedia adalah antara tiga jenis algoritma:

  1. Algoritma yang membahas semua solusi yang mungkin, memilih yang optimal.

  2. Algoritma yang membahas subset dari semua solusi yang mungkin, dipilih sehingga solusi optimal milik subset tersebut.

  3. Algoritma yang masuk ke subset dari semua solusi yang mungkin, tanpa jaminan bahwa solusi optimal milik subset.

Dua jenis algoritma pertama menghasilkan solusi optimal, sedangkan tipe ketiga bertujuan untuk menghasilkan solusi "baik" daripada solusi optimal. Menurut pendapat saya, perbedaan antara dua jenis pertama tidak begitu jelas.

Mari saya mulai dengan memberikan contoh sederhana untuk ketiga jenis algoritma, dalam konteks jalur terpendek (contoh yang Anda berikan).

  1. Coba semua jalur yang memungkinkan. Ini dikenal sebagai brute force .

  2. Coba semua jalur yang mungkin, lacak solusi minimum sejauh ini. Kapan pun jalur yang Anda buat saat ini lebih mahal daripada solusi minimum sejauh ini, abaikan saja dan pilih yang lain (kami membayangkan bahwa jarak dihitung berdasarkan segmen-per-segmen). Ini disebut pemangkasan .

  3. Lihatlah peta, pertimbangkan beberapa jalur, dan pilih yang terbaik di antara mereka. Ini adalah algoritma untuk manusia daripada komputer.

Contoh-contoh ini agak kasar, dan mungkin tidak melukiskan gambaran yang sangat akurat. Pemangkasan sangat penting dalam banyak situasi, misalnya dalam catur komputer. Jika Anda penasaran, lihat algoritma A * , yang sebenarnya digunakan untuk jalur terpendek.

Pemrograman dinamis adalah teknik untuk mempercepat secara signifikan algoritma brute force. Namun, agak menyesatkan untuk memikirkannya dengan cara ini. Ini adalah teknik algoritmik untuk menyelesaikan masalah optimisasi. Anda dapat menerapkan pemangkasan dalam konteks pemrograman dinamis.

ttt+1t

Yuval Filmus
sumber
Dan kemudian ada menghapus kandidat dari pertimbangan tanpa sepenuhnya memprosesnya. Misalnya, menemukan set angka non-negatif dengan jumlah minimum, Anda tidak benar-benar harus menjumlahkan setiap set sepenuhnya, hanya pergi sampai jumlah melebihi yang terbaik saat ini. Ini adalah ide yang mirip dengan pemangkasan tetapi ortogonal. Menggabungkan dua ide menghasilkan "cabang-dan-terikat", di mana masalah pengurangan kompleksitas dipecahkan dan digunakan untuk membenarkan pemangkasan.
Ben Voigt
0

Pemrograman dinamis jauh lebih cepat daripada brute force. Brute force mungkin membutuhkan waktu yang eksponensial, sedangkan pemrograman dinamis biasanya jauh lebih cepat.

Analogi dengan kekuatan kasar sangat longgar. Pemrograman dinamis bukanlah peluru perak ajaib yang memungkinkan Anda mengambil algoritma brute force apa pun yang Anda inginkan dan membuatnya efisien.

DW
sumber
5
Itu konsekuensi, bukan penjelasan.
Raphael
-2

Ini mudah. Pemrograman dinamis adalah "strategi pencarian" yang menggunakan faktor-faktor tambahan untuk mempersempit pencarian. Jika tidak ada solusi di ruang pencarian, pemrograman dinamis akan (biasanya) melakukan pencarian melalui setiap elemen ruang pencarian. Tapi itu tidak berarti bahwa itu adalah pencarian brute force.

nomen
sumber
"Jika tidak ada solusi di ruang pencarian, pemrograman dinamis akan (biasanya) melakukan pencarian melalui setiap elemen ruang pencarian." - salah, lihat jawaban saya.
Raphael
-2

Pernyataan bahwa pemrograman dinamis adalah kekuatan kasar yang cerdas adalah benar, tetapi agak sulit untuk dipahami dengan ungkapan itu. Inti dari pemrograman dinamis umumnya untuk mengambil masalah dan memecahnya menjadi potongan-potongan kecil dengan cara yang cerdas. Setelah Anda selesai melakukannya, Anda akan menggunakan brute force untuk menyelesaikan setiap potongan kecil, dan kemudian Anda akan menggunakan brute force lagi untuk menggabungkan potongan menjadi solusi akhir. Jadi sementara Anda pasti bisa mengatakan bahwa pemrograman dinamis adalah jenis solusi brute force, triknya terletak pada bagaimana Anda menggunakan brute force itu.

Tal
sumber
1
"Anda akan menggunakan kekuatan kasar untuk menyelesaikan setiap bagian kecil" - salah. Anda biasanya akan menggunakan pendekatan yang sama secara rekursif.
FrankW