Dinamik Programlama

Dinamik programlama, karmaşık problemlerde, o problemi kendi içerisinde tekrarlayan alt problemlere bölerek elde edilen sonuçları kaydeden, bu sonuçlarla tümdengelim-tümevarım yaklaşımlarıyla asıl problemi çözmeye yarayan bir yöntemdir. Alt problemlerin çözümünü kaydettiği için, aynı işlemlerin tekrar hesaplanması ihtiyacını ortadan kaldırarak kod maliyetini düşürür.Örneğin, Faktöriyel hesaplama işlemini düşünün. Her sayının faktöriyeli, kendisi ile birlikte 1’e kadar bütün sayıların çarpımına eşittir. Bu da aynı zamanda, bir sayının kendisi ile kendinden önceki sayının faktöriyeli çarpımına denk gelir. Dinamik programlama ile çözecek olursak, 1’den başlayarak her sayının faktöriyelini tutmak, bir sonraki sayı için sadece 2 değerin çarpımıyla sonucu elde etmemizi sağlayacaktır. Dinamik programlamanın, aşağıdan yukarıya ve yukarıdan aşağıya olarak yorumlanabilen iki metodu vardır. Brute force yinelemeli çözüm bularak başladığımız bu çözümde memoization ya da tabulation(tablo) ile yorumlayarak Dinamik Programlama ile en verimli çözümü bulmaya çalışırız.

Dinamik Programlama Metotları Hakkında

Küçük problem parçalarının çözümlerinin bilinip yorumlanarak çözümün kolaylaştırıldığı dinamik programlama yorumuna memoization denir. Memoization yukarıdan dibe bir yaklaşımdır. Çözümün küçük parçalarının tablo ile yorumlanarak dipten yukarı yaklaşımla incelendiği metoda ise tabulation denir. Bunlar çeşitli soru tiplerine çeşitli yorumlamalar getirmemizi sağlar ve işimizi bir hayli kolaylaştırırlar.

Dinamik Yaklaşım Nasıl Oluşturulur?

Dinamik Programlamayı kurabilmek için birkaç adıma ihtiyaç duyarız. Bunlar şu şekilde özetlenebilir:

• Dinamik Programlamayı temel mantığından da tahmin edebileceğimiz üzere önce küçük parçalar haline getiririz.

• Alt problemler üzerinde çözümleri yorumla böylece her adımda verilmesi gereken kararları hazırla.

• Asıl problemini üst adımları tekrarlayarak yorumla yani elinde birinde küçük parçalar haline getirdiğin birinde ise matematiksel halde karar mekanizman için yorumladığın verilerin var. Bu verilerle ana problem nasıl çözülür sorusuna kafanı yor.

• Memoization ya da tabulation üzerine yoğunlaş.

• Tüm bu verileri koda dökmeye uğraş.

Ana teması bu şekilde kurulabilen Dinamik Programlama, sorular, yaklaşımlar ve vakalar üzerinde bu yol haritası üzerinden farklılaşabilir. Bilinen Dinamik Programlama örneklerini bir sonraki konu başlığında anlatmaya gayret edeceğim.

Bilinen Dinamik Programlama Çözümleri

Dinamik Programlama sayesinde optimal çözüm elde edilen ve sonrasında çözümü formalize edilen bir konu ile başlayalım;

Matrix zincir çarpım hesapları. Bize verilen bir matrix zincir çarpımında parantezleme yani işlem önceliğini nereye vermemiz gerektiğini hesaplamamız gerekir. Bunun çözümüne Dinamik Programlama ile kolayca ulaşabiliriz. Matematiksel olarak kare matrixler ikili halde çarpılabilmektedirler ve yanlış bir işlem önceliği çok daha fazla hesaplama işlemine sebep olacağından dolayı sistemi bir hayli yavaşlatmacaktır. Tablo doldurarak optimal çözüme kolaylıkla Dinamik Programlama sayesinde ulaşır parantezlemeyi böylece yaparız. Tekrarlı çözüm içerisinde uygun ve uygun olmayan kondisyonların kontrolü bizim için yeterli olacaktır. Biraz da memoization üzerine kafa yormakta fayda var. Normalde dipten yukarı doğru bir yaklaşım olan(bottom up) Dinamik Programlamada, yukarıdan dibe (top down) bir strateji geliştirmenin gerektiği noktalarda genellikle memoization çözümleri daha verimlidir. İkinci çözüm örneğimiz en uzun benzer parça bulabilme üzerine. O da ne dediğinizi duyar gibiyim. İki array düşünün bu array ler harflerden oluşuyor ve bu arrayler arasındaki en uzun benzer elemanlar serisini bulmamız istenmiş. Ayrıca verimli bir çözüme ihtiyacımız olmuş, bu durumda Dinamik Programlama’nın bize faydası olacaktır. Dinamik çözümde tuttuğumuz tablo ile genel çözüm yaklaşımımızı kullanarak en uzun seriyi bulabiliriz. Dinamik programlama için genel çözüm yaklaşımımız şu şekildedir;

0 geçersiz durumlar

C[i,j]= C[i-1,j-1] alamıyorum

Max/Min(C[i-1,j-1],C[i-1,j-1]+V[1]) karar

Alamıyorum durumu tablonun önceki değerinin kullanılması gerektiği durumdur. Alamıyorum, elimdeki mevcut sayının ,paranın ya da yük miktarının(soruya bağlı) karşılamaya yeterli olmadığı durumda tercih yapmaya kalmadan zorunlu olarak önceki tablo değerinden devam ettiğim durumdur. Karar ise önceki tablo değeri ile mevcutta bu ürünü alırsam, bu adımı gerçekleştirirsem durumunun karşılaştırılıp maximum isteniyorsa büyük olanın, minimum isteniyorsa küçük olanın alınması durumunu temsil eder.

Bu yaklaşımı sorumuza entegre edebiliriz, örneğin seri benzerlik için,

0 geçersiz durumlar

C[i,j]= C[i-1,j-1]+1 liste elemanları aynı

Max(C[i,j-1],C[i-1,j]) karar

Böylece tablomuz oluşturulur dikine elemanlar bir listeyi yatay elemanlar bir diğer listeyi tutar ve karşılaştırılarak tablo oluşturulur.

Ve tabiki meşhur Knapsack problemine değinmeden olmaz. Bu problem mevcut bir hacme sahip çantamıza ortadaki nesne opsiyonları içerisinden hangilerini seçerek en değerli yükü oluşturabilirim üzerine modellenmiştir. Nesnelerin birtakım değerleri ve birtakım hacimleri vardır çantamızda yer tutacaklardır ancak bize değer getirisi olacaktır. Bu soru modelinin iki türü vardır birisi nesneleri parçalayamadığımız yani 0-1(binary) ile temsil edilen Dinamik Programlama ile çözülebilen tür, bir de Açgözlü Yaklaşım ile çözülebilen nesneleri parçalayabildiğimiz kısmen hesaba katabildiğimiz tür. 0-1 olanını yorumlamak için, 0 nesneyi almadığımızı 1 ise aldığımızı temsil etmektedir. Bunun için Dinamik Programlama çözümü şu şekilde söylenebilir:

0 geçersiz durumlar

C[i,W]= C[i-1,W] ürünün ağırlığı kalan ağırlık hakkından fazlaysa

Max(Vi + C[i-1,W-Wi],C[i-1,W]) değilse, getirilerini kıyaslamak için

0 değeri geçersiz durumlar için konmuştur, yani nesne 0 sa ya da ağırlık 0 sa. Ürünün ağırlığının çantamda kalan ağırlık limitinden fazla olduğu durumlarda değerleri kaydettiğim array içerisinden bir önceki değerin devam etmesi gerekir bunun için

C[i-1,W] dönmektedir. Karar kısmında ise elime gelen nesne çantamda kalan ağırlık limitine uygundur ancak almak mantıklı mıdır bunun ayırdına varılır, buna göre o ürünün değeri(Vi) eklenerek değerler karşılaştırılır, böylece maksimum değer içeren durum hesaplanılır.

Knapsack sorusunu temsilen görsel örneği.

Dinamik Programlama ile Böl ve Yönet Algoritma Yaklaşımları Karşılaştırması

Böl ve Yönet yaklaşımı detaylı bir şekilde başka bir yazının konusu olabilir ancak kısaca şu şekilde özetleyebiliriz;

Böl ve Yönet problemleri daha küçük parçalarına bölerek çözmeye yani yönetmeye dayalı bir yaklaşımdır .Bunun için recursive yani tekrarlı yaklaşım kullanılır, böylece problem nispeten daha kolay çözülebilecek küçük parçalar haline getirilir sonrasında ise tabiri caizse yönetmek daha kolay olacaktır. Bu ufak problemler tekrarlı halde çözülür ve çözümleri bir araya getirilir.Bu şekilde problemimiz ufak parçalara bölünerek tekrarlı halde çözülmüş ve bir araya getirilerek arzu edilen çözüm elde edilmiş olunur.

Dinamik Programlamada ise verimlilik de göz önüne alınır ve küçük problem parçaları yalnızca bir kez çözülür. Problemimiz Böl ve Yönet’teki gibi küçük parçalar halinde düşünülür elbet yani yaklaşım bu şekildedir. Ancak küçük problemlerin getirisi olan çıktılar bir tablo içerisinde tutulur ve yorumlanır. Kodlama esnasında bu tablo yaklaşımı genellikle bir array, liste ya da hash tablosu vaziyetindedir. Böylece ufak çözümler oluşturulmuş ve talep olunan sonucun iyisi için kolaylıkla tercih yapılabilmiş olur. Memoized edilen çözümleme ile vaka üzerinden çok daha hızlı sonuçlar alınabilir. Örneğin, çok meşhur bir yorumlama olan Fibonacci sayılarını alalım. Böl ve Yönet için ilk 2 adımı initialize ettikten sonra(F1=F2=1) formülize halde implemente edebiliriz. Naive algoritması üzerinden yorumlayarak, karmaşıklık analizini T(n) = T(n-1) + T(n-2) + O(1) bulabiliriz.

Böylece Böl ve Yönette genel karmaşıklık analizi olan;

T(n) = 2T(n-2) + O(1) ve bu durum için exponential time olarak yorumlanır, bu da gayet yavaş çalıştığı anlamına gelmektedir.

Ek bilgi olarak Böl ve Yönet’te 2T(n-k) lı kısım bölünmüş küçük/alt problemlerin karmaşıklığını temsil ederken O(n) li kısım conquer yani problemi kendi içinde çözme zamanını temsil eder.

Dinamik Programlama için memoize edilmiş çözüm yorumlamasıyla, bir adet if else yapısı ile Fibonacci serimizi hesaplayabiliyoruz. Yani çözüm karmaşıklık analizimiz,

T(n) = T(n-1) + O(1) halde oluyor ki bu da bu durum için O(n) e eşit yani linear time, bu da gayet hızlı çalıştığını gösterir.

Sonuç olarak özetlemek gerekirse, Böl ve Yönet alt problemler üzerinde daha çok iş yapar bundan dolayı daha çok zaman tüketir, ayrıca alt problem çözümleri birbirinden bağımsız haldedir. Tam tersine Dinamik Programlamada, alt problemler birbirine bağımlı haldedir ve yalnızca bir kez çözümlenirler sonrasında ise tabloya kaydedilip çözümde kullanılırlar, böylece verimliliği yükseltirler.