Dp 1.4 – Gezginler

DP 1.4: Dinamik Programlama Tekniği

Giriş

Dinamik programlama (DP), karmaşık sorunları daha küçük, üst üste binen alt sorunlara bölerek ve bu alt sorunları çözümlerini saklayarak çözen güçlü bir algoritma tekniğidir. Bu teknik, alt sorunların birden fazla kez çözülmesini önleyerek hesaplama maliyetini önemli ölçüde azaltır.

DP 1.4’ün Özellikleri

Alt Sorunların Üst Üste Binmesi: DP, alt sorunların birden fazla kez çözülmesini önler.
Alt Sorunların Optimal Çözümlerinin Saklanması: DP, alt sorunların optimal çözümlerini bir tablo veya dizide saklar.
Alt Sorunların Çözülme Sırası: DP, alt sorunları belirli bir sırayla çözer, böylece daha büyük alt sorunlar daha önce çözülmüş alt sorunların çözümlerini kullanabilir.

DP 1.4’ün Uygulamaları

DP 1.4, çeşitli bilgisayar bilimi alanlarında yaygın olarak kullanılmaktadır, bunlar arasında şunlar yer alır:

En Uzun Ortak Alt Dizi: İki dizenin en uzun ortak alt dizisini bulmak.
En Uzun Artan Alt Dizi: Bir dizideki en uzun artan alt diziyi bulmak.
Matris Çarpımı: Bir dizi matrisi en az sayıda işlemle çarpmak.
Knapsack Problemi: Belirli bir kapasiteye sahip bir sırt çantasına maksimum değere sahip öğeleri yerleştirmek.
Seyahat Satıcı Problemi: Bir dizi şehri ziyaret etmek için en kısa yolu bulmak.

DP 1.4’ün Adımları

DP 1.4’ü uygulamak için şu adımlar izlenir:

Alt Sorunları Tanımlayın: Sorunu daha küçük, üst üste binen alt sorunlara bölün.
Alt Sorunların Çözümlerini Saklayın: Alt sorunların optimal çözümlerini bir tablo veya dizide saklayın.
Alt Sorunları Çözün: Alt sorunları belirli bir sırayla çözün ve daha büyük alt sorunların çözümlerini daha önce çözülmüş alt sorunların çözümlerini kullanarak hesaplayın.
Sonucu Bulun: Son alt sorunun çözümünü, orijinal sorunun çözümü olarak döndürün.

Örnek: En Uzun Ortak Alt Dizi

En uzun ortak alt diziyi bulmak için DP 1.4’ü kullanma örneği:

“`
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]

for i in range(m+1):
    for j in range(n+1):
        if i == 0 or j == 0 :
            L[i][j] = 0
        elif X[i-1] == Y[j-1]:
            L[i][j] = L[i-1][j-1] + 1
        else:
            L[i][j] = max(L[i-1][j], L[i][j-1])

return L[m][n]

“`

Faydalı Kaynaklar