Bu eğitimde, dinamik programlamanın ne olduğunu öğreneceksiniz. Ayrıca, problemleri çözmek için dinamik programlama ve açgözlü algoritmalar arasındaki karşılaştırmayı bulacaksınız.
Dinamik Programlama, üst üste binen alt problemlere ve optimal alt yapı özelliğine sahip bir problem sınıfını verimli bir şekilde çözmeye yardımcı olan bir bilgisayar programlama tekniğidir.
Bu tür problemler, optimum çözümü bulmak için aynı alt problemlerin değerini tekrar tekrar hesaplamayı içerir.
Dinamik Programlama Örneği
Fibonacci dizisini oluşturma durumunu ele alalım.
Dizi F (1) F (2) F (3)… F (50) ise, F (n) = F (n-1) + F (n-2) kuralını izler
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Örtüşen alt problemler olduğuna dikkat edin, hem F (50) hem de F (49) 'u hesaplamak için F (48)' i hesaplamamız gerekir. Bu, Dinamik Programlamanın parladığı türden algoritmadır.
Dinamik Programlama Nasıl Çalışır?
Dinamik programlama, alt problemlerin sonucunu depolayarak çalışır, böylece çözümleri gerektiğinde, onlar elinizin altında olur ve onları yeniden hesaplamamıza gerek kalmaz.
Bu alt problemlerin değerini saklama tekniğine hafızaya alma denir. Dizideki değerleri kaydederek, daha önce karşılaştığımız alt problemlerin hesaplamaları için zamandan tasarruf ediyoruz.
var m = harita (0 → 0, 1 → 1) fonksiyon fib (n) eğer anahtar n haritada değilse mm (n) = fib (n - 1) + fib (n - 2) return m (n)
Hafızaya alma yoluyla dinamik programlama, dinamik programlamaya yukarıdan aşağıya bir yaklaşımdır. Algoritmanın çalıştığı yönü tersine çevirerek, yani temel durumdan başlayarak ve çözüme doğru çalışarak, dinamik programlamayı aşağıdan yukarıya bir şekilde de uygulayabiliriz.
function fib (n) eğer n = 0 ise 0 döndür, else var prevFib = 0, currFib = 1 tekrar n - 1 kez var newFib = prevFib + currFib prevFib = currFib currFib = newFib dönüş akımıFib
Özyineleme ve Dinamik Programlama
Dinamik programlama çoğunlukla özyinelemeli algoritmalara uygulanır. Bu bir tesadüf değildir, çoğu optimizasyon problemi özyineleme gerektirir ve optimizasyon için dinamik programlama kullanılır.
Ancak özyinelemeyi kullanan tüm problemler Dinamik Programlamayı kullanamaz. Fibonacci dizi probleminde olduğu gibi üst üste binen alt problemler olmadığı sürece, özyineleme ancak çözüme böl ve yönet yaklaşımı ile ulaşabilir.
Birleştirme Sıralaması gibi özyinelemeli bir algoritmanın Dinamik Programlamayı kullanamamasının nedeni budur, çünkü alt problemler hiçbir şekilde üst üste binmez.
Açgözlü Algoritmalar ve Dinamik Programlama
Açgözlü Algoritmalar, her ikisinin de optimizasyon aracı olmaları açısından dinamik programlamaya benzer.
Bununla birlikte, açgözlü algoritmalar, küresel bir optimum bulma umuduyla yerel olarak en uygun çözümleri veya başka bir deyişle açgözlü bir seçimi arar. Bu nedenle, açgözlü algoritmalar, o anda en iyi görünen, ancak daha pahalı hale gelen ve küresel olarak optimum bir garanti sağlamayan bir tahminde bulunabilir.
Öte yandan dinamik programlama, alt problemlere en uygun çözümü bulur ve daha sonra en optimum çözümü bulmak için bu alt problemlerin sonuçlarını birleştirmek için bilinçli bir seçim yapar.
