Dinamik Programlama
Dinamik programlama, optimal alt yapıya ve örtüşen alt problemlere sahip sorunları, her alt problemi bir kez çözerek ve sonucunu yeniden kullanım için saklayarak çözen, üstel yeniden hesaplamayı polinom zamanlı hesaplamaya dönüştüren bir algoritma tasarım paradigmasıdır.
Tanım
Dinamik programlama, bir optimizasyon veya sayma problemini, değerini örtüşen alt problemler cinsinden özyinelemeli olarak tanımlayarak ve her farklı alt problemi tam olarak bir kez hesaplayıp sonucunu yeniden hesaplamak yerine yeniden kullanılabilmesi için önbelleğe alarak çözen bir yöntemdir.
Kapsam
Bu konu, dinamik programlamayı uygulanabilir kılan iki temel özelliği — optimal alt yapı ve örtüşen alt problemler — ve iki uygulama stilini, yukarıdan aşağıya memoizasyon ve aşağıdan yukarıya tablolamayı kapsamaktadır. En uzun ortak alt dizi, düzenleme mesafesi, sırt çantası problemi, matris zinciri çarpımı ve en kısa yol dinamik programları gibi kanonik problemlerin yanı sıra durum uzayı tasarımı ve zaman ile uzay takaslarının analizi de bu kapsamdadır. Aynı temel prensibi paylaşsalar da, graf algoritmaları altında ele alınan grafa özgü en kısa yol yöntemleri bu kapsamın dışındadır.
Temel sorular
- Problem, optimal alt çözümlerden optimal bir çözüm oluşturulmasına izin veren optimal alt yapıya sahip midir?
- Alt problemler kümesi (durum uzayı), her birinin yalnızca polinom sayıda kez özyinelemesi için nasıl tanımlanır?
- Çözüm, memoizasyon ile yukarıdan aşağıya mı yoksa tablolama ile aşağıdan yukarıya mı uygulanmalıdır?
- Tablo, yalnızca değeri değil, gerçek optimal çözümü elde etmek için nasıl yeniden yapılandırılabilir?
- Her adımda tablonun yalnızca bir kısmı gerektiğinde alan nasıl azaltılabilir?
Anahtar kavramlar
- optimal alt yapı
- örtüşen alt problemler
- optimalite prensibi
- memoizasyon
- tablolama
- durum uzayı ve özyineleme
- en uzun ortak alt dizi
- düzenleme mesafesi
- sırt çantası problemi
Temel kuramlar
- Optimalite Prensibi
- Bellman'ın optimalite prensibi, optimal bir politikanın, başlangıç durumu ve karar ne olursa olsun, kalan kararların ortaya çıkan durum için optimal bir politika oluşturması gerektiğini belirtmektedir — bu, dinamik programlama özyinelemelerinin resmi temelidir.
- Memoizasyon ve Tablolama
- Bir dinamik program, özyinelemeli bir formülasyona önbellek ekleyerek yukarıdan aşağıya (memoizasyon) veya bağımlılık sırasına göre bir tabloyu doldurarak aşağıdan yukarıya (tablolama) gerçekleştirilebilir; her ikisi de her alt problemi bir kez hesaplar ancak değerlendirme sırası ve uzay davranışı açısından farklılık gösterirler.
Klinik önem
Dinamik programlama, uygulamada yaygın olarak kullanılmaktadır: hesaplamalı biyolojide dizi hizalama (Needleman-Wunsch, Smith-Waterman), yazım denetiminde ve sürüm kontrolü farklarında düzenleme mesafesi, konuşma tanıma ve iletişimde Viterbi algoritması, yöneylem araştırması, finans ve pekiştirmeli öğrenmedeki dinamik programlar bunlara örnek olarak verilebilir.
Tarihçe
Richard Bellman, dinamik programlamayı 1950'lerde RAND Corporation'da geliştirmiştir ve ismi kısmen araştırma sponsorlarına cazip gelmesi için seçmiştir. Optimalite prensibi ve Bellman denklemi, yöneylem araştırması, kontrol teorisi ve bilgisayar bilimi genelinde temel bir rol oynamış ve bu teknik daha sonra algoritma ders kitaplarında temel bir algoritmik paradigma olarak kodlanmıştır.
Öne çıkan isimler
- Richard Bellman
- Thomas H. Cormen
- Jon Kleinberg
- Éva Tardos
İlgili konular
Temel eserler
- bellman1957
- cormen2009
Sıkça sorulan sorular
- Böl ve yönet ile dinamik programlama arasındaki fark nedir?
- Her ikisi de bir problemi alt problemlere ayırır, ancak böl ve yönet alt problemleri bağımsızdır ve bir kez çözülürken, dinamik programlama alt problemleri örtüşür ve saf özyineleme ile birçok kez yeniden hesaplanırdı. Dinamik programlama, bu yeniden hesaplamayı önlemek için alt problem çözümlerini önbelleğe almaktadır.
- Dinamik programlama ne zaman uygulanamaz?
- Optimal alt yapıya ve polinom boyutlu farklı alt problemler kümesine ihtiyaç duyar. Eğer problem optimal alt yapıdan yoksunsa veya doğal durum uzayı üstel ise ve sıkıştırılamıyorsa, dinamik programlama ya yanlış olur ya da artık verimli değildir.