July 31, 2013 - Tagged as: tr.
Bu yazı, inanılmaz yoğun olduğum bir dönemde, acele içerisinde, kulakta müzik ile, 1 saat içerisinde yazılmış bir dinamik programlama tutorialıdır. Belki bir fayda sağlar diye bloguma da koymak istedim. Aslında bir ders kapsamında yazıldı(anlatım kısmı daha önceden yapılmıştı, rapor yazamamıştım).
Yanlışlık görürseniz lütfen yorum kısmında belirtin.
Dinamik programlama, problemlerin bazı özellikleri sağlaması şartıyla, çözümlerin kompleksliğini düşürmeyi amaçlayan bir programlama yöntemidir.
Bir problemin şu iki şartı sağladığını düşünelim:
Bu durumda küçük problemlerin çözümlerini bir şekilde saklayarak problemlerin yeniden çözülmesi önlenmiş olur ve sonuçta daha verimli bir algoritma elde etmiş oluruz.
Basit ve klasik bir örnek ile başlayalım,
(her bir örnek birbirinden farklı çözüm ve düşünme tekniklerini içermekte)
Elimizde farklı değerlerde bozuk paralar var, N para üstünü en az miktarda bozuk para vererek tamamlamak istiyoruz. Elimizde 1 değerinde bozuk para var, dolayısıyla her miktarda para üstünü verebiliriz.
Öncelikle bu çözüm için aç gözlü bir algoritmanın neden çalışmayacağını gözlemleyelim(diğer türlü çözüm aç gözlü bir algoritma olurdu).
37 para üstü vermek istiyoruz ve elimizde 10, 9 ve 1 değerlerinde bozukluklar var. Aç gözlü bir algoritma bu miktarı şöyle tamamlayacaktır:
10 - 10 - 10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 -- toplamda 10 bozuk para.Fakat aslında daha iyi bir çözüm mevcut:
10 - 9 - 9 - 9 -- toplamda 4 para.Aç gözlü algoritmanın bu problem için çalışmadığını gözlemlemiş olduk. Dinamik programlamaya geçmeden önce ikinci adım olarak bu problemin optimal çözümünü(yani en az miktarda bozuk para ile çözecek çözüm) bulan özyineli bir algoritma yazalım.
N değerinde para üstü tamamlamaya çalışıyor olalım ve A, B, C, … diye isimlendirdiğimiz bozuk paralarımız olsun. Bu durumda optimal çözüm için ya A değerinde bir bozuk para verip, N - A para üstünü tamamlamaya çalışırız(özyineleme), veya B değerinde bir bozuk para verip, N - B para üstünü tamamlamaya çalışırız(özyineleme) … ta ki tüm paraları deneyene kadar. Bu çözümün C++ programı şeklinde ifade edilmiş hali şöyle:
int findMinCoin(const vector<unsigned> &coins, unsigned amount)
{
if (amount == 0)
return 0;
int result = -1;
for (unsigned coin : coins) {
if (amount >= coin) {
int r = findMinCoin(coins, amount - coin) + 1;
if (result == -1 || r < result)
result = r;
}
}
return result;
}Bu özyineli çözüm bize dinamik programlama yapabilmek için aradığımız iki şarttan birini sağladığımızı söylüyor.
findMinCoinin optimal çözümü bulduğunu varsayalım. amount - coin kısmı bize alt problemlerin çözümünü aradığımızı gösteriyor, ve bu çözümü yine findMinCoin aradığımızdan ve findMinCoin optimal çözümü bulduğundan, dinamik programlama yapabilmemiz için gereken ilk şartı sağlamış oluyoruz.
Diyelim ki varsayımımız yanlıştı ve findMinCoin optimal çözümü bulmuyordu. Bu durumda zaten çözümümüz yanlış oluyor, çünkü findMinCoini asıl problemimizin optimal çözümünü bulmak için çağırıyoruz.
Dinamik programlamanın ikinci şartı için problemin hangi alt problemin kaç kere çağırıldığını farketmemiz gerekiyor. Bunun için şöyle bir gözlem yapalım:
Para üstümüz 37 ve paralarımız 10, 9 ve 1 (ilk örnek). 37’den 25’e gitmenin çok yolu var, bunlardan bazıları:
10 - 1 - 1
9 - 1 - 1 - 1
1 - 1 - 1 - 1 …. - 1 (12 tane)Tüm bu durumlar için 25 para üstünü tamamlamayı çözen alt problemimiz paylaşılacak. findMinCoin(coins, 25) çağrısının en azından 3 kere yapıldığını göstermiş olduk. Daha pek çok alt problemin paylaşıldığı benzer bir şekilde kolayca gözlemlenebilir.
Bu durumda, neden findMinCoin(coins, 25) çağrısının cevabını bir yerde saklayıp, gerektiğinde yeniden çözmek yerine cevabı sakladığımız yerden okuyup vermiyoruz? Bu arada tüm özyineli çağrılar için coins parametresinin hep aynı olduğuna dikkat.
Bu dönüş değerlerinin bir yerde saklanıp, yeniden hesaplanmamasına memoization adı veriliyor ve dinamik programlama yapmanın en temel yöntemlerinden biri.
Öncelikle memoization’ın bize ne kazandıracağını farkedelim. İlk çözümümüzde her bir para üstü için problemimiz bozuk para sayısı kadar özyineli çağrı yapacak.
M para üstümüz olsun ve N tane bozuk paramız olsun. Bu durumda M için N tane özyineli çağrı yapılacak. Kabaca, elimizdeki en küçük paranın 1 olduğunu düşündüğümüzde, bu özyineli çağrılar M kere yapılacak. Her seviyede N özyineli çağrı bize O(M ^ N) kompleksliğinde bir algoritma verecektir.
Her bir alt problemi memozation yardımıyla bir kere çözdüğümüz durumda ise, tamamlamak istediğimiz para üstümüz M olduğundan ve M - 1 alt probleme sahip olduğumuzdan O(M*N) bir komplekslik elde edeceğiz.
Örnek implementasyon şöyle:
int findMinCoin(vector<int> table, const vector<unsigned> &coins, unsigned amount)
{
if (table[amount] != -1)
// problem daha onceden cozulmus, cevaba tablodan bak
return table[amount];
// problem henuz cozulmemis, coz
for (unsigned coin : coins) {
if (amount >= coin) {
int r = 1 + findMinCoin(table, coins, amount - coin);
if (table[amount] == -1 || r < table[amount])
table[amount] = r;
}
}
return table[amount];
}Bu noktada özyineli çağrı yapmadan yapılabilecek alternatif bir çözüm için şunu farketmek gerekir: 0 para üstü için cevap zaten belli. 1 para üstü için cevabımızı sadece 1 değerinde bozuk para verip, 0 alt problemi için tabloya bakarak çözebiliriz. Diyelim ki 10 için çözüyoruz, 1 para verip 9 için cevaba tablodan bakmak isteriz, veya 9 para verip 1 için tabloya bakmak isteriz, veya 10 para verip 0 için tabloya bakmak isteriz vs. Yani aslında tabloda bir M değerinden önceki tüm değerler için cevap belliyse, kolayca o değerler arasından gerekli değerlere bakarak tabloda M’i doldurabiliriz. Bu da bizi 0. elemandan başlayarak tüm tabloyu adımlayarak doldurmayı içeren şu çözüme götürür:
void fillMinCoin(const vector<unsigned> &coins, vector<int> &tbl, unsigned amount)
{
for (unsigned coin : coins)
if (amount >= coin &&
(tbl[amount - coin] + 1 < tbl[amount]
|| tbl[amount] == -1))
tbl[amount] = tbl[amount - coin] + 1;
}Daha sonra bu tablodan gerekli elemana bakarak cevabı öğrenmiş oluruz. Bu şekilde bir çözüm dinamik programlamanın doğasını bize daha iyi gösteriyor. Dinamik programlama temelde tablolamaya dayanıyor.
İki harf dizisi(string) düşünelim. En uzun artan altdizi, şu şekilde tanımlanmıştır:
A1 A2 A3 … AN
Her bir harf hem ilk dizide hem ikinci dizide bulunmakta, ve herhangi bir A N-1, A N için A N - 1 ilk dizide A N’den önce bulunmakta ve A N - 1 ikinci dizide A N’den önce bulunmaktadır.
Örnek:
String 1: cbeb
String 2: fdceb
Cevap: cebolacaktır. c harfi birinci dizide ilk eleman, ikinci dizide 3. eleman olarak bulunuyor, e ilk dizide 3., ikinci dizide 4. eleman, b harfi ilk dizide 4. eleman, ikinci dizide 5. eleman olarak bulunmakta.
Bir probleme dinamik programlamanın uygulanabileceğini görmek için önce başta anlatılan iki şart kontrol edilmelidir. Bunun için güzel bir yolun problemin özyineli bir çözümünü yapmak olduğunu daha önceden anlatmıştık. Şimdi bu sorunu özyineli bir şekilde nasıl çözebileceğimize bakalım. Girdilerimiz S1 ve S2 olsun:
Bu çözümün Haskell implementasyonu şu şekilde: (sadelik açısından bu kısım C++ ile yazılmadı, dinamik programlama hali C++ ile verilecek)
solve :: String -> String -> String
solve s1 s2
| null s1 || null s2 = ""
solve s1 s2 =
let (h1, t1) = splitAt (length s1 - 1) s1
(h2, t2) = splitAt (length s2 - 1) s2
in if t1 == t1
then solve h1 h2 ++ t1
else
let result1 = solve h1 s2
result2 = solve s1 h2
in if length result1 > length result2
then result1
else result2Çözümün kompleksliğini düşünelim: Birbirine eşit olmayan M ve N uzunluğunda iki string düşünelim, M ve N - 1 uzunluğunda, M - 1 ve N uzunluğunda ve M - 1, N - 1 uzunluğunda stringler için özyineli çağrılar yapılacak. Her birinden yine 3 farklı özyineli çağrı ve toplamda M + N seviyede her seviyede 3 çağrı yapılacağından O((M + N) ^ 3) kompleksliğinde bir algoritmamız olur.
Dinamik programlamanın mümkün olduğunu görmek için fonksiyonun iki string girdimizin ilk kaç harfi üzerinden çağırıldığını bir ağaç üzerinden takip etmek yeterli olacaktır.
Bu durumda stringlerin ilk kaç harfi için çözümü bulduğumuzu iki boyutlu bir tabloda tutabiliriz. Örneğin tablodaki (3, 5) elemanı bize ilk stringin ilk 3 elemanı, ikinci stringin ilk 5 elemanı için bulduğumuz çözümü verecektir.
Yazıyı kısa tutmak adına bu noktadan sonra direkt olarak adımlayarak tablo doldurma şeklinde düşünelim. Problemin M ve N harflik hali için (M - 1, N), (M - 1, N - 1) ve (M, N - 1) lik hallerini çözmemiz gerekecek. Tablo üzerinde düşündüğümüzde, eğer tabloyu satır satır doldurursak, her bir sonraki adımda gerekli önceki adımları zaten elde etmiş olduğumuz görülebilir.
Burada tabloda tutacağımız her bir değer iki şeyi göstermeli, 1) string uzunluğu cinsinden cevap 2) o adıma geldiğimizde eğer iki stringin de son harflerini cevaba katıyorsak, bu stringin hangi harf olduğu.
void solve(table &tbl,
const string &str1, const string &str2)
{
for (us i = 0; i < str1.size(); i++)
if (str2[0] == str1[i])
tbl(i, 0) = new pair<char, us>(' ', 1);
else
tbl(i, 0) = new pair<char, us>(' ', 0);
for (us i = 0; i < str2.size(); i++)
if (str1[0] == str2[i])
tbl(0, i) = new pair<char, us>(' ', 1);
else
tbl(0, i) = new pair<char, us>(' ', 0);
for (us i = 1; i < str1.size(); i++)
for (us j = 1; j < str2.size(); j++)
if (str1[i] == str2[j])
tbl(i, j) = new pair<char, us>(str1[i], tbl(i - 1, j - 1)->second + 1);
else {
us s1 = tbl(i - 1, j)->second;
us s2 = tbl(i, j - 1)->second;
if (s1 > s2)
tbl(i, j) = new pair<char, us>(' ', s1);
else
tbl(i, j) = new pair<char, us>(' ', s2);
}
}Bu çözümdeki iç içe iki for döngüsü tablonun tamamını bir turda ve her bir adım için 3 işlemde doldurduğumuzu gösteriyor ve çözümümüz dolayısıyla O(M*N).
Bu problemin alıştırması http://www.spoj.com/SPOJ/problems/TLCS/ adresinden yapılabilir.
Bu noktada iki farklı dinamik programlama tekniği görmüş olduk. Biri memoization, biri ise adımlayarak tablo doldurma. Aralarında birkaç temel farklılık var.
Memoization çözümünde tabloyu nasıl dolduracağımızı düşünmemize gerek kalmadı. Eğer tabloda cevap bulunmamışsa, o yerdeki cevabın bulunması için özyineli çağrı yapıldı. Bu şekilde çözüme “yukarıdan-aşağı (top-down)” diyoruz.
İkinci çözüm yöntemimiz adımlayarak tablo doldurmaydı. Bu çözümün güzel yanı özyineli çağrı yapılmaması, fakat dezavantajı tabloyu nasıl bir sırayla dolduracağımızı düşünüp bulmamızı gerektirmesi. Diğer türlü, tabloda bir sonraki konumu doldururken aradığımız bir cevaba ulaşamayabiliriz.
Komplekslik olarak aralarında bir fark yok. Şahsi görüşüm memoization çözümünün daha güzel olduğu yönünde. Sebebi de yukarıda bahsettiğim gibi, tablo doldurma sırasını düşünmemize gerek olmaması.
Sorunun tanımını orjinal kaynaktan okuyabilirsiniz: http://codeforces.com/problemset/problem/225/C
Her bir kolonu tamamen beyaza ve tamamen siyaha boyamanın masraflarını biliyor olalım.
N. kolonu beyaza boyamak istediğimizi düşünelim, en az A en fazla B genişliğinde kolonlar istiyor olalım. Bu durumda X = [A … B] aralığı için N - X. kolonun siyah, [N - X + 1 … N] aralığındaki kolonların beyaz olması bize bir cevap verir(renklerin tam tersi olma durumu 2. bir cevap).
Burada farkedilmesi gereken şen, N - X. kolonun siyah olması aslında bir alt problem, ve en doğal ifade edilme şeklide bir özyineli fonksiyon ile olur.
Peki alt problemler paylaşılıyor mu? Şöyle düşünelim, en az 5, en fazla 10 genişliğinde kolonlar istiyor olalım ve şu anda 15. kolonu boyuyor olalım. Bu durumda 10, 9, 8, 7, … 6. kolona kadar olan kısımlar için aynı problemi yeniden çözeceğiz. 16. kolon için ise 19, 9, … 7. kolona kadar olan kısımları bir yeniden çözmemiz gerekecek. Ciddi miktarda alt problem paylaşılıyor.
Herhangi bir kolon için sadece o kolondan önceki kolonların cevabına ihtiyaç duyuyor olmamız tek boyutlu bir tabloda dinamik programlama yapabileceğimizi gösteriyor. Bu durumda şöyle bir cevap elde ediyoruz:
typedef unsigned us;
...
void solveDP(vector<int> &tblWhites, vector<int> &tblBlacks,
const vector<us> &colWhites, const vector<us> &colBlacks,
us idx, const us min, const us max)
{
if (idx < max) {
tblWhites[idx] = sumInclusive(colBlacks, 0, idx);
tblBlacks[idx] = sumInclusive(colWhites, 0, idx);
}
const us startIdx = idx < max ? 0 : idx - max;
const us endIdx = idx - min;
for (us i = startIdx; i <= endIdx; i++) {
if (tblBlacks[i] != -1) {
us cost = tblBlacks[i] + sumInclusive(colBlacks, i + 1, idx);
if (tblWhites[idx] == -1 || cost < static_cast<us>(tblWhites[idx]))
tblWhites[idx] = cost;
}
if (tblWhites[i] != -1) {
us cost = tblWhites[i] + sumInclusive(colWhites, i + 1, idx);
if (tblBlacks[idx] == -1 || cost < static_cast<us>(tblBlacks[idx]))
tblBlacks[idx] = cost;
}
}
}Bu soru önceki sorudan daha ilginç olmamakla beraber, memoization/tablolama yapma şekli biraz değişik olduğundan anlatmak istedim: http://codeforces.com/problemset/problem/82/D .
Sıradaki son 3 elemandan 2 elemanın sürekli azalacağını biliyoruz, ve alt problem bu iki eleman hariç elemanlar için çözülecek. Fakat bu 3 elemandan seçilmeyen elemanı memoization işleminde nasıl kullanabiliriz? Sıradan ayrılan iki insan alt problemin sıradaki ilk 2 eleman hariç olan kısmı olduğunu gösteriyor. 3 kişiden seçilmeyen bir kişi de algoritmaya ekstra bir parametre olarak verildiğinde karşımıza şöyle bir sonuç çıkıyor:
int solve(int lastElem, int offset, const vector<int> &ppl,
matrix<int> &tbl, matrix<int> &steps)
{
if (lastElem >= static_cast<int>(ppl.size()))
return 0;
if (offset >= static_cast<int>(ppl.size()))
return ppl[lastElem];
if (tbl(lastElem, offset) != -1)
return tbl(lastElem, offset);
int tmp[3];
tmp[0] = max(ppl[lastElem], ppl[offset]) + solve(offset + 1, offset + 2, ppl, tbl, steps);
tmp[1] = max(ppl[lastElem], ppl[offset + 1]) + solve(offset, offset + 2, ppl, tbl, steps);
tmp[2] = max(ppl[offset], ppl[offset + 1]) + solve(lastElem, offset + 2, ppl, tbl, steps);
int idmin = min_element(tmp, tmp + 3) - tmp;
steps(lastElem, offset) = idmin;
return tbl(lastElem, offset) = tmp[idmin];
}Alt problemlerin nasıl paylaşıldığı daha önceden anlatıldığı gibi görülebilir.