Awal Perjumpaan
Malam hari saat pertama kali ikut OSN 2009, saya membaca buku TOKI News. Ada beberapa pembahasan soal di sana, dan sepertinya cocok untuk memanaskan diri sebelum kompetisi.Kemudian yang saya lihat adalah rumus ajaib yang tiba-tiba muncul setelah kata-kata "Dynamic Programming" disebut:
(kutipan sebenar-benarnya yang dipecah agar mudah dimuat di tulisan ini)
Oh astaga, lagi-lagi dynamic programming...
Akhirnya saya tidak belajar apa-apa pada malam tersebut.
Bertahun-tahun kemudian, akhirnya saya mengerti apa itu dynamic programming. Saya pun teringat dengan rumus mewah di atas. Setelah dipahami, ternyata suatu formulasi DP memang dapat dinyatakan dalam rumus mewah. Lalu saya coba-coba menuliskan rumus untuk solusi-solusi DP yang saya temui.
Sepanjang saya berkompetisi, saya tidak banyak melihat orang menuliskan rumus DP. Memang tidak semua rumus DP mudah ditulis atau dibaca, tetapi solusi dalam bentuk rumus menurut saya lebih mudah untuk dikomunikasikan. Tulisan ini akan membahas tentang membaca/menulis rumus DP.
Catatan: Anda diharapkan telah memahami apa itu DP, setidaknya untuk knapsack problem! Jika belum, harap pelajari dahulu (misalnya di kursus dasar dynamic programming dari TLX).
Mengapa Menggunakan Rumus?
Penulisan DP menggunakan rumus memberikan beberapa manfaat:- Saat menulis rumus, kita menerjemahkan pikiran yang abstrak ke bentuk tulisan yang jelas. Sehingga semua yang tadinya tidak jelas menjadi jelas. Jika tadinya ada kasus atau kejadian yang tidak terpikirkan, kini menjadi lebih mudah disadari. Hal ini mengurangi kemungkinan terjadinya "eh iya, tadi nggak kepikiran".
- Seluruh pemikiran yang kompleks itu dituangkan dalam sebuah rumus yang singkat, padat, dan jelas. Sekali melihatnya kembali, kita dapat memahami bagaimana solusi DP itu bekerja.
- Sebuah rumus yang terdefinisi jelas hanya memiliki sebuah makna. Ketidakambiguan ini membantu dalam komunikasi, misalnya jika Anda sedang mendiskusikan solusi DP dengan teman, rekan tim kompetisi, sesi pengajaran, atau bahkan tulisan blog.
Memahami Rumus
Pada dasarnya, sebuah rumus DP adalah sebuah fungsi. Fungsi sederhana yang biasa Anda lihat seperti:\(f(x) = 3x^2 - 2x + 5\)
Hal yang tidak biasa adalah rumus DP biasanya terbagi atas beberapa kasus, bergantung pada kondisi parameter yang diberikan.
Contoh 1: Fibonacci
Sebagai contoh, lihat definisi fungsi fibonacci berikut:\(\displaystyle
f(x) = \left\{
\begin{array}{ll}
1 &, x \lt 2 \\
f(x-1) + f(x-2) &, x \ge 2 \\
\end{array} \right. \)
Wew, tiba-tiba ada kurawal besar di awal dan rumusnya menjadi bertingkat.
Makna sebenarnya dari rumus tersebut sederhana, yaitu \(f(x)\) bernilai:
- 1, ketika \(x\) kurang dari 2
- \(f(x-1) + f(x-2)\), ketika \(x\) lebih dari atau sama dengan 2
Yang langsung dapat dituliskan ke bentuk kode dengan mudah:
Contoh 2: Knapsack
Untuk DP yang lebih rumit, Anda dapat menemui bahwa parameter fungsinya lebih dari 1. Misalnya untuk kasus DP knapsack, terdapat 2 parameter. Berikut rumus DP knapsack dari kursus dasar dynamic programming dari TLX:\(\displaystyle
g(i,c) = \left\{\begin{array}{lr}
0, & i = 0\\
g(i-1,c), & i > 0 \wedge c < w_i\\ \max(g(i-1,c-w_i)+v_i,g(i-1,c)), & i > 0 \wedge c \geq w_i\\
\end{array}\right.
\)
Saya tidak membahas apa itu knapsack pada tulisan ini. Sedikit konteks, berikut makna dari variabel-variabel yang digunakan:
- \(g(i, c)\): total nilai barang terbesar jika kita memilih beberapa barang dari barang ke-1 sampai dengan barang ke-\(i\) untuk dimasukkan ke tas berkapasitas \(c\).
- \(i\): indeks barang yang sedang dievaluasi.
- \(c\): kapasitas tas yang tersisa.
- \(w_i\): berat barang ke-\(i\).
- \(v_i\): nilai barang ke-\(i\).
\(f(x, y) = x^2 + 7xy + y^2\)
Kembali ke DP knapsack, makna dari rumus DP tersebut juga sedernana, yaitu \(g(i, c)\) bernilai:
- 0, ketika \(i\) bernilai 0. Artinya kalau tidak ada barang untuk dimasukkan ke dalam tas (semuanya sudah dievaluasi), maka nilai optimal adalah 0.
- \(g(i-1,c)\), ketika \(i\) bernilai lebih dari 0 dan \(c\) kurang dari \(w_i\). Artinya kalau masih ada barang untuk dievaluasi tetapi kapasitas tas kurang dari berat barang, maka nilai optimalnya sama dengan nilai optimal saat barang ini tidak dimasukkan ke dalam tas.
- \(\max(g(i-1,c-w_i)+v_i,g(i-1,c))\), ketika \(i\) bernilai lebih dari 0 dan \(c\) lebih dari atau sama dengan \(w_i\). Artinya kalau masih ada barang untuk dievaluasi dan kapasitas tas cukup untuk menampung barang tersebut, maka nilai optimalnya sama dengan salah satu nilai yang terbesar dari:
- Ambil barang, nilainya: nilai optimal untuk mengevaluasi barang selanjutnya dengan kapasitas tas berkurang sebanyak \(w_i\), yang ditambah dengan nilai barang \(v_i\).
- Tidak mengambil barang, nilainya: nilai optimal untuk mengevaluasi barang selanjutnya dengan kapasitas tas tetap.
Notasi yang Perlu Diketahui
Kini Anda telah memahami struktur rumus DP. Berikutnya mari pelajari notasi-notasi yang umum digunakan.--
Penjumlahan (sigma)
Terdapat sejumlah gaya penulisan. Misalnya penulisan untuk penjumlahan secara iteratif:\(\displaystyle
\sum_{i = a}^{b} f(i) = f(a) + f(a+1) + f(a+2) + ... + f(b)
\)
Pada contoh tersebut, \(i\) adalah iterator-nya, dimulai dari \(a\) sampai dengan \(b\). Lalu lakukan penjumlahan terhadap \(f(i)\). Untuk lebih memahaminya, perhatikan contoh berikut:
\(\displaystyle
\sum_{i = 1}^{99} i^2 = 1^2 + 2^2 + 3^2 + 4^2 + ... + 99^2
\)
\(\displaystyle
\sum_{i = 10}^{99} i^3 = 10^3 + 11^3 + 12^3 + 13^3 + ... + 99^3
\)
Memungkinkan juga bila Anda membutuhkan dua tingkat sigma:
\(\displaystyle
\sum_{i = 1}^{10} \sum_{j = i}^{10} (i + j) = (1+1) + (1+2) + ... + (1+10) + (2+2) + (2+3) + ... + (10 + 10)
\)
Cara penulisan lain adalah dengan menuliskan syarat iteratornya:
\(\displaystyle
\sum_{a \le i \le b} f(i) = f(a) + f(a+1) + f(a+2) + ... + f(b)
\)
Yang dapat dikombinasikan juga dengan iterator lainnya:
\(\displaystyle
\sum_{1 \le i \le j \le 10} (i + j) = (1+1) + (1+2) + ... + (1+10) + (2+2) + (2+3) + ... + (10 + 10)
\)
Jika ada beberapa syarat, cukup susun syarat-syaratnya:
\(\displaystyle
\sum_{\begin{array}{c} 1 \le i \le 10 \\ i \bmod 2 = 0 \end{array}} f(i) = f(2) + f(4) + f(6) + f(8) + f(10)
\)
Gaya penulisan ini lebih fleksibel jika iteratornya bukan sesuatu yang umum untuk diiterasi, misalnya anggota dari himpunan:
\(\displaystyle
\sum_{x \in child(p)} f(x) = f(c_1) + f(c_2) + f(c_3)
\)
Dengan \(child(p) = \lbrace c_1, c_2, c_3 \rbrace\)
Dan terkadang penggunaannya abusive, tanpa memberi keterangan lebih jelas (hindari!):
\(\displaystyle
\sum_{i \; dibutuhkan} f(i)
\)
Apa yang dimaksud dengan dibutuhkan??
--
Perkalian (pi)
Untuk menulis perkalian yang diiterasi, notasinya mirip dengan notasi sigma. Beberapa contoh:\(\displaystyle
\prod_{i = a}^{b} f(i) = f(a) \times f(a+1) \times f(a+2) \times ... \times f(b)
\)
\(\displaystyle
\prod_{1 \le i \lt j \le 4} (i+j) = (1+2) \times (1+3) \times (1+4) \times (2+3) \times (2+4) \times (3+4)
\)
--
max/min
Nah ini yang sangat sering digunakan. Anda dapat menggunakan notasi max/min untuk menyatakan pencarian elemen terbesar/terkecil dari sejumlah elemen:\(\displaystyle
\max{(1, 2)} = 2
\)
\(\displaystyle
\max{(1, 3, 4)} = 3
\)
\(\displaystyle
\max{(1, 3, 4, 2)} = 4
\)
\(\displaystyle
\min{(1, 3, 4, 2)} = 1
\)
Jika elemennya butuh diiterasi/bersyarat, dapat digunakan notasi semacam sigma. Saya lebih menyukai penggunaan notasi yang menyatakan syarat.
\(\displaystyle
\max_{1 \le i \le 10} f(i) = \max{(f(1), f(2), f(3), ..., f(10))}
\)
Latihan
Ambil secarik kertas dan coba tuliskan rumus-rumus untuk DP klasik yang Anda ketahui, misalnya:- Coin Change
- Longest Increasing Subsequence (LIS)
- Longest Common Subsequence (LCS)
- Matrix Chain Multiplication (MCM)
Tidak ada komentar :
Posting Komentar