DAA - Dinamik Programlama

Optimizasyon problemlerinde Dinamik Programlama da kullanılmaktadır. Böl ve yönet yöntemi gibi, Dinamik Programlama da alt problemlerin çözümlerini birleştirerek problemleri çözer. Dahası, Dinamik Programlama algoritması her bir alt problemi sadece bir kez çözer ve ardından cevabını bir tabloya kaydederek, her seferinde cevabı yeniden hesaplama işinden kaçınır.

Bir problemin iki ana özelliği, verilen problemin Dinamik Programlama kullanılarak çözülebileceğini gösterir. Bu özellikleroverlapping sub-problems and optimal substructure.

Örtüşen Alt Problemler

Böl ve Yönet yaklaşımına benzer şekilde Dinamik Programlama, alt problemlere yönelik çözümleri de birleştirir. Çoğunlukla bir alt problemin çözümüne tekrar tekrar ihtiyaç duyulduğunda kullanılır. Hesaplanan çözümler bir tabloda saklanır, böylece bunların yeniden hesaplanması gerekmez. Bu nedenle, çakışan alt problemin olduğu yerlerde bu tekniğe ihtiyaç vardır.

Örneğin, İkili Arama, çakışan alt soruna sahip değildir. Oysa Fibonacci sayılarının özyinelemeli programının birçok çakışan alt problemi vardır.

Optimal Alt Yapı

Verilen problemin optimal çözümü, alt problemlerinin optimal çözümleri kullanılarak elde edilebiliyorsa, belirli bir problem Optimal Alt Yapı Özelliğine sahiptir.

Örneğin, En Kısa Yol problemi aşağıdaki optimal alt yapı özelliğine sahiptir -

Eğer bir düğüm x bir kaynak düğümden gelen en kısa yolda yatıyor u hedef düğüme v, sonra en kısa yol u -e v en kısa yolun birleşimidir u -e xve en kısa yol x -e v.

Floyd-Warshall ve Bellman-Ford gibi standart All Pair En Kısa Yol algoritmaları, Dinamik Programlamanın tipik örnekleridir.