Backtracking and dynamic programming

Hazırlık: Tam k kenarlı en kısa yol

In a directed graph with positive weights, find the shortest path from v to w that uses exactly k edges (repeating vertices is allowed). Let d[x, i] be the shortest walk from v to x using exactly i edges. Then d[v, 0] = 0, every other d[x, 0] = ∞, and d[x, i] = the minimum over edges (y, x) of d[y, i − 1] + w(y, x). Fill the table for i = 1, …, k in O(km) and read off d[w, k]. This is dynamic programming, the subject of the next three lectures.

Pozitif ağırlıklı yönlü bir çizgede, v’den w’ye tam k kenar kullanan en kısa yolu bulun (tepelerin tekrarlanmasına izin verilir). d[x, i], v’den x’e tam i kenar kullanan en kısa yürüyüş olsun. O hâlde d[v, 0] = 0, diğer bütün d[x, 0] = ∞ ve d[x, i], (y, x) kenarları üzerinden d[y, i − 1] + w(y, x) değerlerinin minimumudur. Tabloyu i = 1, …, k için O(km) sürede doldurun ve d[w, k] değerini okuyun. Bu, sonraki üç dersin konusu olan dinamik programlamadır.

Sudoku: Tüm olasılıkları taramayı katlanılabilir kılma

Solving a Sudoku means searching through possible ways of filling the empty cells. Blind trial of every digit in every cell is hopeless, but the constraints (each digit once per row, column and box) rule out most possibilities for most cells, and that pruning is what makes the puzzle solvable by hand. Backtracking is the technique for writing such searches correctly and efficiently.

Sudoku çözmek, boş hücreleri doldurmanın olası yollarını araştırmaktır. Her hücrede her rakamı körlemesine denemek umutsuzdur; fakat kısıtlar (her rakamın her satır, sütun ve kutuda bir kez bulunması), çoğu hücrede olasılıkların çoğunu eler. Bulmacayı elle çözülebilir kılan, bu budamadır. Geri izleme, bu tür aramaları doğru ve verimli yazma tekniğidir.

Temel fikir

Model a solution as a vector a = (a₁, a₂, …, aₙ), where each aᵢ is chosen from a finite ordered set Sᵢ of candidates. The vector might be a permutation (aᵢ = which item sits in position i) or a subset (aᵢ = true if item i is included).

Çözümü, her aᵢ’nin sonlu ve sıralı bir adaylar kümesi Sᵢ’den seçildiği a = (a₁, a₂, …, aₙ) vektörüyle modelleyin. Vektör bir permütasyon (aᵢ = i konumunda bulunan eleman) veya bir alt küme (i elemanı dâhilse aᵢ = true) olabilir.

At each step we hold a partial solution (a₁, …, aₖ) and try to extend it by one more element. After extending, we check: is this now a complete solution? If not, the critical question is whether the current partial solution could still be extended into a solution.

Her adımda (a₁, …, aₖ) kısmi çözümünü tutar ve bir eleman daha ekleyerek genişletmeye çalışırız. Genişlettikten sonra denetleriz: Bu artık tam bir çözüm mü? Değilse kritik soru, mevcut kısmi çözümün hâlâ bir çözüme genişletilip genişletilemeyeceğidir.

If it could, recurse and keep going.

Genişletilebiliyorsa özyinelemeli çağrı yapıp devam edin.

If it could not, delete the last element and try the next candidate for that position, if any is left. (That is the “backtrack”.)

Genişletilemiyorsa son elemanı silin ve o konum için başka aday kaldıysa sıradaki adayı deneyin. (“Geri izleme” budur.)

Backtracking is nothing more than depth-first search (Lecture 12) on an implicit graph whose vertices are partial solutions and whose edges are single extensions.

Geri izleme, tepeleri kısmi çözümler, kenarları ise tek adımlı genişletmeler olan örtük bir çizge üzerinde derinlik öncelikli aramadan (Ders 12) başka bir şey değildir.

Genel yordam

backtrack(a, k, input):
    if is_a_solution(a, k, input):
        process_solution(a, k, input)
    else:
        k = k + 1
        c = construct_candidates(a, k, input)      (all legal values for position k)
        for each candidate c[i]:
            a[k] = c[i]
            make_move(a, k, input)
            backtrack(a, k, input)
            unmake_move(a, k, input)
            if finished: return                     (optional early stop)

backtrack(a, k, input):
    if is_a_solution(a, k, input):
        process_solution(a, k, input)
    else:
        k = k + 1
        c = construct_candidates(a, k, input)
            (k konumu için bütün geçerli değerler)
        for her c[i] adayı:
            a[k] = c[i]
            make_move(a, k, input)
            backtrack(a, k, input)
            unmake_move(a, k, input)
            if finished: return    (isteğe bağlı erken durdurma)

The routine is generic; each problem supplies three pieces:

Yordam geneldir; her problem üç parçayı sağlar:

is_a_solution(a, k, input): are the first k elements a complete solution?

is_a_solution(a, k, input): İlk k eleman tam bir çözüm mü?

construct_candidates(a, k, input): given positions 1 to k − 1, list every legal value for position k. This is where all the cleverness (pruning) lives.

construct_candidates(a, k, input): 1’den k − 1’e kadar olan konumlar verilmişken, k konumu için bütün geçerli değerleri listele. Bütün akıllı seçimler (budama) burada yer alır.

process_solution(a, k, input): print, count or otherwise use a finished solution.

process_solution(a, k, input): Tamamlanmış çözümü yazdır, say veya başka şekilde kullan.

Because each recursive call gets its own fresh candidate array, the not-yet-tried candidates at different depths never interfere with one another. The search visits each partial configuration once, and the input argument carries any problem data the three routines need.

Her özyinelemeli çağrı kendisine ait yeni bir aday dizisi aldığı için, farklı derinliklerde henüz denenmemiş adaylar birbirine karışmaz. Arama her kısmi yapılandırmayı bir kez ziyaret eder; input argümanı ise üç yordamın ihtiyaç duyduğu problem verilerini taşır.

Bütün alt kümeleri üretme

There are 2ⁿ subsets of n items. Represent a subset by a vector of n true/false values, with aᵢ = true meaning item i is in. Then Sₖ = {true, false} for every position, and a is a solution when k = n:

n elemanın 2ⁿ alt kümesi vardır. Alt kümeyi, aᵢ = true değerinin i elemanının dâhil olduğunu belirttiği n doğru/yanlış değerinden oluşan bir vektörle gösterin. O zaman her konum için Sₖ = {true, false} olur ve k = n olduğunda a bir çözümdür:

is_a_solution(a, k, n):        return k == n
construct_candidates(...):     c = [true, false]
process_solution(a, k, ...):   print every i with a[i] == true
generate_subsets(n):           backtrack(a, 0, n)

is_a_solution(a, k, n):        return k == n
construct_candidates(...):     c = [true, false]
process_solution(a, k, ...):   a[i] == true olan her i’yi yazdır
generate_subsets(n):           backtrack(a, 0, n)

For {1, 2, 3} the search tree branches “1 in / 1 out” at the top, then “2 in / 2 out”, then “3 in / 3 out”, and the leaves come out in the order {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {}.

{1, 2, 3} için arama ağacı tepede “1 dâhil / 1 hariç”, sonra “2 dâhil / 2 hariç”, ardından “3 dâhil / 3 hariç” biçiminde dallanır. Yapraklar {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {} sırasıyla ortaya çıkar.

Bütün permütasyonları üretme

There are n! permutations. Represent one as a vector where aᵢ is the item in position i, and candidates for position k are all items not already used: Sₖ = {1, …, n} minus the items in a₁..aₖ₋₁. The candidate constructor marks used items in a boolean array and lists the rest; is_a_solution and process_solution are the same as for subsets. For n = 3 the leaves come out in the order 123, 132, 213, 231, 312, 321.

n! permütasyon vardır. Bir permütasyonu, aᵢ’nin i konumundaki eleman olduğu bir vektörle gösterin. k konumunun adayları henüz kullanılmamış bütün elemanlardır: Sₖ = {1, …, n} kümesinden a₁..aₖ₋₁ içindeki elemanların çıkarılması. Aday oluşturucu, kullanılan elemanları bir Boole dizisinde işaretler ve kalanları listeler; is_a_solution ve process_solution, alt kümelerdekilerle aynıdır. n = 3 için yapraklar 123, 132, 213, 231, 312, 321 sırasıyla oluşur.

Geri izleme yarışması

Skiena’s course sets a programming contest on one of two problems, judged purely on speed:

Skiena’nın dersinde, yalnızca hıza göre değerlendirilen bir programlama yarışması aşağıdaki iki problemden biri üzerine düzenlenir:

Bandwidth: arrange the n vertices of a graph in a line so that the longest edge (measured as distance along the line) is as short as possible. Used in circuit layout, linear algebra, and memory layout. It is NP-complete (Lecture 19), so no polynomial worst-case algorithm is expected; trying all n! permutations costs O(n! · m). The task is to prune as hard as possible.

Bant genişliği: Bir çizgenin n tepesini, en uzun kenar (sıra üzerindeki uzaklık olarak ölçülür) mümkün olduğunca kısa olacak şekilde bir sıraya yerleştirin. Devre yerleşimi, doğrusal cebir ve bellek yerleşiminde kullanılır. NP-tamdır (Ders 19); bu yüzden polinom zamanlı en kötü durum algoritması beklenmez. Bütün n! permütasyonu denemek O(n! · m) sürer. Görev, olabildiğince güçlü budama yapmaktır.

Set cover: given subsets S₁, …, Sₘ of {1, …, n}, pick the fewest subsets whose union is everything. (Buy all the items while buying as few pre-packaged lots as possible.) Trying all 2ᵐ subsets of the subsets costs O(2ᵐ · nm).

Küme örtüsü: {1, …, n} kümesinin S₁, …, Sₘ alt kümeleri verildiğinde, birleşimi tüm kümeyi veren en az sayıda alt kümeyi seçin. (Mümkün olduğunca az sayıda önceden paketlenmiş ürün grubu satın alarak bütün ürünleri edinmek.) Alt kümelerin bütün 2ᵐ alt kümesini denemek O(2ᵐ · nm) sürer.

His advice for producing fast programs applies to any search: do not optimise prematurely, since pruning the tree is where the money is, not recursion versus iteration; choose data structures for a reason (which operations matter?); keep it simple; and let the profiler show you where the time really goes, because it is probably not where you think.

Hızlı programlar üretmeye ilişkin önerileri her arama için geçerlidir: erken optimizasyon yapmayın; asıl kazanç, özyineleme ile döngü arasında seçimde değil, ağacın budanmasındadır. Veri yapılarını bir gerekçeyle seçin (hangi işlemler önemli?). Basit tutun. Zamanın gerçekte nereye gittiğini performans profilleyicisinin göstermesine izin verin; çünkü muhtemelen düşündüğünüz yere gitmiyordur.

A related exercise: a derangement is a permutation in which no item is in its own position (pᵢ ≠ i). Generate all derangements with pruning: simply never offer i as a candidate for position i, so no wasted branches are ever entered.

İlgili bir alıştırma: sabit noktasız permütasyon (derangement), hiçbir elemanın kendi konumunda bulunmadığı permütasyondur (pᵢ ≠ i). Bütün sabit noktasız permütasyonları budamayla üretin: i’yi i konumu için asla aday göstermeyin; böylece boşa gidecek dallara hiç girilmez.

Sekiz vezir problemi

Place eight queens on an 8 × 8 chessboard so that no two attack each other. The representation matters enormously. Since two queens cannot share a row, put one queen in each row and let aᵢ be the column of the queen in row i. Since two queens cannot share a column, the aᵢ form a permutation, so there are only 8! = 40,320 candidates instead of 64 choose 8.

8 × 8 satranç tahtasına, hiçbir ikisi birbirini tehdit etmeyecek biçimde sekiz vezir yerleştirin. Gösterim seçimi son derece önemlidir. İki vezir aynı satırda olamayacağı için her satıra bir vezir koyun ve aᵢ, i. satırdaki vezirin sütunu olsun. İki vezir aynı sütunda da olamayacağı için aᵢ değerleri bir permütasyon oluşturur; böylece 64’ün 8’li kombinasyonu yerine yalnızca 8! = 40,320 aday vardır.

The candidate constructor for row k tests each column i against every earlier queen j: a column threat if i = aⱼ, and a diagonal threat if |k − j| = |i − aⱼ|. Only unthreatened columns become candidates, so the search never enters a doomed branch.

k satırının aday oluşturucusu, her i sütununu daha önceki her j veziriyle sınar: i = aⱼ ise sütun tehdidi, |k − j| = |i − aⱼ| ise çapraz tehdidi vardır. Yalnızca tehdit altında olmayan sütunlar aday olur; böylece arama başarısızlığa mahkûm bir dala hiç girmez.

construct_candidates(a, k, n):
    for each column i from 1 to n:
        legal = true
        for each earlier row j < k:
            if |k − j| == |i − a[j]|: legal = false     (diagonal)
            if i == a[j]: legal = false                  (column)
        if legal: add i to the candidates

construct_candidates(a, k, n):
    for 1’den n’ye her i sütunu:
        legal = true
        for önceki her j < k satırı:
            if |k − j| == |i − a[j]|: legal = false   (çapraz)
            if i == a[j]: legal = false              (sütun)
        if legal: i’yi adaylara ekle

With process_solution just counting, this program finds all 365,596 solutions for n = 14 in minutes.

process_solution yalnızca sayma yaptığında bu program, n = 14 için bütün 365,596 çözümü dakikalar içinde bulur.

Satranç tahtasını örtme: Kombinatoryal patlamayla mücadele

Can the eight major chess pieces (king, queen, two rooks, two bishops, two knights) be placed so that every square on the board is attacked? Since 1849 nobody had found an arrangement, with the bishops on opposite colours, covering all 64 squares; the best known covered 63.

Sekiz ana satranç taşı (şah, vezir, iki kale, iki fil, iki at), tahtadaki her kare tehdit altında kalacak biçimde yerleştirilebilir mi? 1849’dan beri, filler zıt renklerde olacak şekilde 64 karenin tamamını örten bir düzen bulunamamıştı; bilinen en iyi düzen 63 kareyi örtüyordu.

Brute force is out of the question: choosing a square for each of eight pieces gives 64!/56! ≈ 1.8 × 10¹⁴ configurations, and anything much beyond 10⁸ is unreasonable on a modest computer. The attack proceeded in stages:

Kaba kuvvet söz konusu olamaz: sekiz taşın her biri için bir kare seçmek 64!/56! ≈ 1.8 × 10¹⁴ yapılandırma verir; mütevazı bir bilgisayarda 10⁸’in çok ötesi makul değildir. Çözüm arayışı aşamalar hâlinde ilerledi:

Exploit symmetry. Reflecting the board horizontally, vertically and diagonally means the queen need only be tried in 10 non-equivalent squares; a smarter scheme restricts the white bishop and the queen to 16 squares each, bringing the count down to about 2.3 × 10¹².

Simetriden yararlanın. Tahtayı yatay, düşey ve çapraz yansıtmak, vezirin yalnızca eşdeğer olmayan 10 karede denenmesini yeterli kılar. Daha akıllı bir düzen, beyaz karelerdeki fili ve veziri her biri için 16 kareyle sınırlar; sayıyı yaklaşık 2.3 × 10¹²’ye indirir.

Prune on impossibility. Each piece can attack at most a fixed number of squares (queen 27, rook 14, king 8, and so on). Whenever the number of still-unattacked squares exceeds the most the remaining pieces could possibly cover, abandon the branch. Ordering the pieces by decreasing mobility, this pruned 95% of the search space, and with precomputed move lists the program examined 1,000 positions per second.

İmkânsızlığa göre budayın. Her taş en fazla sabit sayıda kareyi tehdit edebilir (vezir 27, kale 14, şah 8 vb.). Henüz tehdit edilmeyen karelerin sayısı, kalan taşların örtebileceği en büyük sayıyı aştığında dalı bırakın. Taşları azalan hareketlilik sırasına koymak, arama uzayının %95’ini budadı; önceden hesaplanmış hamle listeleriyle program saniyede 1,000 konumu inceledi.

Still too slow: 10¹² / 10³ = 10⁹ seconds, over 1,000 days. Further constant-factor speedups would not be enough; more pruning was needed.

Hâlâ çok yavaş: 10¹² / 10³ = 10⁹ saniye, yani 1,000 günden fazla. Sabit çarpan düzeyindeki ek hızlandırmalar yetmeyecekti; daha fazla budama gerekiyordu.

A cleverer algorithm eventually proved, in under a day of computing, that no covering exists.

Daha akıllı bir algoritma sonunda, bir günden kısa hesaplamayla böyle bir örtmenin bulunmadığını kanıtladı.

The moral: with clever backtracking and pruning, surprisingly large problems yield to exhaustive search, but you have to keep finding ways to not look at most of the space.

Çıkarılacak ders: Akıllıca geri izleme ve budamayla, şaşırtıcı derecede büyük problemler tüm olasılıkları taramaya boyun eğer; ancak uzayın büyük bölümüne hiç bakmamanın yollarını bulmaya devam etmelisiniz.

Hazırlık: Çoklu kümenin permütasyonları

A multiset can repeat elements, so {1, 1, 2, 2} has only six distinct permutations rather than 4! = 24. To generate them with backtracking (Lecture 15), keep a count of how many copies of each distinct value remain; the candidates for position k are the distinct values with a positive remaining count. Each value is offered once per position regardless of how many copies exist, so no permutation is produced twice.

Çoklu kümede elemanlar tekrarlanabilir; bu yüzden {1, 1, 2, 2} kümesinin 4! = 24 yerine yalnızca altı farklı permütasyonu vardır. Bunları geri izlemeyle (Ders 15) üretmek için her farklı değerden kaç kopya kaldığını tutun. k konumunun adayları, kalan sayısı pozitif olan farklı değerlerdir. Kaç kopyası olursa olsun her değer her konumda bir kez önerilir; dolayısıyla hiçbir permütasyon iki kez üretilmez.

Neden dinamik programlama?

DP is a powerful, general tool for optimisation problems on left-to-right ordered items such as strings and sequences. Floyd’s all-pairs shortest-path algorithm (Lecture 14) was already an example. It looks like magic until you have seen enough examples; then it is comparatively easy to apply.

DP, dizeler ve sayı dizileri gibi soldan sağa sıralanmış nesneler üzerindeki optimizasyon problemleri için güçlü ve genel bir araçtır. Floyd’un bütün çiftler arasında en kısa yol algoritması (Ders 14) zaten bir örnekti. Yeterince örnek görene kadar sihir gibi görünür; ardından uygulamak görece kolaylaşır.

Compare the two strategies seen so far:

Şimdiye kadar gördüğümüz iki stratejiyi karşılaştırın:

Greedy algorithms make the best local choice at each step. Without a correctness proof they are very likely to be wrong (Lecture 1).

Açgözlü algoritmalar her adımda en iyi yerel seçimi yapar. Doğruluk kanıtı olmadan yanlış olma olasılıkları çok yüksektir (Ders 1).

Exhaustive search (backtracking) is always correct but usually exponential.

Tüm olasılıkları tarama (geri izleme) her zaman doğrudur, fakat genellikle üstel maliyetlidir.

DP gives a way to design custom algorithms that systematically consider all possibilities (so they are correct) while storing results to avoid recomputation (so they are efficient).

DP, bütün olasılıkları sistematik biçimde değerlendiren (bu nedenle doğru olan) ve yeniden hesaplamayı önlemek için sonuçları saklayan (bu nedenle verimli olan) özel algoritmalar tasarlama yolu sunar.

Yineleme bağıntıları

A recurrence relation is an equation defined in terms of itself, together with base cases. Many natural functions are easiest to express this way:

Yineleme bağıntısı, başlangıç durumlarıyla birlikte, kendisi cinsinden tanımlanan bir denklemdir. Birçok doğal fonksiyon en kolay bu şekilde ifade edilir:

A computer can evaluate a recurrence directly, one case after another, even when no tidy closed form exists. That is the whole of DP: evaluate the recurrence, but carefully.

Düzenli bir kapalı biçim bulunmasa bile bilgisayar bir yineleme bağıntısını, durumları art arda ele alarak doğrudan hesaplayabilir. DP’nin tamamı budur: yineleme bağıntısını hesaplayın, ama dikkatle.

Fibonacci sayıları: Üç yöntem

Fₙ = Fₙ₋₁ + Fₙ₋₂ with F₀ = 0 and F₁ = 1, giving 0, 1, 1, 2, 3, 5, 8, 13, …

F₀ = 0 ve F₁ = 1 başlangıçlarıyla Fₙ = Fₙ₋₁ + Fₙ₋₂, 0, 1, 1, 2, 3, 5, 8, 13, … dizisini verir.

1. Plain recursion. Translate the definition directly:

1. Yalın özyineleme. Tanımı doğrudan koda aktarın:

fib_r(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib_r(n − 1) + fib_r(n − 2)

fib_r(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib_r(n − 1) + fib_r(n − 2)

Easy, and disastrously slow, because it recomputes the same values over and over. The call tree for F(6) computes F(4) twice, F(3) three times, F(2) five times. The ratio of consecutive Fibonacci numbers approaches the golden ratio φ ≈ 1.618, so Fₙ ≈ 1.6ⁿ, and since every leaf of the call tree is a 0 or a 1, computing Fₙ makes about 1.6ⁿ calls. Exponential.

Kolaydır ve felaket derecesinde yavaştır; çünkü aynı değerleri tekrar tekrar hesaplar. F(6) için çağrı ağacı F(4)’ü iki kez, F(3)’ü üç kez, F(2)’yi beş kez hesaplar. Ardışık Fibonacci sayılarının oranı altın oran φ ≈ 1.618’e yaklaşır; dolayısıyla Fₙ ≈ 1.6ⁿ’dir. Çağrı ağacının her yaprağı 0 veya 1 olduğundan, Fₙ’yi hesaplamak yaklaşık 1.6ⁿ çağrı yapar. Üstel.

2. Memoisation. Keep the recursion, but cache. Before computing F(n), look in a table; if it is there, return it; if not, compute it, store it, return it:

2. Bellekleme (memoisation). Özyinelemeyi koruyun, fakat önbellek kullanın. F(n)’yi hesaplamadan önce tabloya bakın; varsa döndürün; yoksa hesaplayın, saklayın ve döndürün:

fib_c(n):
    if f[n] is UNKNOWN:
        f[n] = fib_c(n − 1) + fib_c(n − 2)
    return f[n]

driver: f[0] = 0; f[1] = 1; f[2..n] = UNKNOWN; return fib_c(n)

fib_c(n):
    if f[n] is UNKNOWN:
        f[n] = fib_c(n − 1) + fib_c(n − 2)
    return f[n]

sürücü: f[0] = 0; f[1] = 1; f[2..n] = UNKNOWN; return fib_c(n)

Each value is now computed exactly once, so the whole thing is O(n). (A 64-bit integer holds F(92); beyond that the numbers overflow.)

Artık her değer tam bir kez hesaplanır; dolayısıyla işlemin tamamı O(n)’dir. (64 bitlik bir tam sayı F(92)’yi tutar; sonrasında sayılar taşar.)

3. Dynamic programming. Drop the recursion altogether and fill the table from the bottom up, small values first, so that when a value is needed it has already been computed:

3. Dinamik programlama. Özyinelemeyi tamamen kaldırın ve tabloyu aşağıdan yukarıya, küçük değerler önce gelecek biçimde doldurun. Böylece bir değer gerektiğinde zaten hesaplanmış olur:

fib_dp(n):
    f[0] = 0; f[1] = 1
    for i from 2 to n:
        f[i] = f[i − 1] + f[i − 2]
    return f[n]

fib_dp(n):
    f[0] = 0; f[1] = 1
    for i from 2 to n:
        f[i] = f[i − 1] + f[i − 2]
    return f[n]

Linear time, and no recursion overhead. The moral: we traded space for time. A table of n numbers turned an exponential algorithm into a linear one. (Since only the last two values are ever needed, even the table can shrink to two variables, but the idea is the same.)

Doğrusal zaman; üstelik özyineleme ek yükü yoktur. Çıkarılacak ders: bellek alanını zamanla takas ettik. n sayılık tablo, üstel algoritmayı doğrusal algoritmaya çevirdi. (Yalnızca son iki değer gerektiğinden tablo iki değişkene kadar küçültülebilir; fikir aynıdır.)

DP alışkanlığı

The trick is always the same: notice that the naive recursive algorithm keeps solving the same subproblems, and store their answers in a table instead of recomputing them. The working method is: first find a correct recursive algorithm, then speed it up with a results table.

Püf noktası her zaman aynıdır: naif özyinelemeli algoritmanın aynı alt problemleri tekrar tekrar çözdüğünü fark edin; yeniden hesaplamak yerine yanıtlarını bir tabloda saklayın. Çalışma yöntemi şudur: önce doğru bir özyinelemeli algoritma bulun, sonra sonuçlar tablosuyla hızlandırın.

Skiena’s own reasons for loving DP, all from his practice: morphing shapes in computer graphics, compressing data for high-density bar codes, and designing genes that avoid or contain given patterns. Once you understand DP, reinventing the algorithm you need is often easier than finding it in a book.

Skiena’nın DP’yi sevmesinin, kendi uygulamalarından gelen nedenleri şunlardır: bilgisayar grafiklerinde şekilleri birbirine dönüştürmek, yüksek yoğunluklu barkodlar için veri sıkıştırmak ve verilen örüntüleri içeren veya onlardan kaçınan genler tasarlamak. DP’yi anladığınızda ihtiyaç duyduğunuz algoritmayı yeniden tasarlamak, çoğu zaman onu kitapta bulmaktan kolaydır.

Binom katsayıları: İki boyutlu tablo

The binomial coefficient “n choose k”, written C(n, k), counts the ways to choose k things from n. Two of its faces:

C(n, k) ile gösterilen ve “n’nin k’lı kombinasyonu” diye okunan binom katsayısı, n nesneden k tanesini seçmenin yollarını sayar. İki yorumu:

Committees: the number of k-person committees from n people is C(n, k) by definition.

Komiteler: n kişiden k kişilik komite oluşturmanın sayısı, tanım gereği C(n, k)’dir.

Grid paths: the number of ways to walk from the top-left to the bottom-right corner of an n × m grid, moving only down or right, is C(n + m, n): every path has n + m steps, and choosing which n of them go down determines the path.

Izgara yolları: n × m bir ızgaranın sol üst köşesinden sağ alt köşesine yalnızca aşağıya veya sağa giderek yürümenin sayısı C(n + m, n)’dir. Her yol n + m adım içerir; bunların hangi n tanesinin aşağıya gideceğini seçmek yolu belirler.

The formula C(n, k) = n! / ((n − k)! k!) is correct but dangerous in a computer: the factorials overflow long before the final answer does.

C(n, k) = n! / ((n − k)! k!) formülü doğrudur, fakat bilgisayarda tehlikelidir: faktöriyeller, son yanıt taşmadan çok önce taşar.

Pascal’s triangle is the safe route. Each number is the sum of the two directly above it, which is the recurrence

Pascal üçgeni güvenli yoldur. Her sayı hemen üstündeki iki sayının toplamıdır; bu da şu yineleme bağıntısıdır:

Why it is true: look at the nth item. Either it is in the chosen subset (then choose the other k − 1 from the remaining n − 1) or it is not (then choose all k from the remaining n − 1).

Doğru olmasının nedeni: n. elemana bakın. Ya seçilen alt kümededir (kalan n − 1 elemandan diğer k − 1’i seçin) ya da değildir (kalan n − 1 elemandan k tanesinin tamamını seçin).

Base cases, without which no recurrence is complete: C(n, 0) = 1 (one way to choose nothing: the empty set) and C(k, k) = 1 (one way to choose everything).

Hiçbir yineleme bağıntısının onlarsız tamamlanamayacağı başlangıç durumları: C(n, 0) = 1 (hiçbir şey seçmemenin tek yolu: boş küme) ve C(k, k) = 1 (her şeyi seçmenin tek yolu).

binomial_coefficient(n, k):
    for i from 0 to n: bc[i][0] = 1
    for j from 0 to n: bc[j][j] = 1
    for i from 2 to n:
        for j from 1 to i − 1:
            bc[i][j] = bc[i − 1][j − 1] + bc[i − 1][j]
    return bc[n][k]

binomial_coefficient(n, k):
    for i from 0 to n: bc[i][0] = 1
    for j from 0 to n: bc[j][j] = 1
    for i from 2 to n:
        for j from 1 to i − 1:
            bc[i][j] = bc[i − 1][j − 1] + bc[i − 1][j]
    return bc[n][k]

The table is filled row by row, so each entry’s two “parents” are already there when needed. Cost O(n²), all additions, no overflow until the answer itself is too big.

Tablo satır satır doldurulur; böylece her hücrenin iki “ebeveyni” ihtiyaç duyulduğunda zaten hazırdır. Maliyet O(n²)’dir; bütün işlemler toplamadır ve yanıtın kendisi fazla büyük olana kadar taşma olmaz.

This is the pattern for every DP problem to come: (1) a recurrence with base cases, (2) a table indexed by the recurrence’s parameters, (3) an order of filling that computes small cases before the large ones that depend on them.

Bundan sonraki her DP probleminin kalıbı budur: (1) başlangıç durumları olan bir yineleme bağıntısı, (2) bağıntının parametreleriyle indislenen bir tablo, (3) küçük durumları onlara bağlı büyük durumlardan önce hesaplayan bir doldurma sırası.