Dinamik program - Dynamic programming

Şekil 1. Optimal alt yapıyı kullanarak bir grafikte en kısa yolu bulma; düz bir çizgi tek bir kenarı belirtir; dalgalı bir çizgi, bağlandığı iki köşe arasındaki en kısa yolu gösterir (diğer yollar arasında, gösterilmemiştir, aynı iki köşeyi paylaşır); kalın çizgi, başlangıçtan hedefe giden en kısa yoldur.

Dinamik programlama , hem matematiksel bir optimizasyon yöntemi hem de bir bilgisayar programlama yöntemidir. Yöntem tarafından geliştirilen Richard Bellman 1950'lerde ve gelen sayısız alanlarda uygulamalar bulmuştur havacılık mühendisliği için ekonomi .

Her iki bağlamda da karmaşık bir problemi özyinelemeli bir şekilde daha basit alt problemlere bölerek basitleştirmeyi ifade eder . Bazı karar problemleri bu şekilde ayrıştırılamasa da, zaman içinde birkaç noktaya yayılan kararlar genellikle tekrar tekrar bölünür. Aynı şekilde, bilgisayar biliminde, bir problem alt problemlere bölünerek ve daha sonra alt problemlere en uygun çözümleri yinelemeli olarak bularak en iyi şekilde çözülebiliyorsa, o zaman optimal altyapıya sahip olduğu söylenir .

Dinamik programlama yöntemlerinin uygulanabilmesi için alt problemler daha büyük problemlerin içinde özyinelemeli olarak yuvalanabiliyorsa, o zaman daha büyük problemin değeri ile alt problemlerin değerleri arasında bir ilişki vardır. Optimizasyon literatüründe bu ilişki Bellman denklemi olarak adlandırılır .

genel bakış

matematiksel optimizasyon

Matematiksel optimizasyon açısından, dinamik programlama genellikle bir kararı zaman içinde bir dizi karar adımına bölerek basitleştirmeyi ifade eder. Bu bir dizi tanımlanarak yapılır değeri fonksiyonları V 1 , V 2 , ..., V n alma y temsil eden bir değişken olarak durum bazen sistemin I , 1 ila n . Nedir? V N ( y ) durumunda elde edilen bir değerdir y son kez n . Daha önceki zamanlarda i  =  n  −1,  n  − 2, ..., 2, 1 olan V i değerleri Bellman denklemi adı verilen özyinelemeli bir ilişki kullanılarak geriye doğru çalışılarak bulunabilir . İçin i  2, ..., =  N , V ı -1 herhangi bir durum olarak y hesaplanır V i anda kararın kazanç basit bir fonksiyon (genellikle toplam) en üst düzeye i  - 1 ve fonksiyon V ı Bu karar verilirse sistemin yeni durumunda. Yana V i zaten gerekli durumları için hesaplanmıştır, yukarıdaki işlem verimi V i -1 bu durumları için. Son olarak, sistemin başlangıç ​​durumundaki V 1 optimal çözümün değeridir. Karar değişkenlerinin optimal değerleri, daha önce yapılmış olan hesaplamalar takip edilerek tek tek elde edilebilir.

kontrol teorisi

In Kontrol teorisi , tipik bir sorun kabul edilebilir bir kontrole bulmaktır sistem neden olur kabul edilebilir bir yörünge takip etmek sürekli zaman aralığına bir minimize maliyet fonksiyonu

Bu sorunun çözümü , optimal bir yörünge ve bir devam etme maliyeti işlevi üreten bir optimal kontrol yasası ya da politikasıdır . İkincisi, dinamik programlamanın temel denklemine uyar:

Bir kısmi diferansiyel denklem olarak bilinen Hamilton-Jacobi-Bellman denklemi bölgesi ve . Biri , , ve bilinmeyen fonksiyon cinsinden minimize etmenin ve ardından kısmi diferansiyel denklemi sınır koşulu ile çözmek için sonucu Hamilton-Jacobi-Bellman denkleminin yerine koyduğunu bulur . Uygulamada, bu genellikle kesin optimizasyon ilişkisine bazı ayrık yaklaşımlar için sayısal teknikler gerektirir .

Alternatif olarak, sürekli süreç, Hamilton-Jacobi-Bellman denklemine benzer bir aşağıdaki yineleme ilişkisine yol açan ayrık bir sistemle yaklaşıklanabilir:

de bir inci aşaması eşit aralıklı ayrı zaman aralıklarında ve burada ve üzere göstermektedirler ayrık yaklaşımlar ve . Bu fonksiyonel denklem, optimizasyon denkleminin ayrık yaklaşımının kesin bir çözümü için çözülebilen Bellman denklemi olarak bilinir .

Ekonomiden örnek: Ramsey'in optimal tasarruf sorunu

İktisatta amaç, genellikle bazı dinamik sosyal refah fonksiyonlarını en aza indirmek (minimumize etmek yerine) maksimize etmektir . Ramsey probleminde, bu fonksiyon tüketim miktarlarını fayda seviyeleri ile ilişkilendirir . Basitçe söylemek gerekirse, planlayıcı , zamanlararası seçim olarak bilinen, eş zamanlı tüketim ile gelecekteki tüketim ( üretimde kullanılan sermaye stokuna yatırım yoluyla) arasındaki ödünleşimle karşı karşıyadır . Gelecekteki tüketim sabit bir oranda iskonto edilir . Sermayenin geçiş denklemine ayrı bir yaklaşım şu şekilde verilir:

tüketim nerede , sermayedir ve Inada koşullarını sağlayan bir üretim fonksiyonudur . Bir başlangıç ​​sermaye stoğu olduğu varsayılır.

t periyodundaki tüketim olsun ve tüketimin tüketici yaşadığı sürece fayda sağladığını varsayalım . O kadar ki tüketici sabırsız varsayın indirgeyen bir faktörle gelecek programı b nereye her dönem, . Izin olmak sermaye süresi içinde t . Başlangıç ​​sermayesinin belirli bir miktar olduğunu varsayalım ve bu dönemin sermayesinin ve tüketiminin bir sonraki dönemin sermayesini olarak belirlediğini varsayalım , burada A pozitif bir sabit ve . Sermayenin negatif olamayacağını varsayalım. Daha sonra tüketicinin karar problemi aşağıdaki gibi yazılabilir:

herkes için tabi

Bu şekilde yazıldığında, problem karmaşık görünüyor çünkü tüm seçim değişkenlerini çözmeyi içeriyor . (Sermaye bir seçim değişkeni değildir - tüketicinin başlangıç ​​sermayesi verili olarak alınır.)

Bu sorunu çözmek için dinamik programlama yaklaşımı, onu bir dizi daha küçük kararlara bölmeyi içerir. Bunu yapmak için, bir sekansı tanımlamak değer fonksiyonları için, sermaye herhangi bir miktarda sahip olan bir değeri temsil etmektedir ki k her zaman, t . Ölümden sonra sermayeye sahip olmanın (varsayıma göre) hiçbir faydası yoktur .

Herhangi bir önceki zamandaki herhangi bir sermaye miktarının değeri , Bellman denklemi kullanılarak geriye dönük tümevarım yoluyla hesaplanabilir . Bu problemde, her biri için Bellman denklemi

tabi

Bu problem, daha önce yazdığımızdan çok daha basittir, çünkü sadece iki karar değişkeni içerir ve . Sezgisel olarak, tüketici doğumda tüm yaşam planını seçmek yerine, her seferinde bir adım atabilir. t zamanında , mevcut sermayesi verilir ve sadece cari tüketim ve tasarrufu seçmesi gerekir .

Bu sorunu gerçekten çözmek için geriye doğru çalışıyoruz. Basitlik için, mevcut sermaye düzeyi k olarak gösterilir . zaten biliniyor, bu yüzden bir kez Bellman denklemini kullanarak hesaplayabiliriz ve bu , tüm yaşam boyu ilk karar probleminin değeri olan ' ye ulaşana kadar devam eder. Başka bir deyişle, bir kez bildiğimizde , seçim değişkeninin nerede olduğunu , hangisinin maksimum olduğunu ve nerede olduğunu hesaplayabiliriz .

Geriye doğru çalışarak, zamandaki değer fonksiyonunun şu şekilde olduğu gösterilebilir :

buradaki her bir sabit ve bir zamanda tüketmek için en uygun miktarı olduğu

hangi basitleştirilebilir

Yaşlandıkça mevcut servetin daha büyük bir kısmını tüketmenin, sonunda kalan tüm serveti yaşamın son dönemi olan T döneminde tüketmenin optimal olduğunu görüyoruz .

Bilgisayar Programlama

Dinamik programlamanın uygulanabilmesi için bir problemin sahip olması gereken iki temel özellik vardır: optimal altyapı ve örtüşen alt problemler . Bir problem, örtüşmeyen alt problemlere en uygun çözümleri birleştirerek çözülebiliyorsa , stratejiye bunun yerine " böl ve yönet " denir . Bu nedenle birleştirme sıralama ve hızlı sıralama dinamik programlama sorunları olarak sınıflandırılmaz.

Optimal altyapı , belirli bir optimizasyon probleminin çözümünün, alt problemlerine yönelik optimal çözümlerin birleştirilmesiyle elde edilebileceği anlamına gelir. Bu tür optimal altyapılar genellikle özyineleme yoluyla tanımlanır . Örneğin, bir grafik verilmiştir G = (V, E) , en kısa yol p bir tepe noktasından U , bir tepe için v sergiler uygun alt: herhangi bir ara tepe almak w bu en kısa yol üzerindeki p . Eğer p gerçekten en kısa yol, o zaman alt yolları ayrılabilir p 1 den u için ağırlık ve p 2 ile ilgili a kadar , v Bu şekilde, sırayla, basit karşılık gelen tepe noktaları arasında en kısa yollar (aslında olan Algoritmalara Giriş bölümünde açıklanan kes ve yapıştır argümanı ). Bu nedenle, Bellman-Ford algoritmasının veya Floyd-Warshall algoritmasının yaptığı gibi , özyinelemeli bir şekilde en kısa yolları bulmak için çözüm kolayca formüle edilebilir .

Örtüşen alt problemler, alt problemlerin alanının küçük olması gerektiği anlamına gelir, yani problemi çözen herhangi bir özyinelemeli algoritma, yeni alt problemler üretmek yerine aynı alt problemleri tekrar tekrar çözmelidir. Örneğin, Fibonacci serisini oluşturmak için özyinelemeli formülasyonu düşünün: F i = F i -1 + F ben -2 , temel durum F 1  =  F 2  = 1 ile. Sonra F 43F 42  +  F 41 , ve F 42F 41  +  F 40 . Şimdi F 41 , hem F 43'ün hem de F 42'nin özyinelemeli alt ağaçlarında çözülüyor . Toplam alt problem sayısı aslında küçük olsa da (sadece 43 tanesi), bunun gibi naif bir özyinelemeli çözümü benimsersek aynı problemleri tekrar tekrar çözeriz. Dinamik programlama bu gerçeği dikkate alır ve her bir alt problemi yalnızca bir kez çözer.

Şekil 2. Fibonacci dizisi için alt problem grafiği. Ağaç olmaması , örtüşen alt problemlere işaret etmektedir.

Bu, iki yoldan biriyle elde edilebilir:

  • Yukarıdan aşağıya yaklaşım : Bu, herhangi bir sorunun özyinelemeli formülasyonunun doğrudan düşüşüdür. Herhangi bir problemin çözümü, alt problemlerinin çözümü kullanılarak özyinelemeli olarak formüle edilebiliyorsa ve alt problemleri örtüşüyorsa,alt problemlerin çözümlerikolayca bir tabloya kaydedilebilir veya saklanabilir. Ne zaman yeni bir alt problem çözmeye kalksak, önce tablonun çözülüp çözülmediğine bakarız. Bir çözüm kaydedildiyse doğrudan kullanabiliriz, aksi takdirde alt problemi çözer ve çözümünü tabloya ekleriz.
  • Aşağıdan yukarıya yaklaşım : Bir problemin çözümünü alt problemler açısından özyinelemeli olarak formüle ettiğimizde, problemi aşağıdan yukarıya bir şekilde yeniden formüle etmeyi deneyebiliriz: önce alt problemleri çözmeyi deneyin ve çözümlerini inşa etmek için kullanın. ve daha büyük alt problemlere çözümlere ulaşmak. Bu aynı zamanda genellikle küçük alt problemlerin çözümlerini kullanarak daha büyük ve daha büyük alt problemlere yinelemeli olarak çözümler üreterek tablo şeklinde yapılır. Örneğin, F 41 ve F 40 değerlerini zaten biliyorsak,doğrudan F 42 değerini hesaplayabiliriz.

Bazı programlama dilleri , ada göre arama değerlendirmesini hızlandırmak için, belirli bir argüman kümesiyle bir işlev çağrısının sonucunu otomatik olarak not alabilir (bu mekanizmaya ihtiyaca göre arama denir ). Bazı diller bunu taşınabilir olarak mümkün kılar (örneğin Scheme , Common Lisp , Perl veya D ). Bazı diller otomatik sahip memoization bu masaya olarak yerleşik, Prolog ve J ile memoization destekler, M. zarf. Her durumda, bu yalnızca referans olarak şeffaf bir işlev için mümkündür . Memoization, Wolfram Language gibi terim yeniden yazma tabanlı dillerde kolayca erişilebilir bir tasarım deseni olarak da karşımıza çıkar .

biyoinformatik

Dinamik programlama, dizi hizalama , protein katlama , RNA yapı tahmini ve protein-DNA bağlama gibi görevler için biyoinformatikte yaygın olarak kullanılmaktadır . Protein-DNA bağlanması için ilk dinamik programlama algoritmaları, 1970'lerde ABD'de Charles DeLisi ve SSCB'de Georgii Gurskii ve Alexander Zasedatelev tarafından bağımsız olarak geliştirildi . Son zamanlarda bu algoritmalar , özellikle nükleozom konumlandırma ve transkripsiyon faktörü bağlanması çalışmalarında, biyoinformatik ve hesaplamalı biyolojide çok popüler hale geldi .

Örnekler: Bilgisayar algoritmaları

Dijkstra'nın en kısa yol problemi için algoritması

Dinamik programlama açısından, Dijkstra'nın en kısa yol problemi için algoritması , Reaching metodu ile en kısa yol problemi için dinamik programlama fonksiyonel denklemini çözen ardışık bir yaklaşım şemasıdır .

Aslında, Dijkstra'nın algoritmanın arkasındaki mantıkla ilgili açıklaması, yani

Problem 2. Verilen iki düğüm ve .

Biz eğer gerçeğini kullanmak minimal yolda bir düğümdür için , ikincisi bilgisi itibaren asgari yolun bilindiğini ima etmek .

bir başka kelimelerle açıklayabilir olan Bellman ünlü En iyilik İlkesinin bağlamında en kısa yol problemi .

Fibonacci Dizisi

Hesaplanmasında dinamik programlama kullanılarak N inci üyesinin Fibonacci dizisi büyük ölçüde performansı arttırır. İşte doğrudan matematiksel tanımlamaya dayanan naif bir uygulama:

function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)

Diyelim fib(5)ki çağırırsak, işlevi aynı değerde birçok farklı kez çağıran bir çağrı ağacı ürettiğimize dikkat edin :

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Özellikle fib(2)sıfırdan üç kez hesaplanmıştır. Daha büyük örneklerde, çok daha fazla değer fibveya alt problemler yeniden hesaplanır ve üstel bir zaman algoritmasına yol açar.

Şimdi, basit bir harita nesnemiz olduğunu varsayalım , m , bunun her bir değerini fibsonucuyla eşleştirir ve onu kullanmak ve güncellemek için fonksiyonumuzu değiştiririz. Ortaya çıkan işlev , üstel zaman yerine yalnızca O ( n ) zaman gerektirir (ancak O ( n ) alanı gerektirir ):

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Halihazırda hesaplanmış olan bu değerleri kaydetme tekniğine memoization denir ; Bu yukarıdan aşağıya yaklaşımdır, çünkü önce problemi alt problemlere böleriz ve sonra değerleri hesaplar ve depolarız.

In aşağıdan yukarıya yaklaşımı, biz daha küçük değerleri hesaplamak fibsonra onlardan daha büyük değerler oluşturmak, ilk. Bu yöntem aynı zamanda n − 1 kez tekrar eden bir döngü içerdiğinden O( n ) zamanını kullanır , ancak O( n ) boşluk gerektiren yukarıdan aşağıya yaklaşımın aksine yalnızca sabit (O(1)) alan alır . haritayı saklayın.

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
    return currentFib

Her iki örnekte de, yalnızca fib(2)bir kez hesaplıyoruz ve ardından her ikisi de değerlendirildiğinde hesaplamak yerine hem fib(4)ve ' yi hesaplamak için kullanıyoruz fib(3).

Yukarıdaki yöntem aslında büyük n için zaman alır, çünkü her biri bit içeren iki tam sayının eklenmesi zaman alır . ( N inci Fibonacci numarası vardır bit.) Ayrıca, Fibonacci dizisi, için bir kapalı bir şekli vardır Binet formülü olarak bilinen başka, inci süreli olabilir hesaplanan yaklaşık olarak yukarıdaki dinamik programlama tekniğe göre daha etkilidir zaman, . Bununla birlikte, basit yineleme , hızlı matris üstelleştirme ile yaklaşık bir algoritmaya yol açan matris formunu doğrudan verir .

Bir tür dengeli 0-1 matris

Bir konumlarına ya sıfır ya da bir, atama değerleri sorunu göz önünde n x n ile, matris , n , her satır, her sütun tam olarak içerecek şekilde daha da N / 2 sıfır ve n / 2 olanlar. Bir verilen için kaç farklı atama olduğunu soruyoruz . Örneğin, n = 4 olduğunda , dört olası çözüm vardır:

En az üç olası yaklaşım vardır: kaba kuvvet , geri izleme ve dinamik programlama.

Kaba kuvvet, tüm sıfırlar ve birler atamalarını kontrol etmekten ve dengeli satır ve sütunlara sahip olanları saymaktan oluşur ( n / 2 sıfır ve n / 2 bir ). Bulunmadığından mümkün ödevler ve mantıklı atamaları, bu strateji belki yukarı dışında pratik değildir .

Bu problem için geriye dönük izleme, matris elemanlarının bazı sırasını seçmekten ve yinelemeli olarak birler veya sıfırlar yerleştirmekten, her satırda ve sütunda atanmamış elemanların sayısı artı birler veya sıfırların sayısının her ikisinin de en az n / olduğunu kontrol etmekten ibarettir. 2 . Kaba kuvvetten daha karmaşık olsa da, bu yaklaşım her çözümü bir kez ziyaret edecek ve göreceğimiz gibi , çözümlerin sayısı n  = 8 için zaten 116.963.796.250 olduğundan, altıdan büyük n için onu pratik hale getirecektir.

Dinamik programlama, hepsini ziyaret etmeden çözümlerin sayısını saymayı mümkün kılar. İlk satır için geri izleme değerlerini hayal edin – her ilk satır değeri için elde edilen çözümleri doğru bir şekilde sayabilmek için kalan satırlar hakkında hangi bilgilere ihtiyacımız var? 1 ≤ kn olan, satırları sıfırlar ve birler içeren k × n panolarını ele alıyoruz . Fonksiyon f hangi memoization haritaları vektörleri uygulandığında , n kabul panoları (eriyikleri) sayısı tam sayılar çiftleri. Her sütun için bir çift vardır ve iki bileşeni sırasıyla o sütuna henüz yerleştirilmemiş sıfırların ve birlerin sayısını gösterir. ( argümanlar veya bir element vektörü ) değerini ararız . Alt problem oluşturma süreci , tahtanın en üst satırı için olası atamaların her biri üzerinde yineleme yapmayı ve her sütundan geçerek, üst satır için atamanın içerip içermediğine bağlı olarak, o sütun için çiftin uygun elemanından bir tane çıkarmayı içerir. bu konumda sıfır veya bir. Sonuçlardan herhangi biri negatifse, atama geçersizdir ve çözüm kümesine katkıda bulunmaz (özyineleme durur). Aksi takdirde, k × n kartının en üst satırı için bir atamamız olur ve kalan ( k − 1) × n kartının çözüm sayısını özyinelemeli olarak hesaplar , üst satırın her kabul edilebilir ataması için çözüm sayısını toplar ve geri dönerek döneriz. hafızaya alınan toplam. Temel durum, 1 × n'lik bir tahta için meydana gelen önemsiz alt problemdir . Bu kart için çözüm sayısı, vektörün n /2 ve n /2 permütasyon olup olmamasına bağlı olarak sıfır veya birdir .

Örneğin, yukarıda gösterilen ilk iki panoda vektör dizileri şöyle olacaktır:

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0      0      1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

Çözeltilerin sayısı (dizi A058527 olarak OEIS ) olduğu

Dinamik programlama yaklaşımının MAPLE uygulamasına bağlantılar , dış bağlantılar arasında bulunabilir .

dama tahtası

Bir göz önünde dama ile n x n kareler ve bir maliyet fonksiyonu c(i, j)kare ile bağlantılı bir maliyet döner (i,j)( isatır olan jsütun olmak üzere). Örneğin (5 × 5 dama tahtasında),

5 6 7 4 7 8
4 7 6 1 1 4
3 3 5 7 8 2
2 - 6 7 0 -
1 - - *5* - -
1 2 3 4 5

Böylece c(1, 3) = 5

Diyelim ki ilk sıradaki (yani sıradaki) herhangi bir karede başlayabilen bir denetleyici vardı ve son sıraya ulaşmak için en kısa yolu (ziyaret edilen her bir sıradaki minimum maliyetlerin toplamı) bilmek istediniz; denetleyicinin yalnızca çapraz olarak sola ileri, çapraz olarak sağa veya düz ileri hareket edebileceğini varsayarsak. Olduğunu, bir denetleyicisi (1,3)geçebilirsiniz (2,2), (2,3)ya (2,4).

5
4
3
2 x x x
1 Ö
1 2 3 4 5

Bu problem optimal altyapıyı gösterir . Yani, tüm problemin çözümü, alt problemlerin çözümlerine dayanır. q(i, j)olarak bir fonksiyon tanımlayalım .

q ( i , j ) = ( i , j ) karesine ulaşmak için minimum maliyet .

Rank'tan başlayıp rank'e ninerek 1, bu fonksiyonun değerini her bir ardışık sıralamadaki tüm kareler için hesaplarız. Her sırada minimum değeri tutan kareyi seçmek bize rank nve rank arasındaki en kısa yolu verir 1.

Fonksiyon q(i, j), altındaki üç kareden herhangi birine ulaşmak için minimum maliyete eşittir (çünkü ona ulaşabilen tek kareler bunlardır) artı c(i, j). Örneğin:

5
4 A
3 B C NS
2
1
1 2 3 4 5

Şimdi q(i, j)biraz daha genel terimlerle tanımlayalım :

Bu denklemin ilk satırı 1, en alt sınırda ve nen yüksek sınırda indekslenen kareler olarak modellenen bir tahta ile ilgilidir . İkinci satır, ilk sırada ne olduğunu belirtir; temel durum sağlar. Üçüncü satır, özyineleme, önemli kısımdır. A,B,C,DÖrnekteki terimleri temsil eder . Bu tanımdan, için basit özyinelemeli kod türetebiliriz q(i, j). Aşağıdaki sözde kodda, ntahtanın boyutudur c(i, j), maliyet işlevidir ve min()bir dizi değerin minimumunu döndürür:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

Bu işlev, gerçek yolu değil, yalnızca yol maliyetini hesaplar. Aşağıdaki gerçek yolu tartışıyoruz. Bu, Fibonacci sayıları örneğinde olduğu gibi, çok yavaştır çünkü o da örtüşen alt problemler niteliğini sergiler . Yani, aynı yol maliyetlerini tekrar tekrar hesaplar. Ancak, q[i, j]bir fonksiyon kullanmak yerine yol maliyetlerini iki boyutlu bir dizide saklarsak, aşağıdan yukarıya doğru çok daha hızlı hesaplayabiliriz . Bu yeniden hesaplamayı önler; dizi q[i, j]için gereken tüm değerler önceden yalnızca bir kez hesaplanır. için önceden hesaplanmış değerler, (i,j)gerektiğinde basitçe aranır .

Ayrıca gerçek en kısa yolun ne olduğunu da bilmemiz gerekiyor. Bunu yapmak için başka bir dizi kullanıyoruz p[i, j]; bir önceki dizi . Bu dizi, herhangi bir kareye giden yolu kaydeder s. söğesinin öncülü q[i, j], önceden hesaplanan yol maliyetinin indeksine (in ) göre bir ofset olarak modellenir s. Yolun tamamını yeniden oluşturmak için önce 'yi s, sonra o karenin öncesini, sonra o karenin öncesini ve başlangıç ​​karesine ulaşana kadar özyinelemeli olarak devam ederiz. Aşağıdaki kodu göz önünde bulundurun:

function computeShortestPathArrays()
    for x from 1 to n
        q[1, x] := c(1, x)
    for y from 1 to n
        q[y, 0]     := infinity
        q[y, n + 1] := infinity
    for y from 2 to n
        for x from 1 to n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            if m = q[y-1, x-1]
                p[y, x] := -1
            else if m = q[y-1, x]
                p[y, x] :=  0
            else
                p[y, x] :=  1

Şimdi gerisi, minimumu bulmak ve yazdırmak için basit bir mesele.

function computeShortestPath()
    computeShortestPathArrays()
    minIndex := 1
    min := q[n, 1]
    for i from 2 to n
        if q[n, i] < min
            minIndex := i
            min := q[n, i]
    printPath(n, minIndex)
function printPath(y, x)
    print(x)
    print("<-")
    if y = 2
        print(x + p[y, x])
    else
        printPath(y-1, x + p[y, x])

Sıra hizalama

Olarak genetik , dizi hizalama dinamik programlama gerekli olan önemli bir uygulamasıdır. Tipik olarak sorun, bir öğeyi değiştiren, ekleyen veya kaldıran düzenleme işlemlerini kullanarak bir diziyi diğerine dönüştürmekten oluşur. Her işlemin ilişkili bir maliyeti vardır ve amaç, en düşük toplam maliyetle düzenleme sırasını bulmaktır .

Sorun doğal olarak bir özyineleme olarak ifade edilebilir, A dizisi en uygun şekilde B dizisine şu şekilde düzenlenir:

  1. B'nin ilk karakterini eklemek ve A ile B'nin kuyruğunu en uygun şekilde hizalamak
  2. A'nın ilk karakterinin silinmesi ve A ve B'nin kuyruğunun optimal hizalanmasının gerçekleştirilmesi
  3. A'nın ilk karakterini B'nin ilk karakteriyle değiştirmek ve A ve B'nin kuyruklarının optimal hizalamalarını gerçekleştirmek.

Kısmi hizalamalar, (i,j) hücresinin A[1..i]'den B[1..j]'ye optimal hizalamanın maliyetini içerdiği bir matriste tablo haline getirilebilir. (i,j) hücresindeki maliyet, ilgili işlemlerin maliyetinin komşu hücrelerin maliyetine eklenmesi ve optimumun seçilmesiyle hesaplanabilir.

Farklı varyantlar mevcuttur, bkz. Smith-Waterman algoritması ve Needleman-Wunsch algoritması .

Hanoi Kulesi yapboz

Hanoi Kuleleri'nin bir model seti (8 diskli)
T(4,3) için Hanoi Kulesi bulmacasının animasyonlu bir çözümü .

Hanoi kuleleri ya Kuleleri Hanoi bir olan matematiksel oyun veya bulmaca . Üç çubuktan ve herhangi bir çubuğa kayabilen farklı boyutlarda birkaç diskten oluşur. Bulmaca, en küçük olanı üstte olacak şekilde bir çubuk üzerinde artan büyüklük sırasına göre düzgün bir yığın halindeki disklerle başlar, böylece konik bir şekil oluşturur.

Bulmacanın amacı, aşağıdaki kurallara uyarak tüm yığını başka bir çubuğa taşımaktır:

  • Bir seferde yalnızca bir disk taşınabilir.
  • Her hareket, çubuklardan birinden üst diski alıp, o çubukta halihazırda mevcut olabilecek diğer disklerin üzerine, başka bir çubuğa kaydırmaktan ibarettir.
  • Daha küçük bir diskin üzerine hiçbir disk yerleştirilemez.

Dinamik programlama çözümü, fonksiyonel denklemin çözülmesinden oluşur.

S(n,h,t) = S(n-1,h, not(h,t)) ; S(1,h,t); S(n-1,değil(h,t),t)

burada n hareket ettirilecek disk sayısını, h ana çubuğu, t hedef çubuğu belirtir,(h,t) üçüncü çubuğu (ne h ne de t) ifade etmez, ";" birleştirmeyi ifade eder ve

S(n, h, t) := h çubuğundan t çubuğuna hareket ettirilecek n adet diskten oluşan bir problemin çözümü.

n=1 için sorun önemsizdir, yani S(1,h,t) = "h çubuğundan t çubuğuna bir disk taşıyın" (sadece bir disk kaldı).

Bu çözümün gerektirdiği hamle sayısı 2 n  − 1'dir. Amaç, hareket sayısını (çevrimsiz) maksimize etmekse, dinamik programlama fonksiyonel denklemi biraz daha karmaşıktır ve 3 n  − 1 hamle gereklidir.

Yumurta bırakma bulmacası

Aşağıda, N=2 yumurta ve H=36 katlı bir binanın yer aldığı bu ünlü bulmaca örneğinin açıklaması yer almaktadır :

36 katlı bir binadaki hangi katlardan yumurta bırakmanın güvenli olduğunu ve hangilerinin inişte yumurtaların kırılmasına neden olacağını bilmek istediğimizi varsayalım ( birinci katın zemin seviyesinde olduğu ABD İngilizcesi terminolojisini kullanarak ). Birkaç varsayımda bulunuyoruz:
  • Düşüşten kurtulan bir yumurta tekrar kullanılabilir.
  • Kırık bir yumurta atılmalıdır.
  • Düşmenin etkisi tüm yumurtalar için aynıdır.
  • Bir yumurta düştüğünde kırılırsa, daha yüksek bir pencereden düştüğünde kırılır.
  • Bir yumurta bir düşüşten kurtulursa, o zaman daha kısa bir düşüşten kurtulur.
  • Birinci kat pencerelerinin yumurta kırdığı veya yumurtaların 36. kat pencerelerinden sağ çıkabileceği göz ardı edilmemiştir.
Sadece bir yumurta mevcutsa ve doğru sonucu elde ettiğimizden emin olmak istiyorsak, deney sadece bir şekilde yapılabilir. Yumurtayı birinci kat penceresinden bırakın; Eğer hayatta kalırsa, ikinci kat penceresinden at. Kırılana kadar yukarı doğru devam edin. En kötü durumda, bu yöntem 36 dışkı gerektirebilir. Diyelim ki 2 yumurta mevcut. Her durumda çalışması garanti edilen en düşük yumurta dışkısı sayısı nedir?

Bu bulmaca için bir dinamik programlama fonksiyonel denklemi türetmek için , dinamik programlama modelinin durumu bir çift s = (n,k) olsun, burada

n = mevcut test yumurtası sayısı, n = 0, 1, 2, 3, ..., N  − 1.
k = henüz test edilecek (ardışık) kat sayısı, k = 0, 1, 2, ..., H  − 1.

Örneğin, s = (2,6), iki test yumurtasının mevcut olduğunu ve 6 (ardışık) katın henüz test edilmediğini gösterir. Sürecin ilk durumu s = ( N , H )'dir, burada N , deneyin başlangıcında mevcut olan test yumurtalarının sayısını belirtir. İşlem, daha fazla test yumurtası olmadığında ( n = 0) veya k = 0 olduğunda (hangisi önce gelirse ) sona erer . Sonlandırma s = (0, k ) ve k  > 0 durumunda gerçekleşirse, test başarısız olur.

Şimdi izin ver

W ( n , k ) = sürecin s = ( n , k ) durumunda olduğu göz önüne alındığında en kötü durum senaryosu altında kritik katın değerini belirlemek için gereken minimum deneme sayısı .

O zaman gösterilebilir ki

W ( n , k ) = 1 + min{maks( W ( n − 1, x − 1), W ( n , kx )): x = 1, 2, ..., k }

ile W ( n , 0) = Tüm için 0 , n  > 0 ve W (1, k ) = k tüm  k . n ve  k değerlerini sistematik olarak artırarak bu denklemi yinelemeli olarak çözmek kolaydır .

Farklı bir parametrelendirme kullanarak daha hızlı DP çözümü

Yukarıdaki çözümün bir DP çözümü ile zaman aldığına dikkat edin . Bu kadar geliştirilebilir optimum ikili arama tarafından zaman beri, yukarıdaki nüks içinde de artmaktadır süre içinde azalmaktadır böylece yerel minimum, küresel bir minimumdur. Ayrıca, DP tablosundaki her hücre için optimali saklayarak ve bir önceki hücre için değerine atıfta bulunarak, her hücre için optimali , zamana göre iyileştirerek sabit zamanda bulunabilir . Ancak, sorunun farklı bir parametrelenmesini içeren daha da hızlı bir çözüm var:

Yumurtaların inci kattan düştüğünde kırılacağı toplam kat sayısı olsun (Yukarıdaki örnek almak ile eşdeğerdir ).

Yumurtanın kırılması için düşürülmesi gereken minimum zemin olsun .

Denemeler ve yumurtalar kullanılarak ayırt edilebilen maksimum değer sayısı olsun .

Sonra hepsi için .

Optimal stratejide ilk yumurtanın düştüğü zemin olsun .

İlk yumurta girdiyse, dan için ve en fazla kullanan ayırt denemeden ve yumurta.

İlk yumurta kırmak olmasaydı, dan için kullanılması ve ayırt denemeden ve yumurta.

Bu nedenle, .

O zaman problem, minimumu bulmakla eşdeğerdir, öyle ki .

Bunu yapmak için, zaman alacak olan artan sırayla hesaplayabiliriz .

Bu nedenle, durumunu ayrı ayrı ele alırsak , algoritma zaman alacaktır .

Ancak yineleme bağıntısı aslında herkes için özdeşlik kullanılarak zaman içinde hesaplanabilen vererek çözülebilir .

Herkes için , bir algoritma vererek bulmak için ikili arama yapabiliriz .

matris zincir çarpımı

Matris zincir çarpımı, dinamik programlamanın faydasını gösteren iyi bilinen bir örnektir. Örneğin, mühendislik uygulamaları genellikle bir matris zincirini çarpmak zorundadır. Örneğin 100×100 gibi büyük boyutlu matrisler bulmak şaşırtıcı değildir. Bu nedenle görevimiz matrisleri çarpmaktır . Matris çarpımı değişmeli değil, birleştiricidir; ve aynı anda sadece iki matrisi çarpabiliriz. Böylece, bu matris zincirini birçok farklı şekilde çoğaltabiliriz, örneğin:

((A 1 × A 2 ) × A 3 ) × ... A n
A 1 ×(((A 2 ×A 3 )× ... ) × A n )
(A 1 × A 2 ) × (A 3 × ... A n )

ve bunun gibi. Bu matris zincirini çarpmanın sayısız yolu vardır. Hepsi aynı nihai sonucu üretecek, ancak hangi belirli matrislerin çarpıldığına bağlı olarak hesaplanması az ya da çok zaman alacaktır. A matrisinin m×n boyutlarına ve B matrisinin n×q boyutlarına sahip olması durumunda, C=A×B matrisinin boyutları m×q olacaktır ve m*n*q skaler çarpımları gerektirecektir ( amaçlar için basit bir matris çarpım algoritması kullanarak). illüstrasyon).

Örneğin, A, B ve C matrislerini çarpalım. Boyutlarının sırasıyla m×n, n×p ve p×s olduğunu varsayalım. A×B×C matrisi m×s boyutunda olacaktır ve aşağıda gösterilen iki yolla hesaplanabilir:

  1. Ax(B×C) Bu matris çarpım sırası nps + mns skaler çarpımlarını gerektirecektir.
  2. (A×B)×C Bu matris çarpım sırası mnp + mps skaler hesaplamaları gerektirecektir.

m = 10, n = 100, p = 10 ve s = 1000 olduğunu varsayalım. Dolayısıyla zinciri çarpmanın ilk yolu 1.000.000 + 1.000.000 hesaplama gerektirecektir. İkinci yol sadece 10.000+100.000 hesaplama gerektirecektir. Açıkçası, ikinci yol daha hızlıdır ve bu parantez düzenini kullanarak matrisleri çarpmalıyız.

Bu nedenle, sonucumuz parantez sırasının önemli olduğu ve görevimizin en uygun parantez sırasını bulmak olduğudur.

Bu noktada, birkaç seçeneğimiz var, bunlardan biri, problemi örtüşen problemlere bölecek ve optimal parantez düzenini hesaplayacak bir dinamik programlama algoritması tasarlamak. Dinamik programlama çözümü aşağıda sunulmuştur.

i matrisinden j matrisine bir matris zincirini çarpmak için gereken minimum skaler çarpma sayısına m[i,j] diyelim (yani A i × .... × A j , yani i<=j). Zinciri, i <= k < j olacak şekilde bir k matrisinde böleriz ve hangi kombinasyonun minimum m[i,j] ürettiğini bulmaya çalışırız.

Formül:

       if i = j, m[i,j]= 0
       if i < j, m[i,j]= min over all possible values of k (m[i,k]+m[k+1,j] + ) 

burada k aralıkları i için j  - 1.

  • i matrisinin satır boyutu,
  • k matrisinin sütun boyutudur,
  • j matrisinin sütun boyutudur.

Bu formül aşağıda gösterildiği gibi kodlanabilir, burada "zincir" girdi parametresi matrislerin zinciridir, yani :

function OptimalMatrixChainParenthesis(chain)
    n = length(chain)
    for i = 1, n
        m[i,i] = 0    // Since it takes no calculations to multiply one matrix
    for len = 2, n
        for i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinity      // So that the first calculation updates
            for k = i, j-1
                q = m[i, k] + m[k+1, j] + 
                if q < m[i, j]     // The new order of parentheses is better than what we had
                    m[i, j] = q    // Update
                    s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

Şimdiye kadar, tüm olası m [ i , j ] için değerleri hesapladık, i matrisinden j matrisine bir zinciri çarpmak için gereken minimum hesaplama sayısı ve karşılık gelen "bölünme noktası" s [ i , j ] 'yi kaydettik . Örneğin, A 1 ×A 2 ×A 3 ×A 4 zincirini çarpıyorsak ve m [1, 3] = 100 ve s [1, 3] = 2 olduğu ortaya çıkarsa , bu, 1'den 3'e kadar olan matrisler için parantez ve bu matrisleri çarpmak için 100 skaler hesaplama gerekir.

Bu algoritma, tüm olası i ve j değerleri için girişlere sahip olacak "tablolar" m [, ] ve s [, ] üretecektir. Tüm zincir için nihai çözüm, s[1, n]'de karşılık gelen bölünme ile m[1, n]'dir. Çözümün çözülmesi, en baştan başlayıp temel duruma, yani tekli matrislerin çarpımına ulaşana kadar devam edecek şekilde özyinelemeli olacaktır.

Bu nedenle, bir sonraki adım, zinciri fiilen bölmek, yani parantezleri (en uygun şekilde) ait oldukları yere yerleştirmektir. Bu amaçla aşağıdaki algoritmayı kullanabiliriz:

function PrintOptimalParenthesis(s, i, j)
    if i = j
        print "A"i
    else
        print "(" 
        PrintOptimalParenthesis(s, i, s[i, j]) 
        PrintOptimalParenthesis(s, s[i, j] + 1, j) 
        print ")"

Tabii ki, bu algoritma gerçek çarpma için kullanışlı değildir. Bu algoritma, sonucun nasıl göründüğünü görmenin yalnızca kullanıcı dostu bir yoludur.

Uygun bölmeleri kullanarak matrisleri gerçekten çarpmak için aşağıdaki algoritmaya ihtiyacımız var:

   function MatrixChainMultiply(chain from 1 to n)       // returns the final matrix, i.e. A1×A2×... ×An
      OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
      OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

   function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
      if i < j
         // keep on splitting the chain and multiplying the matrices in left and right sides
         LeftSide = OptimalMatrixMultiplication(s, i, s[i, j])
         RightSide = OptimalMatrixMultiplication(s, s[i, j] + 1, j)
         return MatrixMultiply(LeftSide, RightSide) 
      else if i = j
         return Ai   // matrix at position i
      else 
         print "error, i <= j must hold"

    function MatrixMultiply(A, B)    // function that multiplies two matrices
      if columns(A) = rows(B) 
         for i = 1, rows(A)
            for j = 1, columns(B)
               C[i, j] = 0
               for k = 1, columns(A)
                   C[i, j] = C[i, j] + A[i, k]*B[k, j] 
               return C 
      else 
          print "error, incompatible dimensions."

Tarih

Dinamik programlama terimi , ilk olarak 1940'larda Richard Bellman tarafından , birinin birbiri ardına en iyi kararları bulması gereken sorunları çözme sürecini tanımlamak için kullanıldı. 1953'e gelindiğinde, özellikle daha küçük karar problemlerini daha büyük kararların içine yerleştirmeye atıfta bulunarak, bunu modern anlamda rafine etti ve daha sonra alan, IEEE tarafından bir sistem analizi ve mühendislik konusu olarak kabul edildi . Bellman'ın katkısı, bir optimizasyon problemini özyinelemeli biçimde yeniden ifade eden dinamik programlamanın merkezi bir sonucu olan Bellman denklemi adına hatırlanır .

Bellman , otobiyografisinde, Eye of the Hurricane: An Autobiography'de dinamik programlama teriminin arkasındaki mantığı açıklıyor :

Güz çeyreğini (1950) RAND'da geçirdim . İlk işim çok aşamalı karar süreçleri için bir isim bulmaktı. İlginç bir soru, "Dinamik programlama adı nereden geldi?" 1950'ler matematiksel araştırmalar için iyi yıllar değildi. Washington'da Wilson adında çok ilginç bir beyefendimiz vardı . Savunma Bakanıydı ve aslında "araştırma" kelimesine karşı patolojik bir korkusu ve nefreti vardı. Bu terimi hafifçe kullanmıyorum; kesin kullanıyorum. Onun yanında insanlar araştırma terimini kullanırsa yüzü kaplanır, kızarır ve şiddete başvurur. O halde matematiksel terimi hakkında nasıl hissettiğini hayal edebilirsiniz. RAND Corporation, Hava Kuvvetleri tarafından istihdam edildi ve Hava Kuvvetleri, esasen patronu olarak Wilson'a sahipti. Bu nedenle, Wilson'ı ve Hava Kuvvetlerini RAND Corporation'da gerçekten matematik yaptığım gerçeğinden korumak için bir şeyler yapmam gerektiğini hissettim. Hangi başlığı, hangi ismi seçebilirdim? Her şeyden önce planlamayla, karar vermeyle, düşünmeyle ilgileniyordum. Ancak planlama, çeşitli nedenlerle iyi bir kelime değildir. Bu nedenle "programlama" kelimesini kullanmaya karar verdim. Bunun dinamik olduğu, bunun çok aşamalı olduğu, bunun zamana göre değiştiği fikrini aşmak istedim. Bir taşla iki kuş vuralım diye düşündüm. Klasik fiziksel anlamda kesinlikle kesin anlamı olan, yani dinamik olan bir kelimeyi ele alalım. Sıfat olarak da çok ilginç bir özelliği vardır ve dinamik kelimesini aşağılayıcı bir anlamda kullanmak imkansızdır. Muhtemelen aşağılayıcı bir anlam verecek bir kombinasyon düşünmeye çalışın. Bu imkansız. Bu yüzden dinamik programlamanın iyi bir isim olduğunu düşündüm. Bir Kongre üyesinin bile itiraz edemeyeceği bir şeydi. Bu yüzden faaliyetlerim için bir şemsiye olarak kullandım.

—  Richard Bellman, Eye of the Hurricane: An Autobiography (1984, sayfa 159)

Dinamik sözcüğü , problemlerin zamanla değişen yönünü yakalamak için ve kulağa etkileyici geldiği için Bellman tarafından seçilmiştir. Programlama kelimesi , eğitim veya lojistik için askeri bir program anlamında optimal bir program bulmak için yöntemin kullanımına atıfta bulundu . Bu kullanım, matematiksel optimizasyon ile eşanlamlı olan doğrusal programlama ve matematiksel programlama ifadelerindekiyle aynıdır .

Terimin kökenine ilişkin yukarıdaki açıklama eksiktir. Russell ve Norvig'in kitaplarında yukarıdaki hikayeye atıfta bulunarak yazdıkları gibi: "Bu kesinlikle doğru olamaz, çünkü bu terimi kullanan ilk makalesi (Bellman, 1952), Wilson 1953'te Savunma Bakanı olmadan önce ortaya çıktı." Ayrıca, Harold J. Kushner'ın Bellman'ı hatırladığı bir konuşmasında bir yorum var . Kushner'ı Bellman'dan bahsederken alıntılayarak: "Öte yandan, ona aynı soruyu sorduğumda, dinamik ekleyerek Dantzig'in lineer programlamasını yükseltmeye çalıştığını söyledi. Belki de her iki motivasyon da doğruydu."

Dinamik programlama kullanan algoritmalar

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar