Dinamik programlama

Bilgisayar bilimi, matematik, ekonomi ve biyoinformatikte **dinamik programlama** (ya da **dinamik optimizasyon**) karmaşık bir problemi tekrarlanan alt problemlere bölerek, her bir alt problemi yalnız bir kere çözüp daha sonra bu çözümü kaydederek karmaşık problemin çözümünde kullanma yöntemidir. Bir alt problem çözüldükten sonra tekrar çözülmesi gerektiğinde daha önce kaydedilen çözüm kullanılarak zaman kazanılır, ancak alt problemlerin kaydedileceği daha fazla alana gereksinim duyulur. Yani dinamik programlama algoritmaları alandan ödün verilerek zamandan kazanılmasını sağlar. Dinamik programlama algoritmaları optimizasyon problemlerinin çözümünde yaygın olarak kullanılır.

## Genel bakış
Dinamik programlama hem bir matematiksel optimizasyon hem de bir bilgisayar mühendisliği yöntemidir. Her iki bağlamda da karmaşık problemlerin özyinelemeli alt problemlere bölünmesini ifade eder.

Eğer alt problemler özyinelemeli olarak daha geniş problemlerle iç içe geçmişse daha geniş problem ile alt problemlerin değerleri arasında bir ilişki vardır. Optimizasyon literatüründe bu ilişki Bellman denklemi olarak adlandırılır.

### Matematiksel optimizasyon

Matematiksel optimizasyonda, dinamik programlama bir kararın daha küçük alt kararlar dizisine bölünerek basitleştirilmesidir. Bunu yapmak için bir **değer fonksiyonları** dizisi *V*1, *V*2, ..., *V**n* tanımlanır. Her *V**i* fonksiyonu sistemin 1'den n'ye kadarki her i anındaki durumuna bağlıdır. *V**n*(*y*) fonksiyonu, sistemin son *n* anında, *y* durumunda aldığı değerdir. Daha erken *V**i* değerleri, *n*'den geriye doğru (*i*&nbsp;=&nbsp;*n*&nbsp;−1,&nbsp;*n*&nbsp;−&nbsp;2,&nbsp;...,&nbsp;2,&nbsp;1) özyinelemeli Bellman denklemi kullanılarak hesaplanır. *i*'nin 1'den büyük değerleri için, *V**i*−1'in herhangi bir *y* durumundaki değeri *i*&nbsp;−&nbsp;1'de alınacak kararların kazancını maksimize ederek bulunur. *V**i* değeri zaten hesaplanmış olduğu için bu işlemle *V**i*−1'ye ulaşılabilinir. Son adımda bulunan *V*1 değeri, sistemin ilk anında *en iyi karar*ın alınması durumundaki kazançtır. Daha sonra, zaten yapılmış olan hesaplamalar geri sarılarak, her adımda alınacak en iyi kararların değerleri de bulunur.

## Örnekler

### En kısa yol problemi

Bir çizgedeki bir noktadan başka bir noktaya giden en kısa yolu bulma problemi dinamik programlama ile çözülebilir. 1956 yılında bulunan bu çözüm, mucidinin adıyla Dijkstra algoritması olarak bilinir.

Dijkstra algoritması, dinamik programlama yaklaşımına göre, bir P noktasından Q noktasına en kısa yolu bulmak için, P'den Q'ya en kısa yolun üzerinde bulunan her nokta için en kısa yolu bularak ilerler. Yani, P'den Q'ya en kısa yol ana problemi için, Q'dan daha yakındaki noktalardan P'ye en yakın yolların bulunmaları alt problemlerdir.

### Fibonacci dizisi

Fibonacci dizisinin *n*'inci sayısının bulunması probleminin doğrudan tanımını kullanmak yerine, dinamik programlama kullanmak daha hızlı sonuç verir. Doğrudan tanıma dayalı program:

 **fonksiyon** fib(n)
     **eğer** n fib(5)
# `fib(4) + fib(3)`
# `(fib(3) + fib(2)) + (fib(2) + fib(1))`
# `((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`
# `(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`

Burada aynı değer defalarca sıfırdan hesaplanmaktadır. Örneğin, `fib(2)` fonksiyonu 3 defa tekrar hesaplanmıştır. Bu durum, hesaplama süresinin, hesaplanan sayıyla üstel ilişkili bir şekilde büyümesine, yani büyük sayılar için bu hesaplamanın çok uzun sürmesine sebep olur.

Dinamik programlama kullanılarak, tekrar hesaplanan alt problemler hatırlanır ve büyük bir performans kazancı sağlanır. Bir **eşleme** fonksiyonu ile, hesaplanan her alt problemi hafızaya kaydeden aşağıdaki program yalnızca O(''n'') karmaşıklığa sahiptir. Yani çok daha büyük sayılar kısa zamanda hesaplanabilir.

 **değişken** m := ***eşleme***(0 → 0, 1 → 1)
 **fonksiyon** fib(n)
     **eğer** n ***eşleme*** m**'de değilse** 
         m[n] := fib(n − 1) + fib(n − 2)
     **döndür** m[n]

## Kaynakça