Dinamik programlama

Vikipedi, özgür ansiklopedi
Gezinti kısmına atla Arama kısmına atla

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ış[değiştir | kaynağı değiştir]

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.

Kaynakça[değiştir | kaynağı değiştir]

  1. ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms (3 bas.). MIT Press. s. 359. ISBN 9780262033848. Erişim tarihi: 23 Ocak 2018. 
  2. ^ Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001), Introduction to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 0-262-03293-7 . pp. 344.