Fibonacci dan pemrograman dinamis
Minta komputer menghitung bilangan Fibonacci ke-40 dengan cara yang paling jelas, dan ia akan membuat lebih dari 331 juta panggilan. Minta dengan tabel, dan ia cukup melakukan 39 penjumlahan. Bedanya adalah pemrograman dinamis, dan bilangan Fibonacci adalah tempat hampir semua orang pertama kali mengenalnya.
Masalahnya
Bilangan Fibonacci dimulai dengan 0, 1, dan setiap bilangan berikutnya adalah jumlah dua bilangan sebelumnya: 0, 1, 1, 2, 3, 5, 8, 13, 21, dan seterusnya. Jika ditulis sebagai aturan, F(0) = 0, F(1) = 1, dan F(n) = F(n − 1) + F(n − 2). Aturan ini rekursif, dan mengubahnya langsung menjadi program rekursif itu mudah, tetapi program tersebut ternyata sangat lambat.
Mengapa rekursi mengulang dirinya
Untuk mencari F(5), program meminta F(4) dan F(3). F(4) meminta F(3) dan F(2), sehingga F(3) dihitung dua kali, F(2) tiga kali, dan F(1) lima kali. Jika digambar sebagai pohon, jumlah panggilan hampir berlipat dua di setiap tingkat, dan totalnya untuk F(n) adalah 2·F(n + 1) − 1 panggilan. Masalah-masalah kecilnya tumpang tindih: masalah yang sama muncul lagi dan lagi. Itulah tanda bahwa pemrograman dinamis akan membantu.
Dua cara mengingat
Memoisasi tetap memakai rekursi tetapi menulis setiap jawaban ke dalam tabel, dan setiap panggilan memeriksa tabel sebelum melakukan pekerjaan apa pun. Tabulasi mengisi tabel dari bawah ke atas: F(0) dan F(1) dulu, lalu F(2) dari keduanya, F(3) dari F(2) dan F(1), dan seterusnya sampai F(n). Dengan cara mana pun, setiap suku dihitung satu kali, jadi F(n) hanya butuh n − 1 penjumlahan, bukan panggilan yang jumlahnya eksponensial.
Sebuah contoh
Bawah ke atas untuk F(7): mulai dengan 0 dan 1. Lalu 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, dan 5 + 8 = 13, jadi F(7) = 13 setelah enam penjumlahan. Rekursi biasa akan membuat 2·F(8) − 1 = 41 panggilan untuk jawaban yang sama. Pada atas ke bawah, panggilan-panggilan pertama turun terus sampai F(1) di sepanjang tepi kiri pohon; dalam perjalanan kembali ke atas, hampir setiap panggilan kedua menemukan jawabannya sudah ada di tabel.
Asal nama
Richard Bellman memberi nama pemrograman dinamis pada awal 1950-an saat bekerja di RAND Corporation. Belakangan ia menulis bahwa ia memilih kata programming dalam arti lamanya, yaitu perencanaan, dan dynamic karena terdengar mengesankan dan sulit dibantah. Metodenya sendiri, yaitu menyelesaikan masalah melalui jawaban dari versi-versi yang lebih kecil, kini dipakai di pemeriksa ejaan, perencana rute, dan perbandingan DNA.
Jelajahi sendiri
Buka aplikasinya dan tekan Langkah. Pada bawah ke atas, sel oranye sedang diisi dan dua sel biru adalah suku yang dijumlahkannya. Beralihlah ke atas ke bawah dan perhatikan tumpukan panggilan di bawah tabel tumbuh sampai n, lalu menyusut saat jawaban-jawaban kembali; petunjuk di bawah Penjumlahan menghitung berapa panggilan yang langsung dijawab dari tabel.
Pertanyaan yang sering diajukan
Apa itu submasalah yang tumpang tindih?
Masalah-masalah kecil yang dibutuhkan sebuah solusi lebih dari sekali. F(n) dan F(n − 1) sama-sama membutuhkan F(n − 2), sehingga rekursi biasa menghitungnya dua kali, dan pemborosan itu makin berlipat di tingkat yang lebih bawah. Pemrograman dinamis menyelesaikan masing-masing satu kali dan mengingat jawabannya.
Apakah memoisasi lebih cepat daripada tabulasi?
Keduanya melakukan penjumlahan yang sama. Tabulasi biasanya sedikit lebih cepat karena tidak membuat panggilan, dan tidak bisa kehabisan ruang tumpukan; memoisasi berguna jika hanya sebagian jawaban kecil yang dibutuhkan, karena ia hanya menghitung yang itu saja.
Bisakah bilangan Fibonacci dihitung lebih cepat lagi?
Bisa. Dengan F(2k) = F(k)·(2·F(k + 1) − F(k)) dan F(2k + 1) = F(k)² + F(k + 1)², metode fast doubling hanya memerlukan sekitar log₂ n langkah. Rumus Binet dengan rasio emas memberikan bilangan yang sama, tetapi galat pembulatan membuatnya tidak andal untuk n yang besar.
Berapa banyak memori yang dibutuhkan tabel?
Tabel lengkap menyimpan n + 1 angka, tetapi setiap suku baru hanya membutuhkan dua suku sebelumnya, jadi perulangan yang menyimpan dua angka melakukan pekerjaan yang sama dengan memori konstan. Menyimpan seluruh tabel berguna jika Anda menginginkan semua suku, atau ingin melihat cara kerja metodenya.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba Fibonacci dengan pemrograman dinamis