Dinamik programlama

[bullvar_katip]

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, V, ..., V tanımlanır. Her V fonksiyonu sistemin 1'den n'ye kadarki her i anındaki durumuna bağlıdır. V fonksiyonu, sistemin son n anında, y durumunda aldığı değerdir. Daha erken V değerleri, nden geriye doğru (i=n−1,n−2,...,2,1) özyinelemeli Bellman denklemi kullanılarak hesaplanır. inin 1'den büyük değerleri için, Vin herhangi bir y durumundaki değeri i−1'de alınacak kararların kazancını maksimize ederek bulunur. V değeri zaten hesaplanmış olduğu için bu işlemle Vye 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. 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 ninci 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 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: Burada aynı değer defalarca sıfırdan hesaplanmaktadır. Örneğin, 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 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 eğer n eşleme m'de değilse m[n] := fib(n − 1) + fib(n − 2) döndür' m[n] Kaynakça Kategoriinamik programlama