Dinamik Prgramlama

           DİNAMİK PROGRAMLAMA

Dinamik Programlama Bilgisayar Mühendisliğinde olsun gereksede diğer Mühendislik alanlarında olsun sürekli karşılaşılaşılan önemli bir algoritmadır öyleki  karışık problemlerin daha basit hale indirererek çözülmesi yönünde kolaylık sağlıyan yani bilgisayar Dili olarak söylemek istersem Optimizasyonunu sağlamaktadır

Dinamik programlama amaç problemin alt problemlere parçalayarak ve parçalarkende bir önceki konumunu kouycak şekilde parçalanır başka problemlere dönüştürülerek çözüme giden bir yol olmasıda bizim için yeterli ve aranan bir yoldur amaç zaten problemi çözmektir nasıl ki rekürsif fonksiyonları iteratife dönüştürüp oradan sonuça ulaşmaya çalışılıyorsa dinamikte kolaylık ya da başka forma dönüştürülüp çözme işini sağlamaktadır

Yönteme göre optimum çözüm başlangıç durumundan bağımsız olarak diğer çözümler ile çözüm sonuçlarına göre optimum çözümler birbirinin devamı şeklindedir yani önce alt probleme bölüp daha sonra daha detaylı alt problemler bölüp sonucu bulmaya çalışılıcak

Başka sorulacak soru peki bu Dinamik problemleri nerede kullanabiliriz ? bunun için şöyle söyleyebiliriz  çözümlü olarak daha küçük problemlere parçalanabilen tüm problemlere uygulanabilmekteyiz örneğin Fibonacci normal zaman karmaşıklı O(n^2) ike Dimaikle çözümlendiğinde O(n) yapılabilir bunun bize sağladığı yarar o kadar büyük ki neredeyse sorun yok denecek kadar hafife indirgenmiş oluyor bununla beraber.

Dinamik programlama uygulamalarımızda temel olarak 3 teknikten faydalanacağız:

·         Çözümü aynı olan alt-problemler

·         Büyük bir problemi küçük parçalara bölmek ve bu küçük parçaları kullanarak baştaki büyük problemimizin sonucuna ulaşmak

·         Çözdüğümüz her alt-problemin sonucunu bir yere not almak ve gerektiğinde bu sonucu kullanarak aynı problemi tekrar tekrar çözmeyi engellemek.

Şimdi örneğimiz olan fibonacci dizimize başlayalım. Fibonacci dizimizi kısaca bir hatırlayalım.

Eğer herhangi bir sayının Fibonacci karşılığına F(n) dersek,

F(0) = F(1) = 1 olmak üzere

F(n) = F(n-1) + F(n-2)’dir.

İlk yaptığımız prosesimizin fonksiyonunu hatırlayalım:

fib.cpp

1 2 3 4 5 6 7

// Recursive Function int fib(int num) {  if ((num == 0) || (num == 1))  return num;  else  return (fib(num - 1) + fib(num - 2)); }

Bu kadar kısa bir kod yazarak çözümü sağlamıştık. Ancak bu yöntem kodun kısa olmasına rağmen performans açısından kötü bir yöntemdir.  Nedenine gelirsek mesela F(3)’ü adım adım hesaplayalım:

F(4) = (F(2) + F(1)))

= ((F(1) + F(0)) + F(1)) + F(2)

= ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

Görüldüğü gibi F(4) değerini hesaplarken F(1)’ye 2 defa ihtiyacımız oldu ama 2 seferde de hesapladık. Prosesimizi değiştirerek bir de şu hale getirelim.

fib2.cpp

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

/*  *  * Program:  Fibonacci Series v2  * Programmer: Burak ISIKLI  *  */ #include <iostream.h> unsigned int fib2(unsigned int num); unsigned int fibArray[1000]; // Main Function int main() {  unsigned int number, result;  cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";  cin >> number;  result = fib2(number);  cout << "fib( " << number << " ) = " << result << "\n\n";  return 0; } unsigned int fib2(unsigned int num) {  unsigned int i = 2;  fibArray[0] = fibArray[1] = 1;  while(i <= num)  {  fibArray[i] = fibArray[i - 1] + fibArray[i - 2];  i++;  }  return fibArray[num]; }

Burada yaptığımız işlem ise şu. Hesapladığımız Fibonacci sayılarını bir diziye kaydediyoruz. Daha sonra lazım olunca bu değerleri direkt diziden hazır bi şekilde alıyoruz. Böylece aynı işlemi tekrar tekrar yapmaktan kurtuluyoruz.

Performans karşılaştırması yapacak olursak kendi bilgisayarımda fibonacci(50) 8dk. 36 sn’de sonuç verirken fibonacci2(50) 0.003 sn’de sonuç veriyor. Daha bilimsel konuşacak olursak problemi temelde aynı mantıkla çalışan iki fonksiyonun birincisi O(2^n) iken ikincisi O(n) zamanda çözmektedir.