Perbedaan antara Divide and Conquer Algo dan Dynamic Programming

Apa perbedaan antara Algoritma Divide dan Conquer dan Algoritma Pemrograman Dinamis? Bagaimana kedua istilah itu berbeda? Saya tidak mengerti perbedaan di antara mereka.

Silakan ambil contoh sederhana untuk menjelaskan perbedaan antara keduanya dan atas dasar apa mereka tampak serupa.

Memecah dan menaklukkan

Divide and Conquer berfungsi dengan membagi masalah menjadi sub-masalah, menaklukkan setiap sub-masalah secara rekursif dan menggabungkan solusi ini.

Pemrograman Dinamis

Pemrograman Dinamis adalah teknik untuk memecahkan masalah dengan subproblem yang tumpang tindih. Setiap sub-masalah diselesaikan hanya sekali dan hasil dari masing-masing sub-masalah disimpan dalam sebuah tabel (umumnya diimplementasikan sebagai array atau tabel hash) untuk referensi di masa mendatang. Sub-solusi ini dapat digunakan untuk mendapatkan solusi asli dan teknik penyimpanan solusi sub-masalah dikenal sebagai memoisasi.

Anda mungkin memikirkan DP = recursion + re-use

Contoh klasik untuk memahami perbedaannya adalah dengan melihat kedua pendekatan ini untuk mendapatkan nomor fibonacci ke-n. Periksa bahan ini dari MIT.

Pendekatan membagi dan menaklukkan

Pendekatan Pemrograman Dinamis

Perbedaan lain antara divide dan conquer dan pemrograman dinamis adalah:

Memecah dan menaklukkan:

1. Apakah lebih banyak bekerja pada sub-masalah dan karenanya memiliki lebih banyak waktu konsumsi.
2. Dalam membagi dan menaklukkan sub-masalah independen satu sama lain.

Pemrograman dinamis:

1. Memecahkan sub-masalah hanya sekali dan kemudian menyimpannya di tabel.
2. Dalam pemrograman dinamis, sub-masalah tidak independen.

kadang-kadang ketika pemrograman berulang, Anda memanggil fungsi dengan parameter yang sama beberapa kali yang tidak diperlukan.

Contoh terkenal angka Fibonacci:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

Mari kita jalankan F (5):

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

Jadi kita telah memanggil: 1 kali F (4) 2 kali F (3) 3 kali F (2) 2 kali F (1)

Pendekatan Pemrograman Dinamis: jika Anda memanggil suatu fungsi dengan parameter yang sama lebih dari satu kali, simpan hasilnya ke dalam variabel untuk langsung mengaksesnya di lain waktu. Cara berulang:

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

Mari kita panggil F (5) lagi:

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

Seperti yang Anda lihat, kapan pun Anda membutuhkan panggilan ganda, Anda cukup mengakses variabel yang sesuai untuk mendapatkan nilai alih-alih menghitung ulang.

Omong-omong, pemrograman dinamis tidak berarti mengubah kode rekursif menjadi kode berulang. Anda juga dapat menyimpan subresult ke dalam variabel jika Anda menginginkan kode rekursif. Dalam hal ini teknik ini disebut memoisasi. Sebagai contoh kita terlihat seperti ini:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

Jadi hubungannya dengan Divide and Conquer adalah algoritma D&D mengandalkan rekursi. Dan beberapa versi dari mereka memiliki "panggilan fungsi ganda dengan masalah parameter yang sama." Cari "perkalian rantai matriks" dan "urutan umum terpanjang" untuk contoh-contoh semacam itu di mana DP diperlukan untuk meningkatkan T (n) dari D&D juga.

Pemrograman Dinamis dan Kesamaan Divide-and-Conquer

Seperti yang saya lihat sekarang, saya dapat mengatakan bahwa pemrograman dinamis adalah perpanjangan dari paradigma divide and conquer .

Saya tidak akan memperlakukan mereka sebagai sesuatu yang sama sekali berbeda. Karena keduanya bekerja dengan secara rekursif memecah masalah menjadi dua atau lebih sub-masalah dari jenis yang sama atau terkait, sampai ini menjadi cukup sederhana untuk diselesaikan secara langsung. Solusi untuk sub-masalah kemudian digabungkan untuk memberikan solusi untuk masalah asli.

Jadi mengapa kita masih memiliki nama paradigma yang berbeda dan mengapa saya menyebut pemrograman dinamis sebagai ekstensi. Itu karena pendekatan pemrograman dinamis dapat diterapkan pada masalah hanya jika masalah memiliki batasan atau prasyarat tertentu . Dan setelah itu pemrograman dinamis memperluas pendekatan divide and conquer dengan teknik memoisasi atau tabulasi .

Ayo selangkah demi selangkah ...

Prasyarat / Pembatasan Pemrograman Dinamis

Seperti yang baru saja kita temukan ada dua atribut kunci yang harus dimiliki untuk mengatasi dan menaklukkan agar pemrograman dinamis dapat diterapkan:

• Substruktur  optimal - solusi optimal dapat dibangun dari solusi optimal subproblemnya

• Sub-masalah yang tumpang tindih  - masalah dapat dipecah menjadi subproblem yang digunakan kembali beberapa kali atau algoritma rekursif untuk masalah memecahkan subproblem yang sama berulang-ulang daripada selalu menghasilkan subproblem baru

Setelah kedua kondisi ini terpenuhi, kita dapat mengatakan bahwa masalah pembagian dan penaklukan ini dapat diselesaikan dengan menggunakan pendekatan pemrograman dinamis.

Ekstensi Pemrograman Dinamis untuk Divide dan Conquer

Pendekatan pemrograman dinamis memperluas pendekatan membagi dan menaklukkan dengan dua teknik ( memoisasi dan tabulasi ) yang keduanya memiliki tujuan untuk menyimpan dan menggunakan kembali solusi sub-masalah yang secara drastis dapat meningkatkan kinerja. Misalnya implementasi rekursif naif dari fungsi Fibonacci memiliki kompleksitas waktu di O(2^n)mana solusi DP melakukan hal yang sama dengan O(n)waktu saja .

Memoisasi (pengisian cache top-down) mengacu pada teknik caching dan menggunakan kembali hasil yang dihitung sebelumnya. Fungsi memoized fibakan terlihat seperti ini:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)

        mem[n] = result
    return mem[n]
}

Tabulasi (pengisian cache dari bawah ke atas) serupa tetapi berfokus pada pengisian entri cache. Komputasi nilai dalam cache paling mudah dilakukan secara iteratif. Versi tabulasi fibakan terlihat seperti ini:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

Anda dapat membaca lebih lanjut tentang perbandingan memoisasi dan tabulasi di sini .

Gagasan utama yang harus Anda pahami di sini adalah bahwa karena masalah pembagian dan penaklukan kami memiliki sub-masalah yang tumpang tindih, maka caching solusi sub-masalah menjadi mungkin dan dengan demikian memoisasi / tabulasi melangkah ke tempat kejadian.

Jadi Apa Perbedaan Antara DP dan DC?

Karena kita sekarang akrab dengan prasyarat DP dan metodologinya, kami siap untuk memasukkan semua yang disebutkan di atas ke dalam satu gambar.

Jika Anda ingin melihat contoh kode, Anda dapat melihat penjelasan yang lebih terperinci di sini di mana Anda akan menemukan dua contoh algoritma: Pencarian Biner dan Edit Jarak Minimum (Jarak Levenshtein) yang menggambarkan perbedaan antara DP dan DC.

Saya berasumsi Anda sudah membaca Wikipedia dan sumber akademis lain tentang ini, jadi saya tidak akan mendaur ulang informasi itu. Saya juga harus menyatakan bahwa saya bukan ahli ilmu komputer dengan cara apa pun, tetapi saya akan membagikan dua sen saya pada pemahaman saya tentang topik-topik ini ...

Pemrograman Dinamis

Memecah masalah menjadi subproblem diskrit. Algoritma rekursif untuk urutan Fibonacci adalah contoh dari Pemrograman Dinamis, karena ia memecahkan untuk fib (n) dengan pemecahan pertama untuk fib (n-1). Untuk menyelesaikan masalah aslinya, ini memecahkan masalah yang berbeda .

Memecah dan menaklukkan

Algoritma ini biasanya memecahkan bagian masalah yang serupa, dan kemudian menyatukannya di akhir. Mergesort adalah contoh klasik dari memecah belah dan menaklukkan. Perbedaan utama antara contoh ini dan contoh Fibonacci adalah bahwa dalam penggabungan, divisi dapat (secara teoritis) berubah-ubah, dan tidak peduli bagaimana Anda mengirisnya, Anda masih menggabungkan dan menyortir. Jumlah yang sama pekerjaan yang harus dilakukan untuk menggabungkan array, tidak peduli bagaimana Anda membaginya. Memecahkan untuk fib (52) membutuhkan lebih banyak langkah daripada menyelesaikan untuk fib (2).

Saya anggap Divide & Conquersebagai pendekatan rekursif danDynamic Programming mengisi tabel.

Sebagai contoh, Merge Sortadalah Divide & Conqueralgoritma, seperti pada setiap langkah, Anda membagi array menjadi dua bagian, panggilan rekursifMerge Sort dan kemudian menggabungkannya.

Knapsackadalah Dynamic Programmingalgoritme saat Anda mengisi tabel yang mewakili solusi optimal untuk sub-masalah dari keseluruhan ransel. Setiap entri dalam tabel sesuai dengan nilai maksimum yang dapat Anda bawa dalam tas berat dengan item 1-j.

Divide and Conquer melibatkan tiga langkah di setiap tingkat rekursi:

1. Membagi masalah menjadi submasalah.
2. Taklukkan subproblem dengan menyelesaikannya secara rekursif.
3. Gabungkan solusi untuk subproblem ke dalam solusi untuk masalah asli.
   
   • Ini adalah pendekatan top-down .
     
   • Itu lebih banyak bekerja pada submasalah dan karenanya memiliki lebih banyak waktu konsumsi.
   • misalnya. Jangka waktu ke-n dari seri Fibonacci dapat dihitung dalam kompleksitas waktu O (2 ^ n).
     
     

Pemrograman Dinamis melibatkan empat langkah berikut:

1. Mengkarakterisasi struktur solusi optimal.
2. Secara rekursif menentukan nilai-nilai solusi optimal.
3. Hitung nilai solusi optimal.
4. Bangun Solusi Optimal dari informasi yang dihitung .

• Ini adalah pendekatan dari bawah ke atas .
• Konsumsi waktu lebih sedikit daripada divide dan conquer karena kita menggunakan nilai-nilai yang dihitung sebelumnya, daripada menghitung lagi.
• misalnya. Jangka waktu ke-n dari seri Fibonacci dapat dihitung dalam kompleksitas waktu O (n).
  
  

Untuk pemahaman yang lebih mudah, mari kita lihat membagi dan menaklukkan sebagai solusi brute force dan optimalisasi sebagai pemrograman dinamis. Algoritma membagi dan menaklukkan

NB dengan subproblem yang tumpang tindih hanya dapat dioptimalkan dengan dp.

• Memecah dan menaklukkan
  • Mereka masuk ke dalam sub-masalah yang tidak tumpang tindih
  • Contoh: bilangan faktorial yaitu fakta (n) = n * fakta (n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

Seperti yang dapat kita lihat di atas, tidak ada fakta (x) yang diulang sehingga faktorial memiliki masalah yang tidak tumpang tindih.

• Pemrograman Dinamis
  • Mereka pecah menjadi sub-masalah yang tumpang tindih
  • Contoh: Angka-angka Fibonacci yaitu fib (n) = fib (n-1) + fib (n-2)

fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))

Seperti yang bisa kita lihat di atas, fib (4) dan fib (3) keduanya menggunakan fib (2). begitu pula banyak fib (x) yang diulang. itu sebabnya Fibonacci memiliki sub-masalah yang tumpang tindih.

• Sebagai hasil dari pengulangan sub-masalah dalam DP, kami dapat menyimpan hasil tersebut dalam tabel dan menyimpan upaya perhitungan. ini disebut memoisasi