Dinamik Programlama

Dinamik Programlama (DP; İng. dynamic programming, DP) — karmaşık optimizasyon problemlerini çözmek için kullanılan, orijinal problemi daha basit alt problemlerden oluşan bir diziye bölen bir yöntemdir. Yöntem, tüm problemin optimal çözümünün alt problemlerin optimal çözümlerinden inşa edilebildiği çok adımlı karar alma süreçlerine uygulanır.

Terim, 1950'lerde Amerikalı matematikçi Richard Bellman tarafından ortaya atılmıştır. Bu bağlamda "programlama" kelimesi, bilgisayar kodu yazmak anlamında değil, "planlama" veya "optimal eylem planı oluşturma" anlamında kullanılmaktadır.

Temel Özellikler ve Teoremler

Dinamik programlamanın bir probleme uygulanabilirliği, o problemin iki temel özelliğe sahip olmasıyla belirlenir.

Bellman'ın Optimallik İlkesi

Yöntemin merkezi kavramı Bellman'ın optimallik ilkesidir (İng. Bellman's principle of optimality). İlke şunu belirtir: başlangıç durumu ve başlangıç kararı ne olursa olsun, sonraki kararlar ilk kararın sonucunda elde edilen duruma göre optimal bir strateji oluşturmalıdır.

Başka bir deyişle, optimal bir yörüngenin herhangi bir parçası kendi başına da optimaldir. Bu özellik, genel problemin daha basit alt problemlerden oluşan bir diziye bölünmesini ve bunların özyinelemeli olarak çözülmesini mümkün kılar.

Örtüşen Alt Problemler - Overlapping Subproblems

Bir problem, özyinelemeli çözümü sırasında aynı alt problemlerin defalarca ortaya çıkması durumunda örtüşen alt problemler (İng. overlapping subproblems) özelliğine sahiptir. DP, daha önce çözülen alt problemlerin çözümlerini saklayarak (bu teknik memoization veya tablo oluşturma olarak adlandırılır) tekrarlanan hesaplamaları önler ve bu sayede naif özyinelemeli aramaya kıyasla verimliliği önemli ölçüde artırır.

Bellman Denklemi

Optimallik ilkesinden, yöntemin temel yinelemeli bağıntısı olan Bellman denklemi türetilir. Bu denklem, mevcut durumun "değerini" (optimal kazanç veya maliyet) sonraki durumların değerleriyle ilişkilendirir. Toplamsal amaç fonksiyonuna sahip deterministik çok adımlı bir süreç için genel biçimi şöyledir:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

burada:

• $k$ — adım numarası ($m$'ten 1'e kadar);
• $x$ — $k-1$ adımındaki sistemin durumu;
• $y$ — $k$ adımında alınan kontrol kararı;
• ${\phi }_k(x,y)$ — k. adımdaki kazanç (veya maliyet);
• $f_k(x,y)$ — sistemin yeni durumunu tanımlayan fonksiyon;
• $V_k(s)$ — $k$ adımında $s$ durumundan başlayan alt problemin amaç fonksiyonunun optimal değeri.

Denklem, genellikle son adımdan ilk adıma doğru ilerleyerek "sondan başa" sıralı biçimde çözülür.

Uygulama Örnekleri

• Grafta en kısa yol problemi: Bu problem, en kısa yolun herhangi bir parçasının kendisinin de en kısa olması nedeniyle optimal alt yapı özelliğine sahiptir. Bellman-Ford ve Floyd-Warshall algoritmaları, bu problemi çözmek için DP uygulamasının klasik örnekleridir.
• Sırt çantası problemi: Sınırlı kapasiteli bir sırt çantasını farklı değer ve ağırlıktaki nesnelerle optimal biçimde doldurma problemi. DP, nesneleri sırayla ele alarak ve her adımda kalan kapasitenin tüm olası değerleri için maksimum değeri hesaplayarak bu problemi çözmeye olanak tanır.
• Kaynak dağıtımı problemi: Toplam etkiyi en üst düzeye çıkarmak amacıyla sınırlı bir kaynağın (örneğin yatırımların) birden fazla proje arasında dağıtılması.

Kısıtlamalar

Yöntemin başlıca kısıtlaması, boyutsallık laneti (İng. curse of dimensionality) — Bellman tarafından, sistemi tanımlayan değişken sayısı arttıkça durum sayısının ve dolayısıyla hesaplama karmaşıklığının üstel büyümesini ifade etmek için ortaya atılan bir terimdir. Bu durum, kesin DP'nin çok büyük boyutlu problemlere pratik uygulamasını kısıtlamaktadır.

İlgili Kavramlar

• Yöneylem araştırması
• Optimal kontrol teorisi
• Markov karar süreci (stokastik genelleme)
• Hamilton — Jacobi — Bellman denklemi (sürekli zaman için analog)

Notlar

</references>