Dalam tutorial ini, anda akan mempelajari apa itu pengaturcaraan dinamik. Anda juga akan mendapat perbandingan antara pengaturcaraan dinamik dan algoritma tamak untuk menyelesaikan masalah.
Pengaturcaraan Dinamik adalah teknik dalam pengaturcaraan komputer yang dapat membantu menyelesaikan masalah dengan cekap dengan masalah yang mempunyai masalah yang bertindih dan sifat substruktur yang optimum.
Masalah seperti itu melibatkan berulang kali mengira nilai sub-masalah yang sama untuk mencari penyelesaian yang optimum.
Contoh Pengaturcaraan Dinamik
Ambil kes menghasilkan urutan fibonacci.
Sekiranya urutannya adalah F (1) F (2) F (3)… F (50), ia mengikuti peraturan F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Perhatikan bagaimana terdapat sub-masalah yang bertindih, kita perlu mengira F (48) untuk mengira kedua F (50) dan F (49). Ini betul-betul jenis algoritma di mana Pengaturcaraan Dinamik bersinar.
Bagaimana Pengaturcaraan Dinamik Berfungsi
Pengaturcaraan dinamik berfungsi dengan menyimpan hasil sub-masalah sehingga apabila penyelesaiannya diperlukan, mereka sudah siap dan kita tidak perlu menghitungnya semula.
Teknik menyimpan nilai sub-masalah ini disebut penghafalan. Dengan menyimpan nilai dalam array, kita menjimatkan masa untuk pengiraan sub-masalah yang telah kita temui.
var m = peta (0 → 0, 1 → 1) fungsi fib (n) jika kunci n tidak berada dalam peta mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Pengaturcaraan dinamik dengan memoisasi adalah pendekatan top-down untuk pengaturcaraan dinamik. Dengan membalikkan arah di mana algoritma berfungsi iaitu dengan memulakan dari casing asas dan berusaha menuju penyelesaiannya, kita juga dapat menerapkan pengaturcaraan dinamis dengan cara dari bawah ke atas.
fungsi fib (n) jika n = 0 pulangan 0 yang lain var prevFib = 0, currFib = 1 ulangan n - 1 kali var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Pengulangan vs Pengaturcaraan Dinamik
Pengaturcaraan dinamik kebanyakannya digunakan untuk algoritma rekursif. Ini bukan kebetulan, kebanyakan masalah pengoptimuman memerlukan pengulangan dan pengaturcaraan dinamik digunakan untuk pengoptimuman.
Tetapi tidak semua masalah yang menggunakan rekursi dapat menggunakan Pengaturcaraan Dinamik. Kecuali terdapat kehadiran masalah yang tumpang tindih seperti dalam masalah urutan fibonacci, pengulangan hanya dapat mencapai penyelesaian dengan menggunakan pendekatan divide and winer.
Itulah sebabnya mengapa algoritma rekursif seperti Merge Sort tidak dapat menggunakan Pengaturcaraan Dinamik, kerana sub-masalahnya tidak tumpang tindih dengan cara apa pun.
Algoritma tamak vs Pengaturcaraan Dinamik
Algoritma tamak serupa dengan pengaturcaraan dinamik dalam arti bahawa kedua-duanya merupakan alat untuk pengoptimuman.
Walau bagaimanapun, algoritma tamak mencari penyelesaian optimum tempatan atau dengan kata lain, pilihan tamak, dengan harapan dapat mencari optimum global. Oleh itu algoritma tamak dapat membuat tekaan yang kelihatan optimum pada masa itu tetapi menjadi mahal dan tidak menjamin optimum global.
Sebaliknya, pengaturcaraan dinamik mencari penyelesaian yang optimum untuk sub-masalah dan kemudian membuat pilihan yang tepat untuk menggabungkan hasil sub-masalah tersebut untuk mencari penyelesaian yang paling optimum.
