Bagaimana pemrograman dinamis berbeda dari Brute force

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 ??

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.$K_n$$\Theta(n^2)$$\gg (n-1)!$

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.

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.

$t$$t$$t+1$$t$

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.

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.

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.