Dinamik Programlama nedir?

Bilgisayar programlama söz konusu olduğunda, dinamik programlama matematiksel olduğu kadar çok yönlüdür. Richard Bellman, tekniği 50'lerde yarattı ve o zamandan beri havacılık mühendisliğinden ekonomiye kadar her alanda kullanım alanı buldu.

Her iki bağlamda da kelime, karmaşık bir konuyu yönetilebilir parçalara ayırmayı ifade eder. Çok yıllı kararlar tipik olarak yinelemeli olarak parçalanır. Bilgisayar biliminde, bir konu, onu alt problemlere ayırarak ve yinelemeli olarak en iyi çözümleri bularak en uygun şekilde ele alınabiliyorsa, en uygun altyapıya sahiptir.

Eğer alt problemler ana problemin içinde özyinelemeli olarak iç içe geçirilebilirse ve ana problemi çözmek için dinamik programlama teknikleri kullanılabiliyorsa, ana sorunun değeri ile alt problemlerin değerleri arasında bir ilişki vardır. Optimizasyon alanında, Bellman denklemi, daha iyi strateji için bu özel bağlantı hakkında konuşmanın iyi bilinen bir yoludur.

Çevrimiçi kursların yardımıyla yazılım mühendisliğini öğrenebilirsiniz .

Matematiksel Optimizasyon

Dinamik programlamada yapıldığı gibi, karmaşık bir seçimi bir dizi artımlı seçime ayrıştırarak, matematiksel bir optimizasyon problemi operasyonlar için çok daha yönetilebilir hale getirilebilir. Bunu başarmak için, her biri 0'dan n'ye I zamanındaki belirli bir andaki sistemin durumunu açıklamak için y'yi argüman olarak alan bir dizi değer fonksiyonu V1, V2,…, Vn tanımlarız. Vn(y), y durumundan alınan n zamanındaki değerdir. Bellman denklemi olarak bilinen özyinelemeli bir bağlantı kullanarak, önceki I = n1, n2,…, 2, 1 periyotlarındaki Vi değerlerini belirleyebiliriz. zaman I 1 ve Vi fonksiyonu sistemin yeni durumunda, I = 2,…, n olmak üzere Vi'den herhangi bir y durumunda Vi1 türetebiliriz. Bu prosedür, gerekli durumlar için Vi1'i döndürür, çünkü Vi zaten onlar için hesaplanmıştır. Son olarak, optimal çözüm değeri olan V1, sistemin başlangıç ​​koşulunda bulunur. Daha önceki hesaplamalardan adımların izini sürerek, seçim değişkenlerinin optimum değerleri birer birer elde edilebilir.

Dinamik programlamanın yararlı olabilmesi için, bir problemin iki özelliği olmalıdır: optimum bir alt yapı ve örtüşen alt problemler. "Böl ve fethet" terimi, bir zorluğun daha küçük, bağımsız problemlere bölündüğü ve daha sonra her birine verilen en iyi cevapların birleştirilerek çözüldüğü bir tekniği ifade etmek için kullanılır. Bu nedenle, birleştirme sıralamasını ve hızlı sıralamayı dinamik programlama zorlukları olarak görmüyoruz.

Bir yazılım mühendisliği sertifika programı becerilerinizi geliştirebilir.

Optimum alt yapıya sahip bir optimizasyon problemi, alt problemlerinin çözümleri birleştirilerek çözülebilir. İdeal alt yapılar genellikle özyineleme yoluyla tanımlanır. G=(V,E) grafiğindeki her bir ara tepe noktası, u tepe noktasından v tepe noktasına en kısa yolu p kazandı, optimal altyapıya bir örnektir. p yolu en kısaysa, iki yola bölünebilir, p1 u'dan w'ye ve p2 w'den v'ye, bunlar da ilgili köşe çiftleri arasında en kısa olanlardır. Bu nedenle, Bellman-Ford ve Floyd-Warshall algoritmaları en kısa yolları bulmak için özyinelemeyi kullanır.

Dinamik Programlama Yöntemi Kullanmanın Arkasındaki Mantık Nedir?

Dinamik programlama prosedürü aşağıdaki gibidir:

1. Bunu yaparken, orijinal sorunun tüm yönlerinin karmaşıklığını azaltır.
2. Bu küçük sorunları çözmek için mümkün olan en iyi yanıtı belirler.
3. Daha küçük zorluklara (not alma) yönelik çözümlerin kaydını tutar. Ezberleme, daha küçük problemlerin çözümlerini hatırlama eylemidir.
4. Sorunun aynı kısmı birkaç kez çözülebilecek şekilde onları geri dönüştürür.
5. Tüm bunlardan sonra, zor sorunun cevabını bulmanız gerekiyor.

1. Optimal alt yapılar ve örtüşen alt problemlerle ilgili sorunlar. Bu bağlamda, “optimal alt yapı” terimi, optimizasyon sorunlarının, en iyi çözümleri, onları oluşturan alt problemlere entegre ederek çözülebileceği bir yöntemi ifade eder.
2. Ara sonuçların saklanması gerektiğinden dinamik programlamanın alan karmaşıklığı, zaman karmaşıklığı azalsa bile artar.