Dinamik Programlama
- İngilizcesi
- Dynamic Programming
- Okunuşu
- daynemik programing
Kısaca
Dinamik programlama, bir problemi çakışan alt problemlere bölüp her cevabı saklayarak hiçbirini iki kez çözmeden problemi çözme tekniğidir.
Dinamik programlama (dynamic programming) nedir?
Dinamik programlama (DP), bir problemi aynı problemin daha küçük sürümlerinin cevaplarını birleştirerek çözme yöntemidir. İki koşul sağlandığında uygulanır: alt problemler çakışır, yani aynı küçük problemler tekrar tekrar karşımıza çıkar; ayrıca problem optimal alt yapıya sahiptir, yani en iyi genel cevap alt problemlerinin en iyi cevaplarından kurulabilir. DP her farklı alt problemi bir kez çözer, sonucu kaydeder ve yeniden kullanır.
İki yaygın biçimi vardır. Yukarıdan aşağı DP, normal bir özyinelemeli çözüm yazar ve buna memoization ekler; bu, her sonucu ilk hesaplandığında saklayan bir önbellektir. Aşağıdan yukarı DP ise tabulation olarak da adlandırılır; en küçük alt problemlerden başlayarak bir tabloyu doldurur ve özyineleme kullanmadan son cevaba doğru ilerler. Örneğin saf özyinelemeli bir Fibonacci fonksiyonu aynı değerleri defalarca yeniden hesapladığı için üstel sürede çalışır; DP'nin iki sürümü de n. sayıyı O(n) sürede hesaplar.
Günlük bir benzetme: biri sizden 1 + 1 + 1 + 1 + 1 işlemini isterse beşe kadar sayarsınız; ardından bir 1 daha eklerse baştan saymazsınız, hatırladığınız beşe bir eklersiniz. DP; verilen bir tutarı oluşturan en az madeni para sayısı, diff araçlarının arkasındaki en uzun ortak altdizi, yazım denetleyicilerinin kullandığı düzenleme mesafesi ve sınırlı alana en fazla değeri yerleştirmeye çalışan sırt çantası problemi gibi klasik problemleri çözer.
Ad yanıltıcıdır: dinamik tiplemeyle bir ilgisi yoktur ve yöntemi 1950'lerde geliştiren Richard Bellman, dinamik sözcüğünü kısmen etkileyici duyulduğu için seçmiştir. DP sıklıkla merge sort'taki gibi böl ve yönet yaklaşımıyla karıştırılır; o da problemi alt problemlere böler, ancak bu alt problemler çakışmaz, dolayısıyla yeniden kullanılacak bir şey yoktur. DP, her adımda yerel olarak en iyi seçimi yapan ve en iyi cevabı kaçırabilen açgözlü algoritmadan da farklıdır: 1, 3 ve 4 değerli madeni paralarla 6 oluşturmak istediğinizde açgözlü yöntem 4 + 1 + 1 seçer, DP ise 3 + 3'ü bulur.
Önemli noktalar
- DP, bir problemin çakışan alt problemleri ve optimal alt yapısı olduğunda işe yarar.
- Her farklı alt problem bir kez çözülür ve sonucu yeniden kullanılmak üzere saklanır.
- Yukarıdan aşağı DP memoization'lı özyineleme kullanır; aşağıdan yukarı DP tabloyu en küçük durumlardan doldurur.
- Üstel zamanlı çözümleri polinom zamanlıya çevirebilir; örneğin Fibonacci sayıları için O(n).
- Böl ve yönet yaklaşımının aksine DP, tekrar eden alt problemlere dayanır.
Örnek
def min_coins(coins, amount):
# best[a] = fewest coins that add up to a; start every amount as "impossible"
best = [0] + [float("inf")] * amount
for a in range(1, amount + 1):
for coin in coins:
if coin <= a:
# Reuse the stored answer for the smaller amount a - coin
best[a] = min(best[a], best[a - coin] + 1)
return best[amount] if best[amount] != float("inf") else -1
# O(amount * len(coins)) time instead of exponential recursion
print(min_coins([1, 3, 4], 6)) # 2 (3 + 3); greedy would use 3 coins (4 + 1 + 1)Sık sorulan sorular
Dinamik programlama ile memoization arasındaki fark nedir?
Memoization, bir fonksiyonun her girdi için sonucunu saklayan ve tekrarlanan çağrıları anında yanıtlayan bir önbellekleme tekniğidir. Dinamik programlama ise çakışan alt problemleri bir kez çözmeyi hedefleyen daha geniş bir stratejidir; memoization bunu uygulamanın yukarıdan aşağı DP denen bir yoludur, diğeri aşağıdan yukarı tabulation'dır.
Bir problemin dinamik programlamaya ihtiyacı olduğunu nasıl anlarım?
En düşük maliyet ya da yol sayısı gibi en iyi bir değeri veya bir sayıyı soran, saf özyinelemeli çözümü aynı girdileri defalarca yeniden hesaplayan bir problem arayın. Bir girdinin cevabı daha küçük girdilerin cevaplarından kurulabiliyorsa DP büyük olasılıkla uygundur.
Buna neden dinamik programlama deniyor?
Adı 1950'lerde Richard Bellman koydu. Programlama, kod yazmayı değil planlamayı ve tabloları doldurmayı ifade ediyordu; dinamik sözcüğünü ise kısmen araştırmasını finanse eden yetkililere etkileyici geleceği için seçti.
İlgili sayfalar
- MemoizationProgramlamanın Temelleri, s. 37Memoization, fonksiyon çağrılarının sonuçlarını saklayıp aynı girdiler tekrar geldiğinde kaydedilen sonucu döndüren bir optimizasyon tekniğidir.
- ÖzyinelemeProgramlamanın Temelleri, s. 42Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- ÖnbellekBackend ve API'ler, s. 34Önbellek, sık kullanılan verilerin kopyalarını tutan hızlı ve geçici bir depolama katmanıdır; sonraki istekler yavaş işi tekrarlamadan hızla karşılanır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin