Fibonacci ve dinamik programlama
Bir bilgisayardan 40. Fibonacci sayısını en bariz yoldan isterseniz 331 milyondan fazla çağrı yapar. Bir tabloyla isterseniz 39 toplama yeter. Aradaki fark dinamik programlamadır ve neredeyse herkes onunla ilk kez Fibonacci sayılarında tanışır.
Problem
Fibonacci sayıları 0, 1 ile başlar ve sonraki her sayı kendinden önceki iki sayının toplamıdır: 0, 1, 1, 2, 3, 5, 8, 13, 21 ve böyle devam eder. Kural olarak yazıldığında F(0) = 0, F(1) = 1 ve F(n) = F(n − 1) + F(n − 2). Kural özyinelemelidir ve onu doğrudan özyinelemeli bir programa çevirmek kolaydır, ama bu programın çok yavaş olduğu ortaya çıkar.
Özyineleme neden kendini tekrar eder?
F(5)'i bulmak için program F(4) ve F(3)'ü ister. F(4) de F(3) ve F(2)'yi ister; böylece F(3) iki kez, F(2) üç kez ve F(1) beş kez hesaplanır. Ağaç olarak çizildiğinde çağrılar her seviyede neredeyse ikiye katlanır ve F(n) için toplam 2·F(n + 1) − 1 çağrıdır. Küçük problemler örtüşür: aynıları tekrar tekrar karşımıza çıkar. Bu, dinamik programlamanın işe yarayacağının işaretidir.
Hatırlamanın iki yolu
Memoization özyinelemeyi korur ama her cevabı bir tabloya yazar ve her çağrı herhangi bir iş yapmadan önce tabloya bakar. Tablolama tabloyu aşağıdan yukarı doldurur: önce F(0) ve F(1), sonra onlardan F(2), F(2) ve F(1)'den F(3) ve böylece F(n)'ye kadar. Her iki durumda da her terim bir kez hesaplanır, bu yüzden F(n) üstel sayıda çağrı yerine n − 1 toplamaya mal olur.
Bir örnek
F(7) için aşağıdan yukarı: 0 ve 1 ile başlayın. Sonra 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 ve 5 + 8 = 13; yani altı toplamadan sonra F(7) = 13. Düz özyineleme aynı cevap için 2·F(8) − 1 = 41 çağrı yapardı. Yukarıdan aşağı yöntemde ilk çağrılar ağacın sol kenarı boyunca F(1)'e kadar iner; geri dönüşte neredeyse her iki çağrıdan biri cevabını tabloda hazır bulur.
Adı nereden geliyor?
Richard Bellman, dinamik programlamaya bu adı 1950'lerin başında RAND Corporation'da çalışırken verdi. Daha sonra, programlama kelimesini eski anlamıyla, yani planlama anlamında seçtiğini; dinamik kelimesini de kulağa etkileyici geldiği ve itiraz edilmesi zor olduğu için seçtiğini yazdı. Yöntemin kendisi, yani bir problemi daha küçük hâllerinin cevaplarıyla çözmek, bugün yazım denetleyicilerinde, rota planlayıcılarında ve DNA karşılaştırmasında çalışıyor.
Kendiniz keşfedin
Uygulamayı açın ve Adım'a basın. Aşağıdan yukarı yöntemde turuncu hücre doldurulan hücredir, iki mavi hücre ise topladığı terimlerdir. Yukarıdan aşağı yönteme geçin ve tablonun altındaki çağrı yığınının n'ye kadar büyüyüp cevaplar geri geldikçe küçülmesini izleyin; Toplamalar kutusunun altındaki ipucu, kaç çağrının doğrudan tablodan cevaplandığını sayar.
Sık sorulan sorular
Örtüşen alt problemler nedir?
Bir çözümün birden fazla kez ihtiyaç duyduğu küçük problemlerdir. F(n) ve F(n − 1)'in ikisi de F(n − 2)'ye ihtiyaç duyar, bu yüzden düz özyineleme onu iki kez hesaplar ve bu israf aşağıya indikçe katlanır. Dinamik programlama her birini bir kez çözer ve cevabı hatırlar.
Memoization tablolamadan daha mı hızlı?
İkisi de aynı toplamaları yapar. Tablolama genellikle biraz daha hızlıdır çünkü hiç çağrı yapmaz ve yığın alanı tükenmez; memoization ise küçük cevapların yalnızca bir kısmı gerektiğinde kullanışlıdır, çünkü yalnızca onları hesaplar.
Fibonacci sayıları daha da hızlı hesaplanabilir mi?
Evet. F(2k) = F(k)·(2·F(k + 1) − F(k)) ve F(2k + 1) = F(k)² + F(k + 1)² kullanan hızlı ikiye katlama yöntemi yalnızca yaklaşık log₂ n adım gerektirir. Altın oranla Binet formülü de aynı sayıları verir, ancak yuvarlama hataları onu büyük n için güvenilmez kılar.
Tablo ne kadar bellek gerektirir?
Tam bir tablo n + 1 sayı tutar, ama her yeni terim yalnızca kendinden önceki iki terime ihtiyaç duyar; bu yüzden iki sayı tutan bir döngü aynı işi sabit bellekle yapar. Tüm terimleri istediğinizde ya da yöntemin nasıl çalıştığını görmek istediğinizde tablonun tamamını tutmak işe yarar.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Dinamik programlama ile Fibonacci'yi deneyin