‘Çeviri’ kategorisi için arşiv.
Dinamik programlamaya giriş
Alttaki yazı Jesse Farmer'ın "Introduction to Dynamic Programming" adlı yazısının çevirisidir. Burada, yazarın izniyle yayınlanmaktadır.
Dinamik programlama, örtüşen altproblemler (overlapping subproblems) ve eniyi altyapı (optimal substructure) özelliklerini gösteren geniş bir yelpazedeki arama ve eniyileme (optimizasyon) problemlerini verimli bir biçimde çözmek için kullanılan bir yöntemdir. Size bazı basit örnekler aracılığıyla bu özellikleri göstermeye çalışacağım ve bir alıştırma ile bitireceğim. Mutlu kodlamalar!
Örtüşen altproblemler
Tekrar tekrar kullanılan altproblemlere bölünebilen bir problem için, örtüşen altproblemlere sahiptir denir. Özyineleme (recursion) ile yakından ilişkilidir. Farkı görmek için (Python ile) şu şekilde tanımlanan faktöryel fonksiyonunu düşünün:
def factorial(n):
if n == 0: return 1
return n*factorial(n-1)
Görüldüğü gibi factorial(n) probleminin hesabı factorial(n-1) altprobleminin hesabına bağımlıdır. Bu problem örtüşen altproblemler özelliğini göstermez çünkü factorial, n'den daha küçük her pozitif tamsayı için bir kez çağrılır.
