5 min read

Dynamic Programming nedir?

Bu yazıda Dinamik Programlama kullanarak sık rastlanan optimizasyon problemlerinde nasıl performans kazanıldığını göreceğiz.

Dinamik programlama, bir problemi daha ufak problemlerin çözümlerini kullanarak daha hızlı çözmeyi sağlayan bir optimizasyon yöntemidir.

Örneğin Türkiye'ye yeni bir il kazandırılacağını duyduğumuzda bunun plaka kodunun 82 olacağını hemen söyleyebiliriz. Çünkü ülkemizdeki bütün illerin sayısını toplamının 81 olduğunu önceden biliyoruz. Bu yüzden bütün illeri sayıp üzerine bir ekleyerek 82 sayısına ulaşmak yerine 81+1=82 şeklinde hızlı bir cevap verebiliyoruz.

İşte bu şekilde daha önce yapılmış olan hesaplamaları kullanarak çözülen problemlerde dinamik programlama kullandığımızda tekrar tekrar aynı işlemleri yapmaktan kaçınarak zaman kazanırız.

Dinamik programlama vs. böl ve yoket yöntemi

İlk bakışta dinamik programlama böl ve yoket (divide and conquer) yöntemine çok benzer. Fakat arada bir nüans farkı bulunuyor: böl ve yoket yönteminde bir problemi küçük parçalara (sub-problem) böldüğünüzde bu küçük parçaların hepsini teker teker hesaplarsınız. Bu sırada bazen aynı parçaları tekrar tekrar hesapladığınız da olur. Bu açıdan bakıldığında bir miktar zamanı boşa harcadığınız ortaya çıkar.

Dinamik programlamada her küçük parçanın sonunu ezberler ve aynı parçaya rastladığınızda bu ezberinizdeki değeri yazıp geçersiniz. Bu şekilde aynı parçayı asla iki kez çözerek zaman kaybetmezsiniz.

Eğer elinizdeki problemde aynı parçaların hesaplanması durumu sıklıkla karşınıza çıkıyorsa bu DP ile önemli bir zaman kazancı elde edebileceğiniz anlamına gelir.

Dinamik programlamanın maliyeti

Dinamik programlama çok avantajlı görünse de, yukarıda bahsettiğimiz parçaları ezberlemenin de bir maliyeti olacaktır. Yani çözdüğünüz problemde bu yöntemi kullanarak kazanacağınız zamanın ezberleme maliyetini aşması gerekiyor. Aksi halde optimizasyon yapmaya çalışırken performans kaybına sebep olabilirsiniz.

Dinamik Programlama ne zaman kullanılır

Dinamik programlama ile her problemi optimize edemeyiz. Bunun için problemin temel bazı özelliklere sahip olması gerekir.

1.Aynı parçanın tekrar etmesi (overlapping subproblems)

Yukarıdaki 82. il örneğinde olduğu gibi, problemi çözerken daha önceki hesaplardan yararlanabiliyor olmamız gerekir. Eğer elinizdeki problemde alt parçaların hesapları tekrarlanmıyorsa DP'nin size bir faydası olmaz.

Binary search yani ikili aramada ise alt parçalardan yararlanılmaz. Bu yüzden bu tarz problemleri çözmek için DP kullanmanın bir anlamı yoktur.

2. Parçaların toplamını kullanarak elde ettiğimiz çözümün optimal çözüm olması (optimal substructure)

Bazı problemlerde bu şekilde alt parçaları toplayarak bulduğunuz sonuç en ideal sonuç olmayabilir. Bu gibi durumlarda DP ile optimal çözüme ulaşamazsınız.

Örneğin bir grafta en kısa yolu bulmak için DP kullanabilirken, en uzun yolu bulmak için kullanamıyoruz. Bunun sebebi bir graftaki en kısa yol parçalarının birleşimi bize en kısa yolu verirken, en uzun yol parçalarının en uzun yolu vermemesidir.

Özetlemek gerekirse, DP sadece belirli bir problem tipinde avantaj sağlayan bir optimizasyon yöntemidir. Elinizdeki problem mutlaka tekrarlayan alt parçaların ezberlenip birleştirilmesi yöntemiyle ideal sonuca ulaşılan bir problem olmalıdır. Ancak bu şartlar gerçekleşirse DP ile performans kazancı elde edebilirsiniz.

Dinamik Programlama ile çözülebilen problemler

Aşağıdaki listede DP ile çözülebilen problemleri inceleyebilirsiniz. Bunlar ilk bakışta ip kesme, harf dizme, yol çizme gibi çok farklı problemler olarak görünse de, temele indiğiniz zaman hepsinin aynı problemin kelime oyunlarıyla gizlenmiş versiyonları olduğunu fark edeceksiniz.

Bunların tümü gerçek hayatta sıkça rastladığımız optimizasyon yani en iyiyi, en büyüğü, en ucuzu, kısacası en ideali bulma problemleridir. Ve en ideal eşleşmeyi veya grubu bulabilmek için de farklı varyasyonları hesaplamanızı gerektirirler.
  • Longest Common Subsequence
    • Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.
  • Longest Increasing Subsequence
    • The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
  • Edit Distance
    • Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’. Operations: Insert,Remove,Replace. All operations are of equal cost.
  • Minimum Partition
    • Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
      If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) – sum(Subset2)) should be minimum.
  • Ways to Cover a Distance
    • Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.
  • Longest Path In Matrix
    • Given a n*n matrix where all numbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1. We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.
  • Subset Sum Problem
    • Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
  • 0-1 Knapsack Problem
    • Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
  • Shortest Common Supersequence
    • Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
  • Partition problem
    • Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is the same.
  • Rod Cutting
    • Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
  • Coin change problem
    • Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
  • Word Break Problem
    • Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
  • Maximal Product when Cutting Rope
    • Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters.
  • Dice Throw Problem
    • Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
  • Box Stacking
    • Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.
  • Tower of Hanoi
  • All pair shortest path by Floyd-Warshall
  • Shortest path by Dijkstra
  • Project scheduling

Son söz.

Bu yazıda algoritmaların geliştirilmesi ve analizinde önemli bir yer tutan optimizasyon için kullanılan Dinamik Programlama yönteminden bahsettik.

DP'nin her durumda kullanılamasa da, doğru yerde uygulandığı taktirde büyük performans kazançları elde edilebilen bir yöntem olarak hafızanızda yer etmesini umuyorum.

DP aynı zamanda yapay zeka algoritmalarında da kullanılan bir yöntemdir. Bir çok yapay zeka metodu DP mantığı üzerine inşa edilmiştir.

Siz de örnek problemlerden bir kaç tanesini çözdükten sonra DP uygulanabilen problem tipine aşina olacaksınız. Faydalı olması ümidiyle, hoşçakalın.