Dynamic Programming Bukan Sihir Hitam

Dynamic Programming bukan sihir

• Dynamic programming adalah teknik yang digunakan untuk menyelesaikan masalah kompleks dengan memecahnya menjadi masalah-masalah kecil.
• Teknik ini bersifat alami, dan banyak algoritma umum sebenarnya merupakan penerapan dynamic programming pada masalah tertentu.
• Untuk membantu memahami dynamic programming, artikel ini memberikan pengantar yang lebih mudah dan penjelasan yang rinci.

Keluhan

• Rekayasa perangkat lunak sering kali sangat buruk dalam urusan penamaan.
• Istilah seperti 'bootstrap', 'daemon', 'cascading style sheets', 'cookie', dan 'kecerdasan buatan' terdengar ambigu atau mudah menyesatkan.
• Istilah 'dynamic programming' juga sama sekali tidak berkaitan dengan sesuatu yang 'dinamis'; sebenarnya ini adalah sebuah gagasan yang digunakan dalam perancangan algoritma.

Caching dasar

• Saat mencoba menyelesaikan masalah dengan membaginya menjadi masalah-masalah kecil yang serupa, kita bisa saja harus menyelesaikan masalah kecil yang sama berulang kali.
• Dengan contoh deret Fibonacci, jika diimplementasikan sebagai fungsi rekursif sederhana, perhitungan yang sama akan diulang berkali-kali.
• Hasilnya dapat di-cache (atau dimemoisasi) untuk menghindari perhitungan duplikat.

Caching yang dioptimalkan

• Dengan memoization, kita tetap mempertahankan rekursi, tetapi menghitung hanya hal yang diperlukan saat dibutuhkan.
• Sebagai gantinya, kita bisa menggunakan pendekatan yang menghitung semua hal yang diperlukan terlebih dahulu.
• Pendekatan ini menyelesaikan masalah tanpa pemanggilan rekursif, dan inilah yang disebut dynamic programming.

Jarak edit

• Jarak edit antara dua string adalah jumlah minimum penyuntingan yang diperlukan untuk mengubah satu string menjadi string lainnya.
• Jarak edit dapat dihitung dengan memasukkan penggantian, penyisipan, dan penghapusan karakter, dan ini bisa diselesaikan secara efisien menggunakan dynamic programming.
• Kita perlu menemukan cara untuk menurunkan solusi keseluruhan dari solusi masalah-masalah kecil.

Advent of Code, Day 12

• Dalam soal Advent of Code tanggal 12 Desember 2023, kita harus menyelesaikan nonogram 1D.
• Masalah ini bisa diselesaikan dengan brute force, tetapi memiliki kompleksitas eksponensial.
• Sebagai gantinya, dynamic programming dapat diterapkan untuk menyelesaikannya secara efisien.

Kesimpulan

• Dynamic programming memang tidak mudah, tetapi bukan sesuatu yang mustahil dijangkau oleh sebagian besar programmer.
• Jika memahami cara memecah masalah menjadi masalah-masalah kecil, kita bisa menggunakan memoization dalam berbagai situasi, dan ini merupakan peningkatan besar dibanding implementasi yang naif.
• Dengan menguasai dynamic programming, kita dapat memahami satu kelas algoritma secara utuh, lebih memahami trade-off, dan membuka kemungkinan optimasi lainnya.

Opini GN⁺

• Dynamic programming adalah teknik penting untuk menyelesaikan masalah kompleks secara efisien; alih-alih mengandalkan pendekatan rekursif murni, teknik ini dapat sangat meningkatkan performa dengan menyimpan solusi masalah kecil untuk mengurangi perhitungan berulang.
• Artikel ini sangat bermanfaat bagi software engineer pemula yang ingin memahami konsep dasar dynamic programming.
• Contoh deret Fibonacci dan jarak edit membantu memahami konsep dynamic programming, serta memberikan titik awal yang baik untuk menerapkannya pada pemecahan masalah nyata.

[GN⁺]

Komentar Hacker News

• Artikel yang menjelaskan algoritme dynamic programming (DP) sebagai caching pada rekursi adalah hal yang bagus.

  • Menemukan solusi rekursif adalah titik awal terbaik untuk menemukan solusi DP.
  • Melakukan memoization pada solusi rekursif dapat sangat membantu meningkatkan kecepatan.
  • Yang penting bukanlah ada banyak submasalah dalam pohon pemanggilan, melainkan harus ada jumlah submasalah unik yang relatif sedikit.

• Menyukai pendekatan artikel yang pertama-tama menangani masalah secara rekursif, lalu secara bertahap menambahkan caching, kemudian menguranginya hingga sebesar ukuran cache yang benar-benar diperlukan.

  • Pernah mengalami kebuntuan atau perlu usaha besar saat mencoba langsung menemukan solusi dynamic programming.
  • Ke depannya akan memaksa diri untuk mengikuti pendekatan berurutan seperti itu.

• Salah satu penerapan dynamic programming yang keren adalah penyelarasan berpasangan untuk urutan asam nukleat/protein.

  • Misalnya, sequence alignment, algoritme Needleman–Wunsch, dan algoritme Smith–Waterman.

• Membagikan pengalaman tentang seorang profesor algoritme yang sangat luar biasa.

  • Profesor itu belajar di UCLA, dan kuliahnya tentang dynamic programming sangat istimewa.
  • Ia memulai dari masalah sederhana tetapi berkompleksitas eksponensial, lalu memecah masalah menjadi masalah-masalah kecil dan menurunkan kompleksitasnya menjadi polinomial, kemudian menerapkan memoization hingga turun ke kompleksitas linear.
  • Ingin mengingat masalah-masalah yang digunakan saat itu.

• Membagikan tautan ke tulisan berjudul Dynamic Programming is not Black Magic.

  • Tulisan tersebut sulit diakses karena terlalu banyak trafik (hug of death).

• Seseorang yang sebagian besar belajar pemrograman secara otodidak mengatakan bahwa jika saat mencari kerja ia diminta menggunakan dynamic programming dalam wawancara, kemungkinan ia tidak akan tahu.

  • Untungnya itu tidak terjadi, dan karena mengetahui teknik tersebut, ia memakainya di beberapa wawancara.

• Nama "dynamic programming" mungkin tidak terlihat seperti berasal dari bidang pemrograman.

  • Sebenarnya ini terkait optimisasi dan merupakan metode untuk menyelesaikan masalah keputusan pada waktu diskret.
  • Dynamic programming adalah metode yang sangat mengurangi dimensi masalah optimisasi dengan mendefinisikan fungsi nilai V*.

• Mengajukan pertanyaan apakah salah jika ketika mendengar "dynamic programming" yang terpikir hanya "memoization".

  • Bagian yang mungkin terlewat adalah membagi masalah dengan cerdas agar memoization bisa digunakan secara efektif.

• Dynamic programming bukan black magic, tetapi yang sulit adalah membuktikan bahwa sesuatu memang bisa diprogram secara dinamis dan membuktikan kebenarannya.

  • Seperti algoritme greedy, dibutuhkan pembuktian formal menggunakan induksi matematika.

• Untuk menguasai dynamic programming, merekomendasikan buku algoritme DPV dan kuliah Udacity dari Georgia Tech.

  • Dynamic programming bisa dipelajari dengan berlatih menyelesaikan soal-soal.