Dinamik Programlama — Memoization ve Tabulation Açıklaması

Dinamik programlama, daha küçük alt problemlerin cevaplarını saklayıp daha sonra yeniden kullanarak problemleri çözme yöntemidir. Aynı alt problemler tekrar ortaya çıktığında ve tam cevap bu küçük cevaplardan kurulabildiğinde işe yarar.

İki temel yaklaşım memoization ve tabulation’dır. Memoization, özyinelemeli bir çözüm sırasında cevapları saklar. Tabulation ise cevapları aşağıdan yukarı bir sırayla, genellikle bir dizi veya tablo kullanarak doldurur.

Dinamik programlama ne zaman işe yarar?

Dinamik programlama, iki koşul sağlandığında kullanışlıdır.

İlk olarak, alt problemler çakışır. Yani aynı ara sonuca birden fazla kez ihtiyaç duyulur. İkinci olarak, daha büyük cevaplar daha küçük cevaplardan tutarlı bir şekilde kurulabilir.

Bu koşullar sağlanmıyorsa, eski sonuçları saklamak çok fayda sağlamadan ek bellek maliyeti getirebilir.

Memoization ve tabulation karşılaştırması

Memoization: yukarıdan aşağı saklama

Memoization, özyinelemeli fikirle başlar. Algoritma bir alt problemi ilk kez çözdüğünde sonucu saklar. Daha sonraki çağrılar, yeniden hesaplamak yerine saklanan değeri kullanır.

Bu yaklaşım, yineleme bağıntısı açık olduğunda ama gerekli tüm durumların sırası net olmadığında genellikle daha kolaydır.

Tabulation: aşağıdan yukarı kurma

Tabulation, taban durumlarından başlar ve durumları, ihtiyaç duyulan bağımlılıkların hazır olacağı bir sırayla doldurur.

Bu yaklaşım, temiz bir yineleme sırasını zaten bildiğinizde ve tablo üzerinde açık kontrol istediğinizde genellikle daha kolaydır.

Dinamik programlama örneği: Fibonacci

Fibonacci dizisi şu şekilde tanımlanır:

$$F(0) = 0, \quad F(1) = 1$$

ve $n \ge 2$ için,

$$F(n) = F(n-1) + F(n-2)$$

Düz bir özyinelemeli çözüm aynı işi tekrar eder. Örneğin, $F(5)$ hesaplanırken $F(4)$ ve $F(3)$ gerekir; ardından $F(4)$ hesaplanırken yine $F(3)$ gerekir. Tekrarlanan bu $F(3)$ çağrısı, dinamik programlamanın ortadan kaldırdığı türden bir israftır.

Fibonacci üzerinde memoization

Memoization ile yineleme bağıntısı aynı kalır, ancak her değer ilk kez hesaplandıktan sonra saklanır.

$F(5)$ için yararlı sıra şöyledir:

• $F(0)=0$ hesaplanır ve saklanır
• $F(1)=1$ hesaplanır ve saklanır
• $F(2)=1$ hesaplanır ve saklanır
• $F(3)=2$ hesaplanır ve saklanır
• $F(4)=3$ hesaplanır ve saklanır
• $F(5)=5$ hesaplanır ve saklanır

Temel nokta, her durumun bir kez hesaplanmasıdır. Daha sonraki istekler saklanan değeri okur.

Fibonacci üzerinde tabulation

Tabulation ile taban durumlarından yukarı doğru ilerlersiniz:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Bu sürüm, bağımlılık sırasını açıkça gösterir: her yeni değer, zaten bilinen girişleri kullanır.

Dinamik programlama neden daha hızlı olabilir?

Bir problemde önemli olan yalnızca $k$ farklı durum varsa, dinamik programlama bu $k$ durumu birer kez çözmeye çalışır. Bu da büyük bir özyineleme ağacını çok daha küçük bir hesaplamaya dönüştürebilir.

Kesin hızlanma probleme bağlıdır. Dinamik programlama kendiliğinden hızlı değildir. Asıl faydası, tekrar eden işin özgün çözümün gerçek bir parçası olduğu durumlarda ortaya çıkar.

Dinamik programlamada yaygın hatalar

Alt problemler çakışmadığında kullanmak

Her özyinelemeli problem bir dinamik programlama problemi değildir. Alt problemlerin neredeyse hepsi farklıysa, sonuçları önbelleğe almak fark yaratacak kadar iş kazandırmayabilir.

Yanlış durumu tanımlamak

Durum, bir sonraki adım için gereken tüm bilgiyi içermelidir. Önemli bilgi eksikse, yineleme bağıntısı doğru görünebilir ama yanlış cevaplar üretebilir.

Taban durumlarını yanlış belirlemek

Taban durumları tüm yöntemin dayanağıdır. Başlangıç değerleri yanlışsa, onlardan kurulan sonraki her durum da yanlış olur.

Tabloyu yanlış sırada doldurmak

Tabulation, ancak her durum kendisinin bağlı olduğu durumlardan sonra doldurulduğunda çalışır. Yineleme bağıntısı doğru olsa bile, doldurma sırası yanlışsa yöntem başarısız olabilir.

Dinamik programlamanın her zaman optimizasyon anlamına geldiğini sanmak

Birçok ünlü örnek bir şeyi en büyük ya da en küçük yapar, ancak dinamik programlama sayma ve karar problemlerinde de kullanılır. Asıl işaret “en iyi” kelimesi değil, yeniden kullanılabilir alt problemlerdir.

Dinamik programlama nerelerde kullanılır?

Dinamik programlama; düzenleme mesafesi, en uzun ortak alt dizi, yol sayma, çanta tipi optimizasyon ve bazı en kısa yol durumları gibi problemlerde karşımıza çıkar.

Bunu denemeye karar verirken kendinize iki soru sorun:

• küçük alt problemler tekrar ediyor mu?
• daha büyük cevap, bu küçük cevaplardan kurulabiliyor mu?

Her iki sorunun cevabı da evetse, dinamik programlama güçlü bir adaydır.

Benzer bir problem deneyin

Her hareketin ya $1$ adım ya da $2$ adım olduğu durumda, $n$ basamağı çıkmanın kaç farklı yolu olduğunu kendi başınıza deneyin. Yineleme bağıntısı basittir, tekrar eden alt problemleri fark etmek kolaydır ve Fibonacci’den sonra iyi bir sonraki örnektir.