Dinamik programlama, temel ilkeler

Yaparken en uygun çözümü seçmek içinprogramlama görevleri bazen, kişisel bilgisayarın belleğini yükleyen çok sayıda veri kombinasyonundan geçmek zorunda kalmaktadır. Bu gibi yöntemler, örneğin "böl ve fethet" programlama yöntemini içerir. Bu durumda, algoritma görevin bireysel küçük alt görevlere ayrılmasını sağlar. Bu yöntem yalnızca küçük alt görevlerin birbirinden bağımsız olduğu durumlarda kullanılır. Alt görevlerin birbirine bağlı olması durumunda gereksiz çalışmaları yapmaktan kaçınmak için, 1950'lerde Amerikan R. Bellman tarafından önerilen dinamik programlama yöntemi kullanılır.

Metodun özü

Dinamik programlama, n-boyutlu sorunun optimal çözümünün belirlenmesinden oluşur, n ayrı adımlara bölünür. Her biri bir değişkene göre bir alt görevdir.

Bu yaklaşımın en büyük avantajıgeliştiricilerin n-boyutlu problem yerine alt görevlerin bir boyutlu optimizasyon görevleriyle uğraştığını ve ana görevin çözümü "alttan yukarıya" doğru ilerlediğini düşünüyorlardı.

Dinamik kullanmak uygun olur.alt görevlerin birbiriyle ilişkili olduğu durumlarda programlama, ör. Ortak modüller var. Algoritma alt görevlerin her birine bir kez çözüm getirir ve yanıtlar özel bir tabloya kaydedilir. Bu, benzer bir alt görevle karşılaşıldığında cevabı tekrar hesaplamamayı mümkün kılar.

Dinamik programlama görevinin çözümüoptimizasyon sorunu. Bu yöntemin yazarı olan R. Bellman, optimallik ilkesini formüle etmiştir: her aşamadaki başlangıç ​​durumu ve bu adımda belirlenen çözüm ne olursa olsun, aşağıdakilerin hepsi, sistemin basamağın sonunda aldığı duruma göre en uygun olacak şekilde seçilmiştir.

Bu yöntem, değişkenleri veya özyinelemeleri araştırarak çözülen görevlerin performansını artırır.

Problemin algoritmasının oluşturulması

Dinamik programlama varsayılırgörevin iki veya daha fazla alt görevlere ayrıldığı problemler için bir algoritma inşası, böylece onun çözümü, içinde bulunan bütün alt görevlerin en uygun çözümünden oluşturulabilir. Ayrıca, bir yineleme ilişkisi yazmak ve sorunun parametresinin optimal değerini bir bütün olarak hesaplamak gerekir.

Bazen, üçüncü adımda, her bir alt görevin ilerlemesiyle ilgili ilave yardımcı bilgileri de hatırlamanız gerekir. Buna tersi denir.

Yöntemin uygulanması

Dinamik programlama iki karakteristik özellik olduğunda kullanılır:

• alt görevler için optimizasyon;
• Problemde üst üste gelen alt görevlerin varlığı.

Optimizasyon problemini metot ile çözmeDinamik programlama, öncelikle çözümün yapısını tanımlamanız gerekir. Sorun, çözümün kendi alt görevlerinin en uygun çözümlerinden oluşması durumunda problemdir. Bu durumda, dinamik programlamanın kullanılması tavsiye edilir.

Sorunun ikinci özelliği, verilen biryöntem, az sayıda alt görev. Sorunun özyinelemeli çözümü aynı üst üste binen alt görevleri kullanır ve bunların sayısı orijinal bilginin büyüklüğüne bağlıdır. Cevap özel bir tabloda saklanır, program bu verileri kullanarak zaman kazandırır.

Dinamik kullanımıGörev esasen aşamalarında kararlar gerektiğinde programlama. Örneğin, ekipmanın değiştirilmesi ve onarılması görevinin basit bir örneğini düşünün. iki farklı formlarda lastiği üretmek aynı anda lastiklerin üretimi için döküm makinesi fabrikaya diyelim. Formlardan birinin başarısız olması durumunda, makineyi sökmeniz gerekir. Bazen daha karlı değiştirip durumda makineyi sökmek için ikinci bir formu ve bu formun bir sonraki aşamada işlemez olacaktır etmek anlaşılabilir. Ayrıca, her iki çalışma formunun da başarısızlığa başlamadan önce değiştirilmesi daha kolaydır. Devam sömürü biçimlerinin, makine kesintiler, atılan lastikler ve daha maliyeti kaybı faydaları: Dinamik programlama metodu dikkate bütün faktörleri dikkate alarak bu formların değiştirilmesi konusunda en iyi stratejiyi belirler.