Dinamik Programlama ve Yöntemleri

Dinamik Programlama ve Yöntemleri

Dinamik programlama ve yöntemleri, karışık ve çok işlemli problemleri tekrar eden, alt problemlere parçalayarak her bir alt problemi bir kere çözüp sonrasında bu problemin daha kolay bir çözüme ulaşılmasını sağlayan yoldur. Karmaşık problem, alt problemlere çevrilerek çözüldüğünde zaman açısından tasarruf sağlanır. Bununla birlikte daha çok boş alan gerekir. Kısaca depolama alanının bir kısmından feragat edilerek zaman tasarrufu sağlar. Çoğu optimizasyon probleminin çözümü için bu yöntem kullanılır. Aynı işlemlerin tekrar hesaplanması zahmetini ortadan kaldırarak kod maliyeti açısından da tasarruf sağlanır.

Dinamik programlama nedir sorusunun diğer bir cevabı, bir hat üzerinde bir yerden diğer bir yere giden en kısa yolu özyineleme tekniği ile bulmaktır. Dinamik programlama yöntemleri kullanılarak çeşitli algoritmalardaki problemler kolayca ve hızlıca çözülür. Bu yöntem tümevarım ve tümdengelim yaklaşımları ve teknikleri ile karmaşık problemleri çözer. Bu sayede kişilerin karmaşık olan problemi daha anlaşılır hale getirme konusundaki sorunu ortadan kalkmış olur. Problemler çözümlenirken karakteristik özellikleri değişmeden çözümlenir. Bu sayede istenilen problemin tam anlamı ile başka konulara sapmadan çözümlenmesi sağlanır. 

Dinamik programlama yöntemi konusunda, en ideal çözüm, en baştaki problemden bağımsız olan alt problemlerin ardışık bir şekilde ana problem için en ideal çözümü bulmasıdır. Diğer bir anlatımla, en başta alttaki sorunlar çözülerek buradan elde edilen veriler ışığında diğer asıl problemin çözümü sağlanır. Bu sayede küçük parçalardan bir bütün elde edilerek çok daha hızlı ve pratik şekilde sorunlar çözülmüş olur.

Dinamik Programlama Yöntemleri ve Kullanış Biçimi

Dinamik programlama yöntemleri, çeşitli metotlar kullanılarak problemlerin çözümü için kullanılır. Küçük problemlerin çözümleri bulunup bir üst veri elde edilerek ana problemin çözülmesi metodu yorumuna memoization adı verilir. Bu yöntemde üst veriden başlanıp aşağılara inilerek çözümleme yapılır. En alt parçalardan üst verilere ve çözümlere doğru çıkmaya ise tabulation denir. Bu yöntemler sayesinde yapılacak işler ve çözülecek sorunlar fazlasıyla kolaylaşır. 

Dinamik programlama, memoization yani not alma işlemi sayesinde işlemler devam ederken bir önceki işlemi depolama sisteminde hafızaya alır. Bu sayede her işlem bir kere tekrarlanmış olur. Zaman ve iş gücünden tasarruf sağlanır. Bu önbelleğe alma işlemi sayesinde, bilgisayar programlarının daha hızlı ve daha verimli çalışması sağlanır. Bu da doğru orantılı olarak bilgisayarın daha optimizasyonlu çalışmasını sağlar. Bu durum dinamik program dilleri açısından tablolama işlemi olarak da bilinir. 

Önbelleğe alınmış bir işlev, sisteme gelen özel girdi verilerine göre çıkacak sonuçları hatırlar ve bu sayede bu sonuçları yeniden analiz edip hesaplamak yerine hatırlanmış olan sonucu veri olarak sunar. Bu not alma işlemi sayesinde, zaman ve iş maliyeti açısından çeşitli kazanımlar sağlanır. Bellek kullanımı her ne kadar artsa da kazanılan optimizasyon sayesinde bilgisayarlar çok daha hızlı çalışır. Elde edilecek olan bu hız kullanıldığı alanlarda maddi kazanç anlamında oldukça fayda sağlar. Bilgisayarlarda tüm işlevler, zaman ve uzay bakımından bir hesaplama karmaşası içindedir. Bu işlemlerin yanı sıra, problem çözümünde kullanılan karmaşık çarpma işlemleri yerine kullanmış olduğu toplama işlemi ile çözümü kolaylaştırır. 

Diğer bir çözümleme yöntemi, zincir matris çarpımı işlemidir. Bu işlemler içerisinde, işlem sırası önceliği sorunun çözülmesidir. Bu sorunun çözümüne dinamik programlama yöntemi ile varmak mümkündür. Bu matrisler, matematik işlemleri aracılığı ile ikili olarak çarpım işlemi yapılarak çözülebilir. Ancak, bu yol çok uzun ve zor bir yoldur. Bu durum da bilgisayar sistemlerini gözle görülür şekilde yavaşlatır. Tablo yapma sistemi sayesinde dinamik programlama sistemleri bu sorunu çözerek bilgisayarın optimize çalışması için kullanılır. Bu sistem, parantezleme ve işlem önceliği sorununu hızlı bir şekilde çözer.

Dinamik Programlama Yöntemlerinin Türleri ve Özellikleri

Dinamik programlama, daha küçük alt problemlere ayrılabilen her problemin çözümü için kullanılabilir. Dinamik programlama yöntemlerinin iki ayrı başlık altında incelenmesi mümkündür. Bu durumun tabanında yatan farklılık, dönüşüm fonksiyonlarının çeşididir. Problem çözme sürecinde işlemler rassal bir biçimde çözülebiliyorsa determinist karakterde bir problem vardır. 

Diğer bir durumda ise dinamik yapılı problemler ile karşı karşıya kalınabilir. Bu sürecin sonunda ortaya çıkan çözümler de sonludur. Yani bu problemlerin önceden de bilinen belli çözümleri vardır. Bazı süreçler ise sonsuz yapıdadır. Bu süreçlerin çözümleri de aynı şekilde sonsuz olarak devam eder. Yukarıda bahsedilen türler şu şekildedir:

•  Deterministik (belirlenim) dinamik programlama sistemi; bir sonraki aşamada ne olacağı ve sonuç durumu daima dış etkenler tarafından ayarlanır. Diğer bir anlatımla, problem çözüm sürecinin tüm aşamaları dış etkenler bütünüyle hakim olunan sistemlerdir.
   
•  Stokastik (olasılıklı) dinamik programlama sistemi; bu tür sistemlerde bir sonraki adım ve anlık durumlar dış etkenler tarafından bilinemez veya belirlenemez. İleriki aşamalarda ne olacağı konusunda bilinen tek durum olasılıklardır. Bu olasılık dağılımı dış etkenler tarafından bilinebilir veya belirlenebilir şekilde dağılır. 

Bütün bu yöntemler, problemlerin tek bir yöntem ile çözülmesini sağlayan işlemlerdir. Oluşan tüm problemler tek tek analiz edilerek hepsinin çözümü ve denklemi kurulur. Çok aşamalı karar verme problemleri açısından tek bir problem yaratarak buna uygun çözümün bulunması bu sistemler aracılığı ile olur. Bu çözüm sürecinde meydana gelen periyotlar, sürekli olarak birbirine bağlıdır ve bunun sonucu olarak diğer bir başka problemin çözülmesinde kullanılabilir. Bu sistemlerin bazı özellikleri aşağıdaki gibidir:

•  Problemler, sistemi yöneten kişinin istediği kadar parçaya ayırır. Bu sayede istenen optimizasyon sağlanır. 
   
•  Her çözüm evresinin kendi özel çözümü olmalıdır. Diğer alt problemler ile bağlı olmayan çözümler için bu durum önem arz eder.