Ders, dinamik programlama kavramını ve görünüşünün tarihsel yönünü ele alacaktır. Dinamik programlamanın sorunları ve çözümlerine ilişkin bazı örnekler ele alınmıştır.

"Dinamik programlama" kavramı ilk olarak 1940'larda Richard Bellman tarafından bir probleme çözüm bulma sürecini tanımlamak için kullanıldı, burada bir problemin cevabı ancak ondan "önceki" başka bir problem çözüldükten sonra elde edilebilir.
Böylece, Amerikalı bir matematikçi ve matematikte önde gelen uzmanlardan biri ve bilgi işlem teknolojisi — Richard Ernst Bellman- dinamik programlamanın atası oldu.

Daha sonra kavramın formülasyonu tamamlanmış ve geliştirilmiştir. modern görünüm Bellman'ın kendisi tarafından.

"Programlama" kelimesi"dinamik programlama" bağlamında, aslında klasik programlama anlayışına (bir programlama dilinde kod yazma) pratik olarak alakasız... "Programlama" kelimesi, "ifadesindeki ile aynı anlama sahiptir. matematiksel programlama", " Optimizasyon " kelimesi ile eş anlamlıdır.

Bu yüzden programlar probleme bir çözüm elde etmek için en uygun eylem dizisi olarak kullanılacaktır.

Genel olarak, bir başlangıç ​​için, dinamik programlamanın resmi olmayan tanımışöyle gelebilir:

Dinamik program Belirli bir özelliği olan (alt problemlerde en uygun olma özelliği) bazı kombinatorik, optimizasyon ve diğer problemlerin çözülmesine izin veren bir teknik veya yöntemdir.

Optimizasyon görevleri, kural olarak, bir veya başka bir amaç fonksiyonunu maksimize etme veya minimize etme sorunuyla ilişkilidir (örneğin, sistemin bozulmama olasılığını maksimize etmek, kar etme beklentisini maksimize etmek, vb.).

kombinatoryal görevler, kural olarak, belirli özelliklere sahip kaç tane nesne olduğu veya özelliklere sahip kaç tane kombinatoryal nesne olduğu sorusuna cevap verin.

Yani, DP tüm sorunları çözmez, sadece bazılarını çözer, belirli bir sınıf alt görevler. Ancak bu alt görevler sınıfı birçok bilgi alanında kullanılır: programlama, matematik, dilbilim, istatistik, oyun teorisi, ekonomi, bilgisayar Bilimi vesaire.

Dinamik programlama kullanılarak çözülen problemler, uyumlu olma özelliği, daha sonraki derslerde tartışılacaktır.

Alt problemlerin optimallik özelliğinin resmi olmayan bir açıklaması aşağıdaki şema kullanılarak gösterilebilir:
DP yardımıyla çözmek istediğimiz bir problem var, yani. çözmek için bir çeşit plan bul. Diyelim ki bu görev zor ve hemen çözemiyoruz. Küçük bir alt problem alıyoruz ve önce onu çözüyoruz (x1 için). Daha sonra bu küçük çözümü x1 kullanarak ve bu çözümün yapısını değiştirmeden aşağıdaki problemi zaten x1 ve x2 ile çözüyoruz. Vesaire.

Pirinç. 1.1. Alt problemlerin optimallik özelliğinin resmi olmayan açıklaması

Gayri resmi bir açıklama daha ayrıntılı olarak tartışılmaktadır.

Dinamik programlama problemleri kullanılarak çözülebilecek örnekler

İlk olarak, optimizasyon problemlerini düşünün (1-5 arası görevler):

1. Optimum rota uzunluğu

Örnek: Grafik olarak sunulan bazı yol haritası var. Amacımız: noktadan almak A işaret etmek B... Bu, mesafeyi veya harcanan yakıtı en aza indirecek şekilde yapılmalıdır.

hedef işlevi işte uzaklık Aönce B... Onlar. amacımız mesafeyi en aza indirmektir.

ve nedir seçim değişkeni? En kısa yolu bulmak için her seferinde kararlar vermek zorundasın. Onlar. her noktada veya her kavşakta kararlar alınmalıdır: nereye dönülmeli veya düz gidilmelidir.

Önemli: Bu görevden zaten görebilirsiniz Genel yapı dinamik programlama kullanılarak çözülen görevler: her problemin bir amaç fonksiyonu ve bir seçim değişkeni vardır..

2. Arabanın değiştirilmesi (maliyetlerin en aza indirilmesi)

Örnek: Her yıl eski arabayı bir yıl daha kullanıp kullanmayacağımıza karar veririz ve destek ve bakım masraflarını karşılarız. eski araba veya arabayı satıp yeni bir tane satın alın (ve satın alma maliyetine katlanın).

Amaç fonksiyonu: maliyetlerin en aza indirilmesi (eski bir arabanın bakım masrafları veya yeni bir arabanın satın alınması için).

Seçim değişkeni: her yıl arabayı satma ya da bırakma kararı al.

3. Borsa portföyü

Örnek: Borsada işlem yapmak, herhangi bir şirketin hissesini satın almak


Amaç fonksiyonu: maksimize etmek orta gelir, çünkü borsada gelir, olasılıklı bir şekilde elde edilir, yani. bu istatistiksel süreç, olasılıklı.

Seçim değişkeni: yatırım portföyü ne olacak: kaç hisse ve hangi şirketi almamız gerekiyor.

4. Optimum üretim planı (lojistik)

Örnek: Bir mobilya fabrikası var. Fabrikada çalışıyor belli bir miktar Belirli sayıda mobilya (sandalye, masa, dolap vb.)


Amaç fonksiyonu: kar maksimizasyonu.

Seçim değişkeni: işgücünün yeterli olması için kaç tane sandalye veya masa yapılması gerektiğinin seçimi.

5. Oyunlar (olasılıklı veya olasılıksız)

Örnek:Çeşitli oyunlara katılım


Amaç fonksiyonu: kazanma olasılığını maksimize etmek veya ortalama kazancı maksimize etmek vb.

Buradaki seçim değişkeni, belirli oyuna bağlıdır.

1'den 5'e kadar olan problemler optimizasyon problemlerine örnektir.

Kombinatorik:

6. Grafikler ve ağaçlar

Örnek: ile kaç tane ağaç olduğunu çözme problemi belirli bir sayı yapraklar; veya böyle bir görevi çözmek için kaç tane grafik var, vb.

7. Madeni para alışverişi sorunu veya değişikliği iade etmenin yollarının sayısı

Örnek: madeni paralar var farklı saygınlık değişikliği hangi yollarla iade edebileceğinizi.

o Kısa Açıklama daha sonra ayrıntılı olarak tartışılacak olan dinamik programlama için görevler.

Dinamik programlama konsepti

DP alt problemlerinin optimalliğinin gayri resmi açıklaması.

Düşünmek gayri resmi DP fikri.

Bir mobilya fabrikası örneğini ele alalım.

İçin karı maksimize etme hedefine ulaşmak için birçok alt görevi çözmek gerekir:

• kaç sandalye üretilecek - değişken X1,
• kaç tablo üretilecek - değişken X2,
• kaç çalışan işe alınacak - değişken X3,
• ... Xn.

Çok sayıda alt görevle, böyle bir sorunun nasıl çözüleceğini anlamak zordur. Genellikle, küçük bir sorunu çözmek büyük bir sorunu çözmekten daha kolaydır küçüklerden oluşur.

Bu nedenle, DP aşağıdakileri önermektedir:

• X1 değişkeni ile bir alt görev alın, şimdilik diğer alt görevleri unutun.

Örneğin bir fabrika sadece sandalye üretiyor. Yönetmenin görevi, sandalye satışından elde edilen karı maksimize etmektir.

• İlk alt problem için en uygun çözümü bulduktan sonra, X1 ve X2 değişkenleri için alt problemi alıyoruz ve çözüyoruz. ilk alt problem için zaten bulunan çözümü kullanmak.
• X1 ve X2 değişkenlerinin göründüğü daha büyük bir alt görev için bir çözüm elde ederiz. Daha sonra elde edilen çözümü kullanarak X1, X2 ve X3'ü kapsayan alt problemler alıyoruz.
• Ve böylece tüm genel problem için bir çözüm bulana kadar devam ediyoruz.

DP'nin resmi fikri

Çoğu zaman, bir sorun belirlerken, en uygun çözüm bir kaba kuvvet olası seçenekler ... Ancak, bu tür seçeneklerin çok sayıda olması ve bunun sonucunda bilgisayarın belleğinin aşırı yüklenmesi nedeniyle bu yöntem her zaman kabul edilemez.

Ek olarak şu soru ortaya çıkabilir: örneğin minimum veya maksimumu bulmak için neden türevi bulamıyoruz? veya La Grange setlerini veya aparatın diğer yöntemlerini kullanmamak matematiksel analiz? Büyük bir araç cephaneniz varsa neden bir DP'ye ihtiyacınız var?

Gerçek şu ki:

Dinamik programlama, bir problemi ayrı parçalara (alt görevler, aşamalar) bölerek çözme, bu alt görevleri çözme ve ardından bu çözümleri bir araya getirme fikrine dayanır. ortak karar... Çoğu zaman, alt görevlerin çoğu tamamen aynıdır.

Aynı zamanda, daha karmaşık bir problemi çözerken, küçük bir alt problemi yeniden çözmemek, ancak bu alt problemin zaten çözülmüş cevabını kullanmak önemlidir.
Grafikte şöyle görünebilir:

Önemli: Bu nedenle, görevin alt görevlere bölünmesi ve bu alt problemleri sadece bir kez çözerek (!), böylece sayıyı azaltmak genel bilgi işlem- dinamik programlamanın doğasında olan daha optimal bir yol

Türevler, La Grange kümeleri vb. ile ilgili bir problemi çözdüğümüzde, sürekli fonksiyonlarla çalışıyoruz. DP problemlerinin çözümünde esas olarak ayrık fonksiyonlarla çalışacağız, bu yüzden burada sürekli fonksiyonların kullanımından bahsetmek uygun olmaz.
Bu nedenle, birçok problemde, ancak hepsinde değil, matematiksel analiz aparatının kullanılması kabul edilemez olacaktır.

DP kullanarak problem çözmenin basit bir örneği

Dinamik programlama kullanarak problemi çözmenin bir çeşidini düşünelim.

Örnek: n sayının toplamını hesaplamak gerekir: 1 + 2 + 3 + ... + n

Bu görevin sözde "zorluğu" nedir: çok sayıda numaraları ve cevabı alın.

DP fikirlerini soruna uygulamaya çalışalım ve onu basit alt görevlere ayırarak çözelim.
(DP'de her zaman ilk önce başlangıç ​​koşullarını veya koşulu tanımlamak gerekir)

• İlk elemanın toplamı ile başlayalım, yani. sadece ilk elemanı alın:
  F (1) = 1
• şimdi ilk elemanın çözümü ile çöz
  F (2) = F (1) + 2 = 1 + 2 = 3, yani. ilk öğenin toplamını almanız ve ikinci öğeyi buna eklemeniz gerekir.
• F (3) = F (2) + 3 = 6
• analoji ile devam edin ve elde edin hedef fonksiyon:
  F (n) = F (n-1) + Bir

Yani, ne yaptık: sırayı belirledik ve alt problemleri izole ettik, sonra her birini bir öncekinin çözümüne dayanarak çözdük.

DP'nin hala haksız bir şekilde (yapay olarak) kullanıldığı basit bir örnek, DP fikirlerinin ilkesini göstermektedir.

Başka bir örnek alalım.

Örnek:önünde arkasında bir kişinin olduğu n basamaklı bir merdiven var 1 bir adım, bir sonraki adıma tırmanabilir veya bir adımın üzerinden atlayabilir. Soru şudur: Son adıma kaç yolla ulaşabilir?

Çözüm:

en çok düşünün basit seçenekler(alt görevler):

i adımlarının bir örneğini düşünün

i. adıma nasıl ulaşabiliriz:

1. i-1 adımından i-1 adımına i-1 yollarıyla ulaşabiliriz
2. i-2 adımlarından i-2 adımına i-2 yollarından ulaşabiliriz

Örneğin, nasıl gidilir 4. adım:

O., toplam tutar yollar i. adıma geçin:
f (a i) = f (a i-1) + f (a i-2)

Başlangıç ​​değerlerini tanımlayalım sorunu çözmeye başlamak için.
1 ile başlarsanız, formül bir Fibonacci sayıları dizisini bulmaya karşılık gelir.

Görevin esasen birleştirici olduğunu (yani, bir şeyi yapmanın yollarının sayısı) tekrarlayan bir diziyi hesaplamaya indirgendiğini görüyoruz.

1. Egzersiz:özyinelemeyi kullanarak ilk on basamak (aslında, Fibonacci serisinin ilk 10 sayısı) için bir örnek uygulayın.

Kodu tamamlayın:

1 2 3 4 5 6 7 8 9 10 11 12 13

var c: tamsayı; prosedür getKolSposob (i, n: tamsayı); writeln'ye başlayın (i + n, ""); inc (c); if ... o zaman getKolSposob (..., ...) sonu; c'ye başla: = 1; getKolSposob (0, 1); son.

var c: tamsayı; prosedür getKolSposob (i, n: tamsayı); writeln'ye başlayın (i + n, ""); inc (c); if ... o zaman getKolSposob (..., ...) sonu; c'ye başla: = 1; getKolSposob (0,1); son.

Ödev 2:
15. tip sınav görevlerinin çözümü (Grafikler. Yol sayısını arayın).

Diyelim ki zaten çözdüğümüz bir problem var. dinamik programörneğin, sonsuz Fibonacci sayıları.
Biraz yeniden formüle edelim. Bir vektör elde etmek istediğimiz bir vektörümüz olduğunu varsayalım. Formülleri biraz açalım: Vektörden vektörü alabileceğinizi görebilirsiniz. bir matrisle çarparak, çünkü yalnızca ilk vektörden eklenen değişkenler son vektörde görünür. Bu matrisin çıkarılması kolaydır, işte burada: ... Buna geçiş matrisi diyelim.

Bunun anlamı, vektörü alırsak ve bunu geçiş matrisi n - 1 ile çarparsak, problemin cevabı olan fib [n] içeren bir vektör elde ederiz.

Ve şimdi, tüm bunlar neden gerekli? Matris çarpımı, birleştiricilik özelliğine sahiptir, yani (ama benim görüşüme göre şaşırtıcı olan komütatifliğe sahip değildir). Bu özellik bize şunu yapma hakkını verir:

İyi haber şu ki, artık işe yarayan hızlı üs alma yöntemini uygulayabilirsiniz. Toplamda, aritmetik işlemlerin logaritması için N. Fibonacci sayısını hesaplayabildik.

Ve şimdi daha ciddi bir örnek:

Örnek # 3: Testere dişi dizisi

N uzunluğundaki bir testere dişi dizisini, her aşırı olmayan öğe için koşulun karşılandığı bir dizi olarak gösterelim: ya her iki komşusundan daha az ya da daha fazla. N uzunluğundaki rakamlardan testere dişi dizilerinin sayısını saymak gerekir. Şuna benziyor:

Çözüm

İlk olarak, geçiş matrisi olmayan bir çözüm:

1) Dinamiklerin durumu: dp [n] - son rakamla biten n uzunluğundaki testere dişi dizilerinin sayısı. Ayrıca, daha az == 0 ise, son rakam sondan bir öncekinden daha küçüktür ve daha az == 1 ise, o zaman daha fazladır.
2) Başlangıç ​​değerleri:
aralıktaki son (10): dp = 9 - son dp = son 3) Dinamik yeniden hesaplama:
(10) aralığında önceki için: eğer önceki> son: dp [n] + = dp önceki ise< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Cevap dp [N]'nin toplamıdır.

Şimdi bir başlangıç ​​vektörü ve ona bir geçiş matrisi bulmamız gerekiyor. Vektör hızla geliyor gibi görünüyor: N dizisinin uzunluğunu gösteren tüm durumlar. Peki, dönüşüm formüllerine bakarak geçiş matrisi görüntülenir.

Vektör ve geçiş matrisi

Segment dinamikleri

Bu, durumun bazı dizilerin bir alt bölümünün sınırları olduğu bir dinamik sınıfıdır. Buradaki nokta, dizimizin olası tüm alt bölümlerine dayalı olarak alt problemlerin cevaplarını saymaktır. Genellikle artan uzunluk sırasına göre sıralanırlar ve yeniden hesaplama sırasıyla daha kısa bölümlere dayanır.

Örnek # 4: Bir diziyi paketleme

İşte Genişletilmiş durum. Kısaca tekrar anlatacağım:

Sıkıştırılmış bir dize tanımlayalım:
1) Yalnızca harfleri içeren bir dize, sıkıştırılmış bir dizedir. Kendini açar.
2) Sıkıştırılmış A ve B dizelerinin birleşimi olan bir dize. Sıkıştırılmamış A ve B dizilerinin bir birleşimine genişletilir.
3) D dizisi (X), burada D, 1'den büyük bir tam sayıdır ve X, sıkıştırılmış bir dizedir. X'ten genişletilen D dizelerinin bir birleşimine genişletilir.
Örnek: “3 (2 (A) 2 (B)) C”, “AABBAABBAABBC” olarak genişler.

s dizesinin, içine genişletilen en kısa sıkıştırılmış dizenin uzunluğunu bulması gerekir.

Çözüm

Bu sorun, muhtemelen tahmin ettiğiniz gibi, alt bölümlerin dinamikleri ile çözülmüştür.

1) Dinamik durumu: d [l] [r] - sıkıştırılmış dize Minimum uzunluk string s'ye genişleme
2) Başlangıç ​​durumları: bir uzunluktaki tüm alt diziler yalnızca kendi içlerinde sıkıştırılabilir.
3) Dinamiklerin yeniden hesaplanması:
Daha iyi cevap, bir tür soyadı sıkıştırma işlemine sahiptir: ya bu sadece bir dize büyük harfler, veya iki dizenin birleştirilmesi veya sıkıştırmanın kendisidir. Öyleyse tüm seçenekleri gözden geçirelim ve en iyisini seçelim.

Dp_len = r - l dp [l] [r] = dp_len # İlk sıkıştırma seçeneği sadece bir dizgedir. i aralığında (l + 1, r): dp [l] [r] = min (dp [l] [r], dp [l] [i] + dp [i] [r]) # Bölmeye çalışın aralıkta (2, dp_len) cnt için iki sıkıştırılmış alt dize ile: if (dp_len% cnt == 0): # Bölünemezse, iyi = True for j aralığında (1, (dp_len) bölmeye çalışmanın bir anlamı yoktur / cnt) + 1 ): # Tüm cnt alt dizelerinin aynı iyi olduğunu kontrol edin & = s == s iyi ise: # Aynı alt dizeleri cnt'ye bölmeyi ve dp [l] [r] = min (dp [l]) sıkıştırmayı deneyin [r], len (str (cnt)) + 1 + dp [l] + 1) 4) Yeniden hesaplama sırası: düz çizgi artan alt dize uzunluğu veya tembel dinamik.
5) Cevap d'de yatıyor.

Örnek # 5: Meşe

Alt ağaçlara göre dinamikler

Alt ağaçlara göre dinamik durum parametresi genellikle bu tepe noktasının kök olduğu alt ağacı gösteren bir tepe noktasıdır. Mevcut durumun değerini elde etmek için genellikle tüm çocuklarınızın sonuçlarını bilmeniz gerekir. Çoğu zaman tembelce uygularlar - sadece ağacın kökünden derinlemesine bir arama yazarlar.

Örnek # 6: Mantıksal ağaç

Yapraklarında bir bitlik sayıların yazıldığı askıda bir ağaç verilir - 0 veya 1. Tüm iç köşeler de sayılar içerir, ancak aşağıdaki kurala göre: her köşe için, bir mantıksal işlemler: "VE" veya "VEYA". "VE" ise, tepe noktasının değeri, tüm çocuklarının değerlerinden mantıksal bir "VE" dir. "VEYA" ise, tepe noktasının değeri, tüm alt öğelerinin değerlerinden mantıksal bir "VEYA"dır.

İç köşelerdeki mantıksal işlemlerde, kökteki değerin değişmesi için minimum değişiklik sayısını bulmak veya bunun imkansız olduğunu bildirmek gerekir.

Çözüm

1) Dinamik durumu: d [v] [x] - v köşesinde x değerini elde etmek için gereken işlem sayısı. Bu mümkün değilse, durumun değeri + inf'dir.
2) Başlangıç ​​değerleri: Yapraklar için, sıfır değişiklik için değerinizi alabileceğiniz açıktır, ancak değeri değiştirmek imkansızdır, yani mümkündür, ancak sadece + inf işlemleri için.
3) Dönüşüm formülü:
Bu tepe noktasında zaten bir x değeri varsa, o zaman sıfırdır. Değilse, iki seçenek vardır: mevcut tepe noktasındaki işlemi değiştirmek veya değiştirmemek. İkisinin de bulması gerekiyor en iyi seçenek ve en iyisini seçin.

İşlem "VE" ise ve "0" almanız gerekiyorsa, cevap d [i] değerlerinin minimumudur, burada i v'nin oğludur.
İşlem "VE" ise ve "1" almanız gerekiyorsa, cevap d [i]'nin tüm değerlerinin toplamıdır, burada i v'nin oğludur.
İşlem "VEYA" ise ve "0" almanız gerekiyorsa, cevap d [i]'nin tüm değerlerinin toplamıdır, burada i v'nin oğludur.
İşlem "VEYA" ise ve "1" almanız gerekiyorsa, cevap d [i] değerlerinin minimumudur, burada i v'nin oğludur.

4) Yeniden hesaplama sırası: onu tembelce uygulamak en kolayıdır - kökten derinlemesine bir arama şeklinde.
5) Cevap d xor 1'dir].

Alt kümelere göre dinamikler

Alt kümeler üzerindeki dinamiklerde, durum genellikle belirli bir kümenin maskesini içerir. Çoğu zaman, bu maskedeki birim sayısını artırma sırasına göre sıralanırlar ve sırasıyla daha az açık olan durumlardan yeniden hesaplanırlar. Tembel dinamikler genellikle, bazen tamamen önemsiz olmayan geçiş sırası hakkında özel olarak düşünmekten kaçınmak için kullanılır.

Örnek # 7: Minimum ağırlıklı Hamilton döngüsü veya gezgin satıcı problemi

N boyutunda ağırlıklı (kenar ağırlıkları negatif olmayan) bir G grafiği verilmiştir. Minimum ağırlıkta bir Hamilton çevrimi (kendisiyle kesişmeyen tüm köşelerden geçen bir çevrim) bulun.

Çözüm

Tüm köşelerden geçen bir döngü aradığımız için “başlangıç” köşelerinden herhangi birini seçebiliriz. 0 numaralı köşe olsun.

1) Dinamiklerin durumu: dp [v] - 0 noktasından v noktasına minimum ağırlığın yolu, maske içinde ve sadece onlar boyunca uzanan tüm köşelerden geçer.
2) Başlangıç ​​değerleri: dp = 0, diğer tüm durumlar başlangıçta + inf'dir.
3) Dönüştürme formülü: Maskedeki i-inci bit 1 ise ve i'den v'ye bir kenar varsa, o zaman:
dp [v] = min (dp [v], dp [i] + w [i] [v]) Burada w [i] [v], i ile v arasındaki bir kenarın ağırlığıdır.
4) Yeniden hesaplama prosedürü: en basit ve uygun yol- bu tembel bir dinamik yazmak içindir, ancak içindeki tek bitlerin sayısını artırma sırasına göre saptırılabilir ve maskeler üzerine bir yineleme yazabilirsiniz.
5) Cevap d'de yatıyor [(1<< N) - 1] .

Profile göre dinamikler

Profil boyunca dinamiklerin çözdüğü klasik problemler, sahayı bazı figürlerle döşeme problemleridir. Ayrıca, örneğin döşeme yöntemlerinin sayısı veya minimum sayıda rakamla döşeme gibi farklı şeyler sorulabilir.

Bu sorunlar, a'nın bir hücre için döşeme seçeneklerinin sayısı olduğu kapsamlı arama ile çözülebilir. Profil boyunca dinamikler ise, boyutların birindeki zamanı doğrusal olarak optimize eder ve sadece katsayıyı üstel olarak bırakır. Bunun gibi bir şey alacaksınız:.

Profil, zaten döşenmiş bir parça ile asfaltlanmamış bir parça arasındaki sınır olan k (genellikle bir) sütundur. Bu sınır sadece kısmen doldurulmuştur. Çoğu zaman dinamik durumun bir parçasıdır.

Hemen hemen her zaman bir durum bir profildir ve bu profilin nerede olduğu. Ve geçiş bu konumu birer birer artırır. Profil boyutundan lineer bir zamanda bir profilden diğerine geçişin mümkün olup olmadığını öğrenmek mümkündür. Bu, yeniden hesaplama sırasında her seferinde kontrol edilebilir, ancak önceden hesaplanabilir. İki boyutlu kutu dizisini önceden hesaplayacağız - profilin konumunu birer birer artırarak birkaç rakam yerleştirerek bir maskeden diğerine geçmek mümkün mü? Ön hesaplama, daha az yürütme süresi ve daha fazla bellek alacaktır.

Örnek # 8: Domino taşları ile döşeme

1 x 2 ve 2 x 1 boyutlarındaki domino taşlarını kullanarak N x M bir tabloyu döşemenin kaç yolunu bulun.

Çözüm

Burada profil bir sütundur. İkili maske şeklinde saklamak uygundur: 0 - döşemeli sütun hücresi, 1 - döşemeli. Yani, tüm profiller.

0) Ön sayım (isteğe bağlı): tüm profil çiftlerini yineleyin ve birinden diğerine geçip geçemeyeceğinizi kontrol edin. Bu görevde, bu şu şekilde doğrulanır:

İlk profilde bir sonraki yerde 1 varsa, bu hücreyi herhangi bir rakamla döşeyemeyeceğimiz için 0 ikinci olmalıdır.

İlk profilde bir sonraki yerde 0 varsa, o zaman iki seçenek vardır - ikinci 0 veya 1'de.
0 ise, bu dikey bir domino koymamız gerektiği anlamına gelir, bu da bir sonraki hücrenin 1 olarak kabul edilebileceği anlamına gelir. 1 ise, dikey bir domino yerleştirir ve bir sonraki hücreye gideriz.

Geçiş örnekleri (üst profilden alt profillere ve sadece içlerine gidebilirsiniz):

Bundan sonra, her şeyi can dizisine kaydedin - gidebilirseniz 1, gidemezseniz 0 -.
1) Dinamiklerin durumu: dp - maske profiline sahip ilk konum - 1 sütunlarının tam döşemelerinin sayısı.
2) Başlangıç ​​durumu: dp = 1 - alanın sol sınırı - düz duvar.
3) Dönüşüm formülü:
dp + = dp * olabilir
4) Geçiş sırası artan sırada pos.
5) Cevap dp'de yatıyor.

Elde edilen asimptotiktir.

Kırık profil dinamikleri

Bu çok güçlü bir dinamik profil optimizasyonudur. Burada profil sadece bir maske değil, aynı zamanda bir kırılma noktasıdır. Şuna benziyor:

Şimdi profile bir bükülme ekledikten sonra, sol bükülme hücresini kaplayan sadece bir rakam ekleyerek bir sonraki duruma geçebilirsiniz. Yani, durum sayısını N kat artırarak (kırılma noktasının nerede olduğunu hatırlamalıyız), bir durumdan diğerine geçiş sayısını azalttık. Asimptotikler .

Domino taşlarıyla döşeme ile ilgili problem örneğini kullanarak kırık bir profil boyunca dinamiklerde geçişler (örnek no. 8):

Bir yanıtı kurtarma

Bazen en iyi cevabın bazı özelliklerini bilmek yeterli olmaz. Örneğin, "Bir dize paketleme" görevinde (örnek # 4), yalnızca en kısa sıkıştırılmış dizenin uzunluğuyla sonuçlanırız, ancak büyük olasılıkla uzunluğuna değil, dizenin kendisine ihtiyacımız vardır. Bu durumda, cevabı geri yüklemeniz gerekir.

Her görevin cevabı kurtarmanın kendi yolu vardır, ancak en yaygın olanı:

• Dinamik durum değerinin yanında, alt görevin tam cevabını saklayın. Cevap büyükse, çok fazla bellek gerektirebilir, bu nedenle farklı bir yöntem kullanabiliyorsanız, genellikle durum budur.
• Verilen durumun ata(lar)ını bilerek cevabı yeniden oluşturun. Sadece nasıl alındığını bilerek bir cevabı yeniden oluşturmak çoğu zaman mümkündür. Aynı "Dizeyi paketleme" bölümünde, yanıtı geri yüklemek için yalnızca son eylemin türünü ve alındığı durumları saklayabilirsiniz.
• Hiç ek bellek kullanmayan bir yol var - dinamikleri yeniden hesapladıktan sonra, en iyi yol boyunca sondan gidin ve yol boyunca bir cevap oluşturun.

Küçük optimizasyonlar

Hafıza

Oldukça sık olarak dinamiklerde, bir durumun sayılması için az sayıda başka durum gerektirdiği bir görevle karşılaşılabilir. Örneğin Fibonacci sayılarını hesaplarken sadece son ikisini kullanırız ve asla öncekilere dönmeyeceğiz. Bu, onları unutabileceğiniz, yani onları hafızada saklamayabileceğiniz anlamına gelir. Bu bazen asimptotik hafıza puanını iyileştirir. Bu teknik örnekler #1, #2, #3 (geçiş matrisi olmayan çözümde), #7 ve #8 örneklerinde kullanılabilir. Doğru, baypas sırası tembel bir dinamik ise, bu hiçbir şekilde çalışmayacaktır.

Zaman

Bazen, bir tür veri yapısı kullanarak asimptotik zamanı iyileştirebilirsiniz. Örneğin, Dijkstra'nın algoritmasında asimptotik zamanı değiştirmek için bir öncelik sırası kullanabilirsiniz.

durum değiştiriliyor

Dinamik kararlarda, mutlaka bir durum belirir - bir alt görevi benzersiz şekilde tanımlayan parametreler, ancak bu durum mutlaka tek durum değildir. Bazen başka parametreleri düşünebilir ve bundan azaltılmış asimptotik zaman veya bellek şeklinde yararlanabilirsiniz.

Örnek # 9: Bir sayının ayrıştırılması

N sayısının farklı terimlere ayrıştırılma sayısını bulmak gerekir. Örneğin, N = 7 ise, bu tür 5 açılım vardır:

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

), karmaşıklığı orijinalinden biraz daha az olan bir dizi örtüşen alt problem gibi görünüyor. Bu durumda, "saf" yöntemlerle karşılaştırıldığında hesaplama süresi önemli ölçüde azaltılabilir.

Dinamik programlamadaki ana fikir oldukça basittir. Kural olarak, belirli bir sorunu çözmek için, sorunun tek tek bölümlerini (alt görevler) çözmek ve ardından alt görevlerin çözümlerini tek bir genel çözümde birleştirmek gerekir. Bu alt görevlerin çoğu genellikle aynıdır. Dinamik programlama yaklaşımı, her bir alt problemi yalnızca bir kez çözmek ve böylece hesaplama sayısını azaltmaktır. Bu, özellikle tekrar eden alt görevlerin sayısının katlanarak fazla olduğu durumlarda kullanışlıdır.

Yöntem yukarıdan dinamik programlama- bu, gelecekte tekrar ortaya çıkabilecek bu alt görevleri çözmenin sonuçlarının basit bir ezberidir. Aşağıdan dinamik programlama karmaşık bir problemi daha basit alt problemlerin özyinelemeli bir dizisi olarak yeniden formüle etmeyi içerir.

Tarih

"Dinamik programlama" ifadesi ilk olarak 1980'lerde R. Bellman tarafından bir probleme çözüm bulma sürecini tanımlamak için kullanıldı, burada bir problemin cevabı ancak problem "önceki" problem çözüldükten sonra elde edilebilir. G.'de bu tanımı modern bir tanımla geliştirdi. Bu alan aslında IEEE tarafından tanınan sistem analizi ve mühendisliği olarak kurulmuştur. Bellman'ın dinamik programlamaya katkısı, bir optimizasyon problemini özyinelemeli bir biçimde yeniden formüle eden dinamik programlama teorisinin merkezi bir sonucu olan Bellman denklemi başlığında ölümsüzleştirildi.

"Dinamik programlama" ifadesindeki "programlama" kelimesinin aslında "geleneksel" programlama (kod yazma) ile neredeyse hiçbir ilgisi yoktur ve "optimizasyon" kelimesi ile eş anlamlı olan "matematiksel programlama" ifadesinde olduğu gibi anlamlıdır. . Bu nedenle, bu bağlamdaki "program" kelimesi, soruna bir çözüm elde etmek için en uygun eylemler dizisi anlamına gelir. Örneğin, bir sergideki belirli bir etkinlik programına bazen program denir. Bu durumda program, kabul edilebilir bir olaylar dizisi olarak anlaşılmaktadır.

Dinamik programlama fikri

Optimal alt yapıyı kullanarak bir grafikte bir tepe noktasından diğerine en kısa yolu bulma; düz bir çizgi basit bir kenarı belirtir; dalgalı çizgi, bağlandığı köşeler arasındaki en kısa yolu gösterir (yolun ara köşeleri gösterilmemiştir); kalın çizgi son en kısa yolu gösterir.

Optimum altyapı dinamik programlamada, orijinal problemi çözmek için daha küçük alt problemlerin optimal çözümünün kullanılabileceği anlamına gelir. Örneğin, bir grafikte bir tepe noktasından (s ile gösterilir) diğerine (t ile gösterilir) en kısa yol şu şekilde bulunabilir: önce, s'den t'ye komşu tüm köşelerden en kısa yolu hesaplarız ve sonra s'yi bitişik köşelere bağlayan kenarların ağırlıklarını hesaba katarak, t'ye giden en iyi yolu seçin (hangi köşeden geçmek en iyisidir). Genel olarak, aşağıdaki üç adımı yaparak optimal bir alt yapıya sahip bir problemi çözebiliriz.

1. Bir görevi daha küçük alt görevlere bölme.
2. Aynı üç adımlı algoritmayı takip ederek, alt problemlere en uygun çözümü yinelemeli olarak bulma.
3. Orijinal probleme bir çözüm oluşturmak için elde edilen alt problem çözümlerini kullanmak.

Alt problemler, onları daha da küçük boyutlu alt problemlere bölerek çözülür ve bu, sabit zamanda çözülebilecek bir problemin önemsiz durumuna gelinceye kadar (cevap hemen söylenebilir). Örneğin, n !'yi bulmamız gerekiyorsa, o zaman önemsiz görev 1! = 1 (veya 0! = 1).

Çakışan alt görevler dinamik programlamada, daha büyük boyutta belirli sayıda sorunu (bir değil) çözmek için kullanılan alt görevler anlamına gelir (yani, aynı şeyi birkaç kez yaparız). Çarpıcı bir örnek, Fibonacci dizisinin hesaplanmasıdır ve - böyle önemsiz bir durumda bile, sadece iki Fibonacci sayısının hesaplanmasında bile iki kez saydık. Daha fazla devam edip sayarsanız, hesaplama için tekrar ihtiyacınız olacağından iki kez daha sayılacaktır. Şunlar ortaya çıkıyor: basit bir özyinelemeli yaklaşım, halihazırda çözmüş olduğu problemler için bir çözüm hesaplamak için zaman harcayacaktır.

Böyle bir gidişattan kaçınmak için, çözdüğümüz alt problemlerin çözümlerini kaydedeceğiz ve tekrar alt problem için bir çözüme ihtiyaç duyduğumuzda, tekrar hesaplamak yerine onu hafızadan geri alacağız. Bu yaklaşıma önbelleğe alma denir. Daha fazla optimizasyon yapılabilir - örneğin, bir alt görev için artık bir çözüme ihtiyacımız olmadığından eminsek, onu bellekten atabilir, diğer ihtiyaçlar için serbest bırakabiliriz veya işlemci boştaysa ve çözümü biliyoruz. Henüz sayılmayan bazı alt görevler, daha sonra ihtiyacımız olacak, önceden çözebiliriz.

Yukarıdakileri özetlersek, dinamik programlamanın problemin aşağıdaki özelliklerini kullandığını söyleyebiliriz:

• örtüşen alt görevler;
• optimal altyapı;
• Sık karşılaşılan alt görevlerin çözümlerini ezberleme yeteneği.

Dinamik programlama genellikle sorunları çözmek için iki yaklaşım kullanır:

• yukarıdan aşağıya dinamik programlama: bir problem daha küçük alt problemlere bölünür, bunlar çözülür ve daha sonra orijinal problemi çözmek için birleştirilir. Ezberleme, sık karşılaşılan alt görevleri çözmek için kullanılır.
• aşağıdan yukarıya dinamik programlama: orijinal problemi çözmek için sonradan ihtiyaç duyulan tüm alt görevler önceden hesaplanır ve daha sonra orijinal probleme bir çözüm oluşturmak için kullanılır. Bu yöntem, gerekli yığının boyutu ve işlev çağrılarının sayısı açısından yukarıdan aşağıya programlamadan daha iyidir, ancak bazen gelecekte hangi alt sorunları çözmemiz gerektiğini önceden anlamak kolay değildir.

Programlama dilleri, "ada göre hesaplamayı" hızlandırmak için belirli bir dizi argümanla (not alma) bir işlevi çağırmanın sonucunu hatırlayabilir. Bazı dillerde bu özellik yerleşiktir (örneğin, Scheme, Common Lisp, Perl) ve bazılarında ek uzantılar (C ++) gerektirir.

Yöneylem araştırması ile ilgili tüm ders kitaplarında yer alan seri dinamik programlama ve 1960'larda keşfedilmesine rağmen şu anda çok az bilinen seri olmayan dinamik programlama (NSDP) bilinmektedir.

Normal dinamik programlama, değişken ilişkilerin grafiğinin tam da gidilecek yol olduğu, seri olmayan dinamik programlamanın özel bir durumudur. Optimizasyon probleminin yapısını dikkate almak için doğal ve genel bir yöntem olan NSDP, kısıtlamalar setini ve/veya amaç fonksiyonunu özyinelemeli hesaplanabilir bir fonksiyon olarak kabul eder. Bu, önceki aşamalarda elde edilen bilgileri kullanarak aşamaların her birinde aşamalar halinde bir çözüm bulmanızı sağlar ve bu algoritmanın verimliliği doğrudan değişkenlerin karşılıklı ilişkileri grafiğinin yapısına bağlıdır. Bu grafik yeterince seyrekse, her aşamadaki hesaplama miktarı makul sınırlar içinde tutulabilir.

Dinamik programlama kullanılarak çözülen problemlerin temel özelliklerinden biri toplanabilirliktir. Katkısız problemler diğer yöntemlerle çözülür. Örneğin, bir şirketin yatırımlarını optimize etmeye yönelik birçok görev, katkı içermez ve şirketin değeri yatırımlı ve yatırımsız karşılaştırılarak çözülür.

Klasik dinamik programlama problemleri

Edebiyat

• Bellman R. Dinamik programlama. - M.: Yabancı edebiyatın yayınevi, 1960.
• Cormen, T., Leiserson, C., Rivest, R., Stein, K. Bölüm 15. Dinamik programlama // Algoritmalar: oluşturma ve analiz = Algoritmalara Giriş / Ed. I.V. Krasikova. - 2. baskı. - E.: Williams, 2005 .-- 1296 s. - ISBN 5-8459-0857-4
• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Algoritmalar = Algoritmalar. - 1. baskı. - McGraw-Hill Bilim / Mühendislik / Matematik, 2006 .-- S. 336 .-- ISBN 0073523402
• Akulich I.L. Bölüm 4. Dinamik Programlama Problemleri// Örneklerde ve problemlerde matematiksel programlama. - M.: Yüksek okul, 1986 .-- 319 s. - ISBN 5-06-002663-9.
• Bertele U., Brioshi F. Seri olmayan dinamik programlama. - N.Y.: Academic Press, 1972 .-- 235 s.
• Shcherbina O.A.Ayrık optimizasyon problemleri için yerel ayrıştırma algoritmasının seri olmayan modifikasyonu hakkında // Dynamical Systems, 2005, no. 19.
• Shcherbina OA Dinamik programlamanın metodolojik yönleri // Dinamik sistemler, 2007, no. 22 .-- s. 21-36.
• Gabasov R., Kirillova FM Dinamik programlamanın temelleri. - Minsk: BSU Yayınevi, 1975 .-- 262 s.

Bağlantılar

Wikimedia Vakfı. 2010.

Diğer sözlüklerde "Dinamik programlama"nın ne olduğunu görün:

dinamik program- - [E.S. Alekseev, A.A. Myachev. Bilgisayar Sistemleri Mühendisliğinin İngilizce Rusça Açıklayıcı Sözlüğü. Moskova 1993] dinamik programlama Matematiksel programlama bölümü, temel alınarak optimal çözümler bulmanızı sağlayan bir dizi teknik ... Teknik çevirmen kılavuzu

Dinamik program- matematiksel programlamanın bir bölümü, her bir kararın sonuçlarını hesaplamaya ve sonraki kararlar için optimal bir strateji geliştirmeye dayalı optimal çözümler bulmayı sağlayan bir dizi teknik. ... ... Ekonomi ve Matematik Sözlüğü

Çok adımlı optimal kontrol problemlerini çözme teorisi ve yöntemlerine ayrılmış bir matematik dalı. Bir diferansiyel sistemde, kontrollü süreçler için, her türlü kontrol arasında, aşırı (en küçük veya en büyük) bir değer veren bir şey aranır ... ... matematik ansiklopedisi

Çok adımlı optimal kontrol problemlerini çözme teorisi ve yöntemlerine ayrılmış bir matematik dalı (Bkz. Optimal kontrol). D.'de kontrollü süreçler için, tüm olası kontroller arasında, aşağıdakileri sağlayan biri aranır ... ... Büyük Sovyet Ansiklopedisi

dinamik program- dinamin programavimas durumları T sritis automatika atitikmenys: angl. dinamik programlama vok. dynamische Programmierung, f rus. dinamik programlama, pranc. programlama dinamiği, f ... Automatikos terminų žodynas

Bölüm matematik. programlama, optimal bulmanın çok adımlı süreçlerini incelemek. karmaşık problemleri çözmek. Çözüm bulma sürecinin bir tür olarak temsil edilebileceği bu tür optimizasyon problemlerini çözmek için programlar derlerken kullanılır ... ... Büyük Ansiklopedik Politeknik Sözlük

Yukarıda tartışılan yönetim görevleri modelleri, zamanı hesaba katmamıştır. Bunlar, örneğin, incelenen süreçteki değişikliklerin zaman içinde ihmal edilebileceği durumlarda, statik, zamandan bağımsız süreçleri analiz etmenize izin veren sözde tek aşamalı modellerdir. Bu tür modellemeye ilişkin yönetimsel karar, ya sistem kararlılığı koşullarında ya da gelecekte kısa bir süre için anlamlıdır.

Gerçekte, tüm ekonomik süreçler ve fenomenler zamanla işler ve gelişir, yani doğaları gereği dinamiktirler. Bu, yöneticilerin, sürecin kontrol edilebilmesi, yani gelişiminin seyrini etkilemesi koşuluyla, zaman içinde ekonomik süreçlerdeki olası değişiklikleri hesaba katması gereken pratik sorunları çözmesini gerektirir.

Dinamik programlama, çok adımlı optimal kontrol problemlerinin çözüldüğü matematiksel bir aparattır. Bu tür programlamada, süreç kontrolü için, tüm uygulanabilir çözümler arasında, belirli bir kriter anlamında optimal olanı, yani amaç fonksiyonunun aşırı (az ya da çok) değerini veren bir çözüm aranır. - sürecin belirli bir sayısal özelliği. Çok derecede, ya sürecin çok aşamalı yapısı ya da kontrolün, kural olarak, zaman içinde farklı noktalara karşılık gelen bir dizi ardışık aşamaya dağılımı anlaşılır. Bu nedenle, "programlama" kelimesi yönetimsel kararlar almak anlamına gelir ve "dinamik" kelimesi, dikkate alınan süreç ve yöntemlerde işlemlerin gerçekleştirilme zamanının ve sırasının önemli önemini gösterir.

Dinamik programlama görevleri, zamanlama, yatırım tahsisi, envanter yönetimi, bakım ve revizyon, reklam yöntemlerinin seçimi ve benzerlerini içerir.

Bazı dinamik programlama problemlerinde yönetim süreci, örneğin ay, çeyrek, yıl gibi doğal bir şekilde aşamalara ayrılır. Diğer durumlarda, aşamalara bölünme şartlı olabilir. Tüm dinamik programlama görevlerinin özelliği, her aşamada, bu tür bir kontrolün kalitesini değerlendirirken önceki değişiklikleri dikkate almanın, olayların akışını kontrol etmenin mümkün olmasıdır. Bu nedenle, dinamik programlama, bir dizi yönetim kararı vermenize izin verir, sistemin bir bütün olarak optimal gelişimini sağlar.

Bu programlama probleminin genel formülasyonunu ele alalım. Ardışık n aşaması olan bazı ekonomik süreçleri inceleyelim. Her 7. aşamada, süreç, her biri sonlu bir parametre seti ile karakterize edilen farklı durumlarda olabilir. Görevin her aşaması, sistemi bir durumdan diğerine aktaran belirli bir yönetsel karar chi'nin benimsenmesiyle ilişkilidir. 7. aşamanın sonunda sistemin si durumunun sadece bir önceki durum si_1 ve 7. aşamada kontrol chi tarafından belirlendiği ve önceki durumlara ve kontrollere bağlı olmadığı varsayılır. Daha sonra sistemin durumu si bağımlılık olarak yazılır.

Si = φ (s, _ !, Xu), i = 1, A.

Tüm yönetim sürecinin etkinliği, bireysel aşamaların yönetim kararlarının etkinliğinin toplamı olarak temsil edilebilir, yani

Bu koşullar altında, dinamik programlama problemi şu şekilde formüle edilir: sistemi başlangıç ​​durumundan (50) son duruma sn aktaran X = (x1, x2, xn) gibi kabul edilebilir bir yönetimsel kararlar dizisini belirlemek ve maksimum kontrol verimliliği elde edilir.

Çok aşamalı bir yönetim süreci planlanırken, dinamik programlama problemlerinde, her aşamada bir yönetim çözümü seçmek, hala devam eden aşamalardaki sonuçlarını dikkate alarak bir yönetim çözümü seçmek gerekir. Sadece son aşamada, bir sonraki adım onun için mevcut olmadığından, maksimum etkiyi sağlayacak bir yönetim kararı alınabilir. Bu nedenle, dinamik programlama sorunları sondan çözülür.

Son n'inci aşamadaki amaç fonksiyonunun maksimumu,

^ n-O = şah / n ^ n-i xn).

Buna göre, sahip olduğumuz (n - 1) -etape üzerinde

r * n-1 (5n-2) = ShaX ((fn-1 (sn-2, xn-1) + r * n ^ n-1)).

Bu düzenliliği hesaba katarak, keyfi bir k-aşaması için tekrarlayan bağımlılığı yazabiliriz.

r * (beşinci-1) = Shahi (L (uk-1, xk) + r * + 1)).

Bu yinelenen ilişki, Bellman'ın optimallik ilkesinin matematiksel bir gösterimidir.

İlk aşamada koşullu olarak optimal etkiyi tekrarlayan bağımlılıklarla belirledikten sonra, koşulsuz kontrol optimizasyonu "ters" yönde gerçekleştirilir, bunun sonucunda sistemin maksimum verimliliğini sağlayan bir dizi yönetim kararı bulunur. bir bütün.

Dinamik programlama yönteminin temel özellikleri

1. Dinamik programlama fikri ve yöntemi, çoğunlukla kontrol problemleri olan ayrık problemlere daha çok uyarlanmıştır.

2. Dinamik programlama yöntemi, amaç fonksiyonunu tanımlamanın herhangi bir şekilde ve kabul edilebilir herhangi bir durum ve kontrol seti ile uygulanabilir. Klasik optimizasyon yöntemleri ve diğer matematiksel programlama yöntemleri bu avantajdan yoksundur.

3. Durum değişkeninin tüm olası değerleri için kth adımında verimlilik ve kontrol göstergesinin optimal değerlerinin bir bölmesi ile ilişkili ayrık durumda dinamik programlama yönteminin hesaplama şemaları, ancak hesaplamaların miktarı doğrudan bir seçenekler bölmesi durumundan çok daha az. Bunun nedeni, koşullu optimizasyon aşamasında başarısız seçeneklerin hemen atılması ve bu aşamada yalnızca koşullu olarak optimal olanların tutulmasıdır.

4. Dinamik programlama yöntemi, sk durumlarının ilk verilerindeki ve n sayılarındaki değişikliklere duyarlılığı analiz etmeyi mümkün kılar. Aslında, burada her adımda bir sorun çözülmez, ancak farklı durumlar için bir dizi benzer sorun çözülür. sk ve farklı k (1<к <п) . Поэтому с изменением исходных данных нельзя не решать задачу заново, а сделать только несложные добавление к уже выполненных расчетов, то есть продолжить уже решенную задачу за счет увеличения количества шагов п или количества значений sk.

sonuçlar

1. Doğrusal olmayan modellerin ortaya çıkışı, optimal bir kararın benimsenmesini etkileyen doğrusal olmayan yasaları dikkate alma ve gösterme ihtiyacı ile ilişkilidir. Bu tür modeller, görev kısıtlamalarına ve amaç fonksiyonuna dahil edilir.

2. Doğrusal olmayan programlama problemlerini tanımlayan fonksiyonların ve kısıtlamaların doğası gereği, bunlar şu şekilde sınıflandırılabilir: klasik optimizasyon problemleri; doğrusal olmayan amaç fonksiyonu ve doğrusal kısıtlamalarla ilgili problemler; dışbükey, ikinci dereceden, ayrılabilir programlama problemleri.

3. Doğrusal programlama problemlerinin aksine, doğrusal olmayan problemleri çözmek için evrensel bir yöntem yoktur. Her durumda, en iyi yöntem seçilmelidir.

4. Dinamik programlama, yardımıyla çok adımlı optimal kontrol problemlerinin çözüldüğü matematiksel bir aparattır. Çok derece, ya bir sürecin çok aşamalı yapısı ya da kontrolün, kural olarak, zaman içinde farklı noktalara karşılık gelen bir dizi ardışık aşamaya dağıtılması olarak anlaşılır.

5. Dinamik programlamanın görevleri, zamanlama, yatırım tahsisi, envanter yönetimi, bakım ve revizyon, reklam yöntemlerinin seçimi ve benzerlerini içerir. Tüm dinamik programlama görevlerinin özelliği, her aşamada, bu tür bir kontrolün kalitesini değerlendirirken önceki değişiklikleri dikkate almanın ve olayların gidişatını kontrol etmenin mümkün olmasıdır.

6. Dinamik programlama problemlerinin çözümü Bellman optimalite ilkesine dayanmaktadır. Dinamik programlama kontrol optimizasyonu sürecinde çok adımlı süreç iki kez gerçekleştirilir. İlk kez - baştan sona, bunun sonucunda koşullu olarak optimal kontroller bulunur. İkincisi, sürecin bir bütün olarak optimal kontrolünün bulunmasının bir sonucu olarak baştan sona kadardır.

), karmaşıklığı orijinalinden biraz daha az olan bir dizi örtüşen alt problem gibi görünüyor. Bu durumda, "saf" yöntemlerle karşılaştırıldığında hesaplama süresi önemli ölçüde azaltılabilir.

Dinamik programlamadaki ana fikir oldukça basittir. Kural olarak, belirli bir sorunu çözmek için, sorunun tek tek bölümlerini (alt görevler) çözmek ve ardından alt görevlerin çözümlerini tek bir genel çözümde birleştirmek gerekir. Bu alt görevlerin çoğu genellikle aynıdır. Dinamik programlama yaklaşımı, her bir alt problemi yalnızca bir kez çözmek ve böylece hesaplama sayısını azaltmaktır. Bu, özellikle tekrar eden alt görevlerin sayısının katlanarak fazla olduğu durumlarda kullanışlıdır.

Yöntem yukarıdan dinamik programlama- bu, gelecekte tekrar ortaya çıkabilecek bu alt görevleri çözmenin sonuçlarının basit bir ezberidir. Aşağıdan dinamik programlama karmaşık bir problemi daha basit alt problemlerin özyinelemeli bir dizisi olarak yeniden formüle etmeyi içerir.

Üniversite YouTube'u

• 1 / 5

  "Dinamik programlama" ifadesi ilk olarak 1980'lerde R. Bellman tarafından bir probleme çözüm bulma sürecini tanımlamak için kullanıldı, burada bir problemin cevabı ancak problem "önceki" problem çözüldükten sonra elde edilebilir. G.'de bu tanımı modern bir tanımla geliştirdi. Bu alan aslında IEEE tarafından tanınan sistem analizi ve mühendisliği olarak kurulmuştur. Bellman'ın dinamik programlamaya katkısı, bir optimizasyon problemini özyinelemeli bir biçimde yeniden formüle eden dinamik programlama teorisinin merkezi bir sonucu olan Bellman denklemi başlığında ölümsüzleştirildi.

  "Dinamik programlama" ifadesindeki "programlama" kelimesinin gerçekte "geleneksel" programlama (kod yazma) ile neredeyse hiçbir ilgisi yoktur ve "optimizasyon" kelimesi ile eş anlamlı olan "matematiksel programlama" ifadesinde olduğu gibi anlamlıdır. . Bu nedenle, bu bağlamdaki "program" kelimesi, soruna bir çözüm elde etmek için en uygun eylemler dizisi anlamına gelir. Örneğin, bir sergideki belirli bir etkinlik programına bazen program denir. Bu durumda program, kabul edilebilir bir olaylar dizisi olarak anlaşılmaktadır.

  Dinamik programlama fikri

  Optimum altyapı dinamik programlamada, orijinal problemi çözmek için daha küçük alt problemlerin optimal çözümünün kullanılabileceği anlamına gelir. Örneğin, bir grafikte bir tepe noktasından (s ile gösterilir) diğerine (t ile gösterilir) en kısa yol şu şekilde bulunabilir: önce, s'den t'ye komşu tüm köşelerden en kısa yolu hesaplarız ve sonra s'yi bitişik köşelere bağlayan kenarların ağırlıklarını hesaba katarak, t'ye giden en iyi yolu seçin (hangi köşeden geçmek en iyisidir). Genel olarak, aşağıdaki üç adımı yaparak optimal bir alt yapıya sahip bir problemi çözebiliriz.

  1. Bir görevi daha küçük alt görevlere bölme.
  2. Aynı üç adımlı algoritmayı takip ederek, alt problemlere en uygun çözümü yinelemeli olarak bulma.
  3. Orijinal probleme bir çözüm oluşturmak için elde edilen alt problem çözümlerini kullanmak.

  Alt problemler, onları daha da küçük boyutlu alt problemlere bölerek çözülür ve bu, sabit zamanda çözülebilecek bir problemin önemsiz durumuna gelinceye kadar (cevap hemen söylenebilir). Örneğin, n !'yi bulmamız gerekiyorsa, o zaman önemsiz görev 1! = 1 (veya 0! = 1).

  Çakışan alt görevler dinamik programlamada, daha büyük boyutta belirli sayıda sorunu (bir değil) çözmek için kullanılan alt görevler anlamına gelir (yani, aynı şeyi birkaç kez yaparız). En önemli örnek, Fibonacci dizisinin hesaplanmasıdır, F 3 = F 2 + F 1 (\ displaystyle F_ (3) = F_ (2) + F_ (1)) ve F 4 = F 3 + F 2 (\ displaystyle F_ (4) = F_ (3) + F_ (2))- böyle önemsiz bir durumda bile, sadece iki Fibonacci sayısının hesaplamalarını iki kez saydık. Daha fazla devam edip sayarsanız, o zaman F 2 (\ görüntü stili F_ (2)) hesaplamak için iki kez daha sayılacak F 5 (\ görüntü stili F_ (5)) tekrar ihtiyaç duyulacak F 3 (\ görüntü stili F_ (3)) ve F 4 (\ görüntü stili F_ (4))... Şunlar ortaya çıkıyor: basit bir özyinelemeli yaklaşım, halihazırda çözmüş olduğu problemler için bir çözüm hesaplamak için zaman harcayacaktır.

  Böyle bir gidişattan kaçınmak için, çözdüğümüz alt problemlerin çözümlerini kaydedeceğiz ve tekrar alt problem için bir çözüme ihtiyaç duyduğumuzda, tekrar hesaplamak yerine onu hafızadan geri alacağız. Bu yaklaşıma memoization denir. Daha fazla optimizasyon yapılabilir - örneğin, bir alt görev için artık bir çözüme ihtiyacımız olmadığından eminsek, onu bellekten atabilir, diğer ihtiyaçlar için serbest bırakabiliriz veya işlemci boştaysa ve çözümü biliyoruz. Henüz sayılmayan bazı alt görevler, daha sonra ihtiyacımız olacak, önceden çözebiliriz.

  Yukarıdakileri özetlersek, dinamik programlamanın problemin aşağıdaki özelliklerini kullandığını söyleyebiliriz:

  • örtüşen alt görevler;
  • optimal altyapı;
  • Sık karşılaşılan alt görevlerin çözümlerini ezberleme yeteneği.

  Dinamik programlama genellikle sorunları çözmek için iki yaklaşım kullanır:

  • yukarıdan aşağıya dinamik programlama: bir problem daha küçük alt problemlere bölünür, bunlar çözülür ve daha sonra orijinal problemi çözmek için birleştirilir. Ezberleme, sık karşılaşılan alt görevleri çözmek için kullanılır.
  • aşağıdan yukarıya dinamik programlama: orijinal problemi çözmek için sonradan ihtiyaç duyulan tüm alt görevler önceden hesaplanır ve daha sonra orijinal probleme bir çözüm oluşturmak için kullanılır. Bu yöntem, gerekli yığının boyutu ve işlev çağrılarının sayısı açısından yukarıdan aşağıya programlamadan daha iyidir, ancak bazen gelecekte hangi alt sorunları çözmemiz gerektiğini önceden anlamak kolay değildir.

  Programlama dilleri, "ada göre hesaplamayı" hızlandırmak için belirli bir dizi argümanla (not alma) bir işlevi çağırmanın sonucunu hatırlayabilir. Bazı dillerde bu özellik yerleşiktir (örneğin, Scheme, Common Lisp, Clojure, Perl) ve bazılarında ek uzantılar (C ++) gerektirir.

  Yöneylem araştırması ile ilgili tüm ders kitaplarında yer alan seri dinamik programlama ve 1960'larda keşfedilmesine rağmen şu anda çok az bilinen seri olmayan dinamik programlama (NSDP) bilinmektedir.

  Normal dinamik programlama, değişken ilişkilerin grafiğinin tam da gidilecek yol olduğu, seri olmayan dinamik programlamanın özel bir durumudur. Optimizasyon probleminin yapısını dikkate almak için doğal ve genel bir yöntem olan NSDP, kısıtlamalar setini ve/veya amaç fonksiyonunu özyinelemeli hesaplanabilir bir fonksiyon olarak kabul eder. Bu, önceki aşamalarda elde edilen bilgileri kullanarak aşamaların her birinde aşamalar halinde bir çözüm bulmanızı sağlar ve bu algoritmanın verimliliği doğrudan değişkenlerin karşılıklı ilişki grafiğinin yapısına bağlıdır. Bu grafik yeterince seyrekse, her aşamadaki hesaplama miktarı makul sınırlar içinde tutulabilir.

  Dinamik programlama kullanılarak çözülen problemlerin temel özelliklerinden biri toplanabilirliktir. Katkısız problemler diğer yöntemlerle çözülür. Örneğin, bir şirketin yatırımlarını optimize etmeye yönelik birçok görev, katkı içermez ve şirketin değeri yatırımlı ve yatırımsız karşılaştırılarak çözülür.

  Klasik dinamik programlama problemleri

  • En uzun ortak dizi sorunu: İki dizi verildiğinde, en uzun ortak diziyi bulmak istiyorsunuz.
  • En büyük artan diziyi bulma problemi: Bir dizi verildiğinde, en uzun artan diziyi bulmak istersiniz.
  • Editör mesafesi sorunu (Levenshtein mesafesi): iki satır verildiğinde, bir satırı diğerine dönüştüren minimum karakter silme, değiştirme ve ekleme sayısını bulmak gerekir.
  • Matris çarpım mertebesi problemi: verilen matrisler A 1 (\ displaystyle A_ (1)), …, Bir n (\ displaystyle A_ (n)), çarpımları için skaler işlemlerin sayısını en aza indirmek gerekir.
  • Yörünge seçimi sorunu
  • Tutarlı karar verme sorunu
  • Emek kullanım sorunu
  • Envanter yönetimi sorunu