Dinamik programlama, aynı alt problemlerin sonuçlarını yeniden kullanarak hesaplamayı azaltan bir algoritma tasarım yaklaşımıdır. Fibonacci gibi özyinelemeli problemlerde, daha önce hesaplanan değerleri saklamak gereksiz tekrarları azaltır. Bu saklama işlemi yukarıdan aşağı memoization veya aşağıdan yukarı tabulation yöntemiyle yapılabilir.
Fibonacci örneği yaklaşımın neden gerekli olduğunu açıkça gösterir: saf özyineleme aynı değerleri farklı çağrı dallarında yeniden hesaplar. Dinamik programlamanın temelini anlamak için önce alt problemlerin nasıl oluştuğunu ve hangi özellikleri taşıdığını incelemek gerekir.
Dinamik programlama nedir ve hangi iki koşula dayanır?
Dinamik programlama, büyük bir problemi daha küçük alt problemlere ayırıp bu alt problemlerin sonuçlarını saklayarak aynı hesaplamaları yeniden yapmayı önleyen bir algoritma tasarım yaklaşımıdır. Bir alt problem, asıl problemin çözümünde kullanılan daha küçük ve bağımsız olarak ifade edilebilen problem parçasıdır.
Bu yaklaşım genellikle iki temel koşulla açıklanır: örtüşen alt problemler ve optimal alt yapı. Her problemde bu iki özelliğin aynı biçimde bulunması gerekmez; ancak dinamik programlama kararını verirken bu özellikleri aramak güçlü bir başlangıç sağlar.
Örtüşen alt problemler aynı girdilerin yeniden ortaya çıkmasıdır
Örtüşen alt problemler, çözüm sırasında aynı alt problem girdilerinin birden fazla kez ortaya çıkması anlamına gelir. Örneğin Fibonacci hesabında F(3) değeri farklı çağrı dallarında tekrar istenir. Değer her defasında yeniden hesaplanırsa işlem tekrarı oluşur, daha önce hesaplanan değer saklanırsa aynı sonuç tekrar kullanılabilir.
Dinamik programlama bu tekrarları iki farklı yönde yönetebilir. Memoization, ihtiyaç duyulan alt problemi hesaplandığı anda kaydeden yukarıdan aşağı bir yaklaşımdır. Tabulation ise daha küçük alt problemlerin sonuçlarından başlayarak tabloyu aşağıdan yukarı doldurur.
Optimal alt yapı, büyük çözümün alt çözümlerden kurulabilmesidir
Optimal alt yapı, bir problemin uygun çözümünün, ilgili alt problemlerin uygun çözümlerinden kurulabilmesiyle ilgilidir. Bu ifade özellikle en kısa yol veya en düşük maliyet gibi bir optimizasyon amacı taşıyan problemlerde kullanılır. Büyük problemin iyi bir çözümü, alt parçalar için uygun çözümlerin doğru biçimde birleştirilmesiyle elde edilir.
Fibonacci dizisinde bir optimizasyon amacı bulunmadığı için “optimal” sözcüğü dikkatli yorumlanmalıdır. Burada en iyi seçimi aramak yerine, daha büyük Fibonacci değerlerinin daha küçük Fibonacci değerlerinden kurulması ve bu alt sonuçların tekrar kullanılabilmesi önemlidir. Bu nedenle Fibonacci, dinamik programlamadaki tekrar kullanılabilir alt sonuç yapısını göstermek için uygun ve anlaşılır bir örnektir.
Fibonacci neden aynı alt problemleri tekrar hesaplar?
Doğrudan özyinelemeli Fibonacci kodu, aynı Fibonacci değerlerini farklı çağrı dallarında yeniden hesaplar. Dizinin temel tanımı şöyledir: F(0) = 0, F(1) = 1 ve F(n) = F(n - 1) + F(n - 2).
F(5) hesaplanırken fonksiyon önce F(4) ve F(3) değerlerini ister. F(4) kendi içinde F(3) ve F(2) değerlerini çağırır. Böylece F(3) ile F(2) aynı çağrı ağacının farklı bölümlerinde tekrar görünür:
F(5)
├─ F(4)
│ ├─ F(3)
│ │ ├─ F(2)
│ │ │ ├─ F(1)
│ │ │ └─ F(0)
│ │ └─ F(1)
│ └─ F(2) [tekrar]
│ ├─ F(1)
│ └─ F(0)
└─ F(3) [tekrar]
├─ F(2) [tekrar]
│ ├─ F(1)
│ └─ F(0)
└─ F(1)Aşağıdaki sayaç, fonksiyona her girişte bir kez artırılır. Bu nedenle temel durumlara ulaşan çağrılar da toplam sayıya dâhil edilir:
calls = 0
def fib(n):
global calls
calls += 1
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
result = fib(5)
print("Sonuç:", result)
print("Toplam çağrı:", calls)Bu kodun çıktısı şöyledir:
Sonuç: 5
Toplam çağrı: 15F(5) için 15 çağrı yapılmasının nedeni, aynı alt sonuçların önceden saklanmamasıdır. Girdi büyüdükçe çağrı ağacı dallanmaya devam eder ve hesaplama maliyeti hızlı biçimde artma eğilimi gösterir. Memoization, her alt problemi ilk hesaplamadan sonra kaydederek bu tekrarları azaltır; tabulation ise değerleri küçük girdilerden başlayarak sıralı biçimde üretir.
Memoization ile Fibonacci yukarıdan aşağı nasıl çözülür?
Memoization, çözüm sırasında hesaplanan Fibonacci değerlerini bir sözlükte saklayıp sonraki çağrılarda yeniden kullanır ve aynı alt problemlerin tekrar hesaplanmasını azaltır. Bu yaklaşımda fonksiyon, ihtiyaç duyduğu değeri önce önbellekte arar; değer yoksa özyinelemeli olarak hesaplar ve sonucu sözlüğe ekler.
def fibonacci(n, memo=None, stats=None):
if memo is None:
memo = {}
if stats is not None:
stats["giris"] += 1
if n in memo:
return memo[n]
if stats is not None:
stats["miss"] += 1
if n < 2:
sonuc = n
else:
sonuc = fibonacci(n - 1, memo, stats) + fibonacci(n - 2, memo, stats)
memo[n] = sonuc
return sonuc
stats = {"giris": 0, "miss": 0}
print(fibonacci(5, stats=stats))
print(stats)Beklenen çıktı: Fibonacci(5) değeri 5, toplam fonksiyon girişi 10, cache miss sayısı ise 6 olur. Toplam giriş sayısı, önbellekte bulunan değerler için yapılan çağrıları da kapsar. Cache miss sayısı ise gerçekten hesaplanan farklı alt problemlerin sayısını gösterir. Bu örnekte 0 ile 5 arasındaki değerlerin her biri bir kez hesaplanır.
memo=None kullanımı burada önemlidir. Fonksiyon her çağrıldığında doğrudan memo={} yazılsaydı her özyinelemeli çağrı yeni bir sözlük oluşturur ve önceki sonuçlar kaybolurdu. None kontrolü sayesinde sözlük yalnızca ilk çağrıda oluşturulur, sonraki çağrılara aynı nesne aktarılır.
Daha kısa bir çözüm için functools.lru_cache dekoratörü kullanılabilir. Dekoratör, fonksiyonun belirli argümanlarla ürettiği sonuçları saklar ve aynı argümanla gelen çağrılarda gövdeyi yeniden çalıştırmadan önbellekteki sonucu döndürür. Python’un functools.lru_cache belgelerinde Fibonacci için benzer bir kullanım gösterilir.
from functools import lru_cache
calls = 0
@lru_cache(maxsize=None)
def fibonacci(n):
global calls
calls += 1
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(5))
print(calls)
print(fibonacci.cache_info())Bu örnekte sayaç fonksiyon gövdesinin içine yerleştirildiği için yalnızca gerçek hesaplamalar sayılır. fibonacci(5) için sonuç 5, gövdeye giriş sayısı ve cache miss sayısı 6, önbellekten karşılanan çağrı sayısı ise 4 olur.
Tabulation ile Fibonacci aşağıdan yukarı nasıl hesaplanır?
Tabulation, en küçük alt problemlerin sonuçlarından başlayıp tabloyu sırayla doldurarak sonuca ulaşır. Fibonacci için önce F(0) ve F(1) bilinir, ardından her yeni değer kendisinden önceki iki değerin toplamıyla hesaplanır.
def fibonacci_table(n):
if n < 2:
return n
tablo = [0] * (n + 1)
tablo[1] = 1
for i in range(2, n + 1):
tablo[i] = tablo[i - 1] + tablo[i - 2]
return tablo[n]
print(fibonacci_table(5))Beklenen çıktı: 5. n=0 için doğrudan 0, n=1 için doğrudan 1 döndürülür. Daha büyük bir n değerinde döngü 2'den n'e kadar ilerler ve her adımda yeni bir Fibonacci değeri üretir.
Tablo sürümü, daha sonra bütün ara sonuçlara erişmek gerektiğinde kullanışlıdır. Yalnızca son değeri hesaplamak yeterliyse tablonun tamamını saklamak zorunlu değildir. Çünkü yeni Fibonacci değeri için yalnızca önceki iki değer gerekir.
def fibonacci_two_values(n):
if n < 2:
return n
onceki, mevcut = 0, 1
for _ in range(2, n + 1):
onceki, mevcut = mevcut, onceki + mevcut
return mevcut
print(fibonacci_two_values(5))Bu sürümde döngü her adımda önceki iki değeri günceller ve yine 5 sonucunu üretir. Tabulation özyinelemeli çağrı kullanmadığı için burada çağrı sayısı yerine döngüde yapılan alt problem hesaplamaları veya toplama adımları karşılaştırılır.
Üç Fibonacci yönteminin zaman ve bellek maliyeti nedir?
Saf özyinelemeli Fibonacci, aynı alt problemleri tekrar tekrar hesapladığı için üstel zaman maliyetine sahiptir; memoization ve tabulation ise her alt problemi doğrusal sayıda hesaplayarak daha düşük zaman maliyeti sunar. Aşağıdaki karşılaştırma, aritmetik işlemlerin sabit maliyetli kabul edildiği klasik analiz çerçevesine dayanır.
| Yöntem | Zaman karmaşıklığı | Ek bellek | Temel neden |
|---|---|---|---|
| Saf özyineleme | O(2n) üst sınırı, daha sıkı ifadeyle Θ(φn) | O(n) özyineleme yığını | Aynı alt problemlerin tekrar tekrar hesaplanması |
Sözlükle memoization veya lru_cache |
O(n) | O(n), cache ve çağrı yığını | Her alt problemin sonucunun saklanıp yeniden kullanılması |
| Tam tabulation | O(n) | O(n) tablo belleği | Sonuçların aşağıdan yukarı sırayla tabloya yazılması |
| Yalnızca son iki değeri tutan tabulation | O(n) | O(1) ek bellek | Bir sonraki Fibonacci değeri için yalnızca önceki iki değerin yeterli olması |
Buradaki φ sembolü, altın oranı ifade eder ve Fibonacci çağrı ağacının büyüme hızını daha sıkı biçimde anlatmak için kullanılır. O(2n) ifadesi pratik bir üst sınırdır, Θ(φn) ise saf özyinelemeli yaklaşımın büyümesini daha yakından açıklar.
Bu karşılaştırmada tam sayı işlemlerinin sabit maliyetli olduğu varsayılır. Büyük Fibonacci sayılarında sayıların basamak veya bit uzunluğu arttığı için toplama işlemlerinin kendi maliyeti de hesaba katılabilir. Bu nedenle tablo, algoritmaların alt problem hesaplama davranışını karşılaştırmak için kullanılan temel modeldir.
Memoization hangi hatalarla bozulur ve ne zaman uygundur?
Memoization’ın doğru çalışması için cache’in ilgili çağrılar arasında korunması ve bir alt problemin aynı girdilerle yeniden oluştuğunun tanınması gerekir. Cache her çağrıda sıfırlanırsa daha önce hesaplanan sonuçlar kaybolur ve algoritma tekrar hesaplama yapmaya başlar.
Memo sözlüğünü fonksiyon içinde yeniden oluşturmak
Aşağıdaki hatalı örnekte memo sözlüğü fonksiyonun her çağrısında yeniden oluşturulur. Böylece fibonacci(n - 1) ve fibonacci(n - 2) çağrılarının her biri kendi boş sözlüğüyle çalışır.
def fibonacci(n):
memo = {}
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
return memo[n]Düzeltilmiş yaklaşımda sözlük dışarıdan taşınır. İlk çağrıda memo değeri None ise yeni bir sözlük oluşturulur, sonraki özyinelemeli çağrılar aynı sözlüğü kullanır.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]Değiştirilebilir varsayılan argüman kullanmak
memo={} biçimindeki değiştirilebilir varsayılan argüman, fonksiyon her çağrıldığında yeni bir sözlük oluşturmaz. Aynı sözlük, birbirinden bağımsız üst seviye çağrılar arasında da korunabildiği için beklenmedik durum taşınabilir.
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]Bu nedenle memo=None kullanıp sözlüğü fonksiyonun içinde yalnızca gerektiğinde oluşturmak daha güvenlidir. Aynı yaklaşım, liste veya küme gibi değiştirilebilir diğer varsayılan argümanlar için de geçerlidir.
Her özyinelemeli problem memoization için uygun değildir
Özyinelemeli bir çözümün bulunması, problemin otomatik olarak dinamik programlamaya uygun olduğu anlamına gelmez. Memoization’dan yararlanabilmek için alt problemlerin belirli koşulları karşılaması gerekir.
- Çözüm ağacında aynı girdilerle oluşan örtüşen alt problemler bulunmalıdır.
- Bir alt problemin sonucu, aynı girdilerle karşılaşıldığında yeniden kullanılabilmelidir.
- Problemin daha büyük çözümünü alt sonuçlardan kuran uygun bir geçiş bağıntısı bulunmalıdır.
- Durum, sonucu etkileyen girdileri sınırlı ve açık bir biçimde temsil edebilmelidir.
Bu koşullar yoksa cache eklemek yalnızca bellek kullanımını artırabilir. Örneğin her çağrıda farklı ve daha önce karşılaşılmamış bir durum oluşuyorsa saklanan sonuçlar yeterince tekrar kullanılmaz.
Fibonacci’de memoization ile tabulation arasında seçim yaparken özyinelemeli anlatımın okunabilirliği, çağrı yığınının kullanacağı bellek ve yalnızca gerekli sonuçların saklanıp saklanamayacağı birlikte değerlendirilir. Özyinelemeli çözümün yapısını korumak istiyorsan memoization anlaşılır bir seçenek olabilir. Döngüyle ilerlemek ve çağrı yığını kullanmamak istiyorsan tabulation, özellikle yalnızca son iki değeri saklayan biçimiyle daha az ek bellek kullanabilir.
Sık Sorulan Sorular
Memoization ile tabulation arasındaki temel fark nedir?
Memoization, özyinelemeli çözüm sırasında ihtiyaç duyulan alt problemlerin sonuçlarını saklayan yukarıdan aşağı bir yaklaşımdır. Tabulation ise başlangıç durumlarından ilerleyerek alt problemleri aşağıdan yukarı sırayla hesaplar ve genellikle döngülerle uygulanır.
Fibonacci hesabında neden yalnızca son iki değeri saklamak yeterlidir?
Fibonacci dizisinde yeni değer, kendisinden önce gelen iki değerin toplamıyla hesaplanır. Bu nedenle daha eski değerler sonraki adımlarda doğrudan kullanılmaz ve tablo yerine iki değişken tutularak O(1) ek bellekle ilerlenebilir.
Memo sözlüğü neden her özyinelemeli çağrıda yeniden oluşturulmamalıdır?
Memo sözlüğü her çağrıda yeniden oluşturulursa önceki çağrıların sonuçları silinir ve aynı alt problemler tekrar hesaplanır. Sözlüğün çağrılar arasında paylaşılması, hesaplanan sonuçların sonraki çağrılarda kullanılmasını sağlar.
Her özyinelemeli problem dinamik programlama ile çözülebilir mi?
Her özyinelemeli problem dinamik programlamaya uygun değildir. Örtüşen alt problemlerin, yeniden kullanılabilir sonuçların, geçiş bağıntısının ve sınırlı bir durum temsilinin bulunması gerekir.
Fibonacci örneği, dinamik programlamada doğru durum tanımının ve uygun saklama stratejisinin zaman ile bellek maliyetini nasıl değiştirdiğini açıkça gösterir.
