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.^[1] 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.^[2] 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₁, V₂, ..., 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 = n −1, n − 2, ..., 2, 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 − 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₁ 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.^[3]

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 <= 1 döndür n
    döndür fib(n − 1) + fib(n − 2)

Bu program ile 5. Fibonacci sayısının bulunması aşağıdaki özyinelemeleri içerir:

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

^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms (3 bas.). MIT Press. s. 359. ISBN 9780262033848. 10 Şubat 2023 tarihinde kaynağından arşivlendi. Erişim tarihi: 23 Ocak 2018.
^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, 0-262-03293-7 . pp. 344.
^ Sniedovich, M. (2006). "Dijkstra's algorithm revisited: the dynamic programming connexion" (PDF). Journal of Control and Cybernetics. 35 (3). ss. 599-620. 15 Şubat 2020 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 6 Mart 2020.

Bilgisayar ile ilgili bu madde taslak seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz.

[cormen-1] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms (3 bas.). MIT Press. s. 359. ISBN 9780262033848. 10 Şubat 2023 tarihinde kaynağından arşivlendi. Erişim tarihi: 23 Ocak 2018.

[:0-2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, 0-262-03293-7 . pp. 344.

[sniedovich_06-3] Sniedovich, M. (2006). "Dijkstra's algorithm revisited: the dynamic programming connexion" (PDF). Journal of Control and Cybernetics. 35 (3). ss. 599-620. 15 Şubat 2020 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 6 Mart 2020.

[1]

[2]

[3]