Sözlük · approach
Dynamic Programming
Çok-aşamalı karar problemlerini örtüşen alt-problemlere özyinelemeli olarak ayırarak ve ara sonuçları saklayarak çözen OR / bilgisayar bilimleri tekniği; Bellman (1957) tarafından geliştirilmiştir.
Dinamik ProgramlamaDPBellman DPDynamic Programming
Dynamic Programming (Dinamik Programlama, DP), Richard Bellman'ın 1957 kitabında (*Dynamic Programming*, Princeton University Press) tanıttığı çok-aşamalı karar problemleri çözüm tekniğidir; problemi örtüşen alt-problemlere ayırır, ara sonuçları bir tabloda saklar (memoization veya tabulation) ve özyinelemeli olarak Bellman denklemi V(s) = max_a {r(s, a) + γ V(s')} aracılığıyla çözer. Knapsack problemi DP'nin kanonik örneğidir — Bellman'ın 1957 kitabında knapsack üzerinden DP çerçevesini sunar; O(N×W) zaman karmaşıklığı **pseudo-polinom** (W'nın değerine polinom, bit sayısına üstel). Diğer kanonik uygulamalar: en kısa yol (Bellman-Ford algoritması), envanter (Wagner-Whitin lot-sizing), ekipman değiştirme (Bellman 1955), stokastik karar süreçleri (Markov Decision Process), bilgisayar biliminde dizi hizalama (Needleman-Wunsch), parantez ayrıştırma (CYK), parçaları matris çarpımı sıralama. DP iki ana sınıfta uygulanır: **deterministik DP** (her aşamada belirli sonuç) ve **stokastik DP** (her aşamada olasılıksal sonuç — Markov karar süreçleri). DP'nin çalışma şartı: optimal substructure (alt-problemlerin optimumları birleşerek tam optimum verir) ve overlapping subproblems (alt-problemler tekrar eder). Approximate Dynamic Programming (ADP) ve Stochastic Dual Dynamic Programming (SDDP) modern büyük ölçekli stokastik problemleri çözer. Bellman 1957 + Bellman ve Dreyfus 1962 + Bertsekas 1995 kanonik kaynaklar.
Örnek
Bir orta-ölçekli holding yatırım komitesi 80 aday proje arasından yıllık 100M TRY bütçeye sığacak optimum NPV alt-kümesini DP ile çözer: N = 80, W = 100.000 (binlik TRY birim), DP tablosu 80 × 100.000 = 8M hücre, modern hesaplayıcıda saniyeler; sezgisel sıralamaya kıyasla %7 daha yüksek toplam NPV.