Geri İzleme

Dinamik programlama alt problem uzayını tümüyle dolaşıp saklıyordu ve bunu yapabiliyordu, çünkü uzay tabloya sığıyordu. Bazı problemlerde uzay tabloya sığmaz: sekiz vezirlik bir tahtada 16.777.216 yerleşim vardır ve bunların yalnız 92’si çözümdür. Böyle bir uzayda tek yol, büyük bölümünün çözüm içermediğini kanıtlayıp kesmektir.

Kalıbın adı geri izleme (backtracking): çözüm parça parça kurulur, kurulan parça bir kısıtı çiğnediği anda o dal bırakılır ve bir önceki karara dönülür. Kesme işlemine budama (pruning) denir. Budama, bu kursta görülen kısaltmalar arasında özel bir yerdedir — ilk dersteki eleme gibi doğruluğu korur, ama yalnız ölçütü doğruysa. Bu ders o “yalnız”ı sayar.

• TY38. Ölçülen problem: $n \times n$ tahtada birbirini tehdit etmeyen $n$ vezir yerleşimlerinin sayısı.
• TY39. Bir adım, arama ağacındaki bir düğümdür; yapraklar da düğüm sayılır.
• TY40. Kâhin budamasız aramadır: bütün yerleşimleri üretir ve geçerliliği sonda sınar. Hiçbir dalı kesmediği için hiçbir çözümü kaçıramaz.
• TY41. Kalıbın ön koşulu: budama ölçütü yalnız kesin olarak çözümsüz dalları kesmelidir.
• TY42. Üç ölçüt ölçülür — doğru, aşırı (çözüm içeren dalı da keser), eksik (çözümsüz dalı kesmez).
• TY43. Dağarcık burada tahtadır: altı vezirlik tahtada üç kare yasak, 40 tahta.
• TY44. Ayrılan girdi, kâhin ile kalıbın çözüm sayısının farklı olduğu tahtadır.
• TY45. Sekiz vezirlik tahtada budamasız aramanın tarayacağı 16.777.216 yerleşim hesaplanır, koşturulmaz; ilk dersin adım bütçesi bunu gerektirir.
• TY46. Her ölçüm 20260219 tohumlu ikinci dağarcıkta da koşturulur.

Kısmi Çözüm Ağacı

Geri izleme, çözümü bir dizi karar olarak görür. Her karar bir düğüm üretir, her düğümün çocukları o karardan sonraki seçeneklerdir. Bu yapıya kısmi çözüm ağacı denir ve yaprakları tam çözüm adaylarıdır.

Budamasız arama bu ağacın tamamını gezer ve geçerlilik sınamasını yalnız yapraklarda yapar. Budamalı arama sınamayı her düğümde yapar: kısmi çözüm zaten bir kısıtı çiğniyorsa, o düğümün altındaki bütün yapraklar da çiğneyecektir ve dal kesilebilir. Kesmenin meşruluğu tam olarak bu çıkarıma dayanır — alt ağaçta çözüm olmadığı kanıtlanmış olmalıdır.

Kanıt zayıfladığında iki yönde hata yapılır. Ölçüt gereğinden fazla keserse çözüm içeren dallar da gider ve yanıt eksik çıkar. Gereğinden az keserse çözümsüz dallar gezilmeye devam eder; bu tek başına yanlış yanıt vermez, ama yaprakta yapılan sınama da zayıfsa geçersiz yerleşimler çözüm sayılır.

İki hata biçiminin çıktıdan ayırt edilme olanağı yoktur. Eksik yerleşim listesi de fazla yerleşim listesi de bir liste olarak dönmeyi sürdürür; hangisinin doğru olduğunu söyleyecek tek şey, dalları hiç kesmeyen kâhinin ürettiği sayıdır.

Budamanın Kestiği Uzay

# Ortak tanimin geri izleme olcumu: ayni arama, budamali ve budamasiz.
class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self, n=1):
        self.adim += n


def vezir(n, budama=True):
    """Budamasiz surum butun yerlesimleri dener; budamali surum catismada durur."""
    s = Sayac()
    cozum = []

    def gez(satir, yer):
        s.say()
        if satir == n:
            cozum.append(tuple(yer))
            return
        for sutun in range(n):
            if budama and any(sutun == y or abs(sutun - y) == satir - i
                              for i, y in enumerate(yer)):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    if not budama:
        cozum = [c for c in cozum
                 if all(c[i] != c[j] and abs(c[i] - c[j]) != j - i
                        for i in range(n) for j in range(i + 1, n))]
    return {"dugum": s.adim, "cozum": len(cozum)}


for n in (5, 6, 7):
    b, k = vezir(n, True), vezir(n, False)
    print(f"n={n} budamali dugum {b['dugum']:5d} cozum {b['cozum']:3d}"
          f" | budamasiz dugum {k['dugum']:7d} cozum {k['cozum']:3d}"
          f" | oran {k['dugum'] / b['dugum']:7.1f}")
b8 = vezir(8, True)
print(f"n=8 budamali dugum {b8['dugum']:5d} cozum {b8['cozum']:3d}"
      f" | budamasiz {8 ** 8} yerlesim taranirdi (oran {8 ** 8 / b8['dugum']:.1f})")

n=5 budamali dugum    54 cozum  10 | budamasiz dugum    3906 cozum  10 | oran    72.3
n=6 budamali dugum   153 cozum   4 | budamasiz dugum   55987 cozum   4 | oran   365.9
n=7 budamali dugum   552 cozum  40 | budamasiz dugum  960800 cozum  40 | oran  1740.6
n=8 budamali dugum  2057 cozum  92 | budamasiz 16777216 yerlesim taranirdi (oran 8156.2)

Çözüm sütunları üç satırda da aynı: 10, 4, 40. Budama hiçbir çözümü kaçırmıyor, yani ayrılan girdi sıfırdır. Düğüm sütunları ise uçurumu gösteriyor: yedi vezirlik tahtada 552’ye karşı 960.800 düğüm, oran 1740,6. Sekiz vezirlikte budamalı arama 2057 düğümde bitiyor; budamasız arama 16.777.216 yerleşim tarardı ve oran 8156,2 olurdu.

Oran $n$ ile büyüyor: 72,3 sonra 365,9 sonra 1740,6 sonra 8156,2 — her adımda yaklaşık beş kat. Budamanın kazancı ölçek arttıkça artıyor. Ama ikinci bir okuma bunu dengeler: budamalı düğüm sayısının kendisi de 54, 153, 552, 2057 diye gidiyor, yani her adımda yaklaşık 3,7 kat. Budama üstel uzayı kesiyor ama üstelliği yok etmiyor. İki katı büyük bir tahta, budamalı aramada da erişilmez kalır; budama erteler, çözmez.

Kesmenin Hangi Kısıttan Geldiği

Vezir probleminin iki kısıtı vardır — aynı sütun ve aynı köşegen — ve budama ikisini birden kullanıyordu. Kısıtlar ayrı ayrı da uygulanabilir; her biri kesin olarak çözümsüz dalları kestiği için üçü de doğruluğu korur.

# Onceki bloklarin uzerine: Sayac oradan gelir.
def parcali_budama(n, olcut):
    """olcut: yok | sutun | kosegen | ikisi. Hepsinde yaprakta tam dogrulama var."""
    s = Sayac()
    cozum = 0

    def gez(satir, yer):
        nonlocal cozum
        s.say()
        if satir == n:
            if all(yer[i] != yer[j] and abs(yer[i] - yer[j]) != j - i
                   for i in range(n) for j in range(i + 1, n)):
                cozum += 1
            return
        for sutun in range(n):
            if olcut in ("sutun", "ikisi") and sutun in yer:
                continue
            if olcut in ("kosegen", "ikisi") and any(
                    abs(sutun - y) == satir - i for i, y in enumerate(yer)):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    return {"dugum": s.adim, "cozum": cozum}


print("n=7  olcut      dugum   cozum")
for olcut in ("yok", "sutun", "kosegen", "ikisi"):
    r = parcali_budama(7, olcut)
    print(f"     {olcut:9s} {r['dugum']:7d} {r['cozum']:7d}")

n=7  olcut      dugum   cozum
     yok        960800      40
     sutun       13700      40
     kosegen     10736      40
     ikisi         552      40

Çözüm sütunu dört satırda da 40; dördü de doğru. Düğüm sütunu ise budamanın gücünün neye bağlı olduğunu gösteriyor. Yalnız sütun kısıtı 960.800 düğümü 13.700’e indiriyor — 70,1 kat. Yalnız köşegen kısıtı 10.736’ya indiriyor — 89,5 kat. İkisi birlikte 552, yani 1740,6 kat. Birleşik kesme, iki tekil kesmenin toplamından çok daha fazlasını kazandırıyor; çünkü bir kısıtın bıraktığı dalların çoğunu öteki kısıt kesiyor.

Buradan çıkan tasarım kuralı ölçülmüştür: bir kısıt ne kadar erken kanıtlanabilirse o kadar çok keser. Kısıtları yaprakta sınamak bir doğrulamadır, düğümde sınamak bir budamadır; aradaki fark bu problemde 960.800 ile 552 arasındaki farktır.

Budama Ölçütü Yanlış Olduğunda

Aynı arama, üç farklı ölçütle koşturulur. İkisi ön koşulu bozar.

# Onceki blogun uzerine: Sayac ve vezir oradan gelir.
def vezir_kipli(n, kip):
    """kip: dogru | asiri (komsu sutun degerini de keser) | eksik (yalniz onceki satir)"""
    s = Sayac()
    cozum = []

    def catisma(sutun, satir, yer):
        if kip == "eksik":
            i = satir - 1
            return i >= 0 and (sutun == yer[i] or abs(sutun - yer[i]) == 1)
        temel = any(sutun == y or abs(sutun - y) == satir - i
                    for i, y in enumerate(yer))
        if kip == "asiri":                        # "vezirler yan yana sutunda olmasin"
            return temel or any(abs(sutun - y) == 1 for y in yer)
        return temel

    def gez(satir, yer):
        s.say()
        if satir == n:
            cozum.append(tuple(yer))
            return
        for sutun in range(n):
            if catisma(sutun, satir, yer):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    return {"dugum": s.adim, "cozum": len(cozum)}


print(" n  kahin cozum  dogru budama      asiri budama      eksik budama")
ayrilan = {"dogru": 0, "asiri": 0, "eksik": 0}
for n in (5, 6, 7):
    kahin = vezir(n, False)
    satir = f"{n:2d} {kahin['cozum']:12d}"
    for kip in ("dogru", "asiri", "eksik"):
        r = vezir_kipli(n, kip)
        if r["cozum"] != kahin["cozum"]:
            ayrilan[kip] += 1
        satir += f"  {r['cozum']:4d} ({r['dugum']:5d})"
    print(satir)
print("kahinden ayrilan tahta sayisi (3 uzerinden):", ayrilan)

 n  kahin cozum  dogru budama      asiri budama      eksik budama
 5           10    10 (   54)     0 (   20)   184 (  306)
 6            4     4 (  153)     0 (   39)  2642 ( 3747)
 7           40    40 (  552)     0 (   82)  45514 (59196)
kahinden ayrilan tahta sayisi (3 uzerinden): {'dogru': 0, 'asiri': 3, 'eksik': 3}

Üç sayı yan yana ve bu kez ikisi de kötü. Doğru budama üç tahtada da kâhinin çözüm sayısını veriyor: 10, 4, 40. Aşırı budama üçünde de sıfır çözüm buluyor — “vezirler yan yana sütunlarda durmasın” kuralı makul görünür, ama kesin olarak çözümsüz olmayan dalları kestiği için geriye hiçbir şey bırakmıyor. Eksik budama yalnız bir önceki satıra baktığı için uzak satırlardaki köşegen çatışmalarını göremiyor ve yedi vezirlik tahtada 40 yerine 45.514 yerleşimi çözüm sayıyor.

Düğüm sütunları burada tuzaktır. Aşırı budama yedi vezirlikte 82 düğümde bitiyor; doğru budamanın 552 düğümüne göre 6,7 kat hızlı. Bir ölçüm yalnız düğüm sayarsa aşırı budama en iyi yordam görünür. Eksik budama ise 59.196 düğüm gezerek en yavaşı; yani yanlış olmak her zaman hızlı değildir. Yanlışlığın iki biçimi vardır ve düğüm sayısı ikisini de ele vermez; ele veren tek şey kâhinin çözüm sayısıdır.

Yasaklı Karelerde Dağarcık

Tek bir tahta ailesi bir dağarcık değildir. Ölçüm, altı vezirlik tahtaya üçer yasak kare eklenerek kırk ayrı örneğe taşınır ve iki tohumla koşturulur.

# Onceki bloklarin uzerine: Sayac ve vezir_kipli oradan gelir.
def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


N = 6
YASAK_SAYISI = 3


def tahta_dagarcigi(tohum, adet=40):
    """Her tahtada 3 kare yasak. Yasak kareler tohumdan gelir."""
    r = uretec(tohum)
    return [{"no": i + 1, "yasak": {(r(N), r(N)) for _ in range(YASAK_SAYISI)}}
            for i in range(adet)]


def yasakli_arama(n, yasak, kip, s):
    """kip: kahin (budamasiz, sonda dogrula) | dogru | asiri"""
    cozum = []

    def gecerli(c):
        if any((i, c[i]) in yasak for i in range(n)):
            return False
        return all(c[i] != c[j] and abs(c[i] - c[j]) != j - i
                   for i in range(n) for j in range(i + 1, n))

    def gez(satir, yer):
        s.say()
        if satir == n:
            if kip != "kahin" or gecerli(tuple(yer)):
                cozum.append(tuple(yer))
            return
        for sutun in range(n):
            if kip != "kahin":
                if (satir, sutun) in yasak:
                    continue
                if any(sutun == y or abs(sutun - y) == satir - i
                       for i, y in enumerate(yer)):
                    continue
                if kip == "asiri" and any(abs(sutun - y) == 1 for y in yer):
                    continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
    gez(0, [])
    return len(cozum)


for ad, tohum in (("birinci dagarcik (20260218)", 20260218),
                  ("ikinci  dagarcik (20260219)", 20260219)):
    tahtalar = tahta_dagarcigi(tohum)
    sh, sd, sa = Sayac(), Sayac(), Sayac()
    ay_dogru, ay_asiri, kayip = 0, 0, 0
    for t in tahtalar:
        h = yasakli_arama(N, t["yasak"], "kahin", sh)
        d = yasakli_arama(N, t["yasak"], "dogru", sd)
        a = yasakli_arama(N, t["yasak"], "asiri", sa)
        ay_dogru += h != d
        ay_asiri += h != a
        kayip += h - a
    print(ad)
    print("  kahin dugum", sh.adim, "| dogru budama dugum", sd.adim,
          "| oran", round(sh.adim / sd.adim, 2))
    print("  ayrilan girdi: dogru budama", ay_dogru, "/ 40 | asiri budama",
          ay_asiri, "/ 40 | kaybolan cozum", kayip)

birinci dagarcik (20260218)
  kahin dugum 2239480 | dogru budama dugum 4736 | oran 472.86
  ayrilan girdi: dogru budama 0 / 40 | asiri budama 40 / 40 | kaybolan cozum 92
ikinci  dagarcik (20260219)
  kahin dugum 2239480 | dogru budama dugum 4452 | oran 503.03
  ayrilan girdi: dogru budama 0 / 40 | asiri budama 40 / 40 | kaybolan cozum 90

Kâhinin düğüm sayısı iki dağarcıkta birebir aynı: 2.239.480. Bu beklenen sonuçtur — budamasız arama yasak karelere bakmadan bütün yerleşimleri üretir, yani düğüm sayısı tahtadan bağımsızdır. Doğru budamanın düğümü 4736 ile 4452 arasında değişiyor, çünkü yasak kareler dalları erkenden kesiyor; oran 472,86 ve 503,03.

Ayrılan girdi sayıları iki dağarcıkta da aynı yönü gösteriyor: doğru budama 0/40, aşırı budama 40/40. Kaybolan çözüm sayısı 92 ile 90; aradaki iki çözümlük fark yasak karelerin yerleşiminden gelir ve ölçünün anlamlı saydığı eşiğin altındadır. Okuma iki dağarcıkta da değişmiyor: doğru budama kırk tahtanın kırkında kâhinle aynı, aşırı budama kırkında da farklı.

Özet

• Geri izleme, kısmi çözüm ağacında bir dalın altında çözüm olmadığı kanıtlandığında o dalı keser; kesmenin meşruluğu bu kanıta bağlıdır.
• Doğru budama yedi vezirlik tahtada 552, budamasız arama 960.800 düğüm geziyor (oran 1740,6) ve çözüm sayıları aynı kalıyor: 10, 4, 40.
• Oran $n$ ile yaklaşık beş kat büyüyor (72,3 · 365,9 · 1740,6 · 8156,2), ama budamalı düğüm sayısı da 3,7 kat büyüyor: budama üstelliği kesmez, erteler.
• Aşırı budama yedi vezirlikte 82 düğümde bitip sıfır çözüm buluyor; yalnız düğüm sayan bir ölçümde en iyi yordam görünür.
• Eksik budama 59.196 düğüm gezip 40 yerine 45.514 yerleşimi çözüm sayıyor; yanlışlık her zaman hızlı değildir.
• Kırk yasaklı tahtada doğru budama 0/40, aşırı budama 40/40 ayrılıyor; ikinci dağarcıkta aynı sonuç, kaybolan çözüm 92 yerine 90.

Sonraki Adım

Şimdiye kadarki bütün yordamlar belirlenimciydi: aynı girdi her zaman aynı adımları ve aynı yanıtı veriyordu. Son tasarım yaklaşımı bu güvenceyi gevşetir ve karşılığında bir şey ister — bazen adım sayısının, bazen de yanıtın kendisinin rastgele olmasını. Sonraki ders iki tür rastgeleleştirmeyi aynı dağarcıkta ölçer ve tek bir soruyu yanıtlar: rastgele bir yordamın kaç girdide yanıldığı, tohum değiştiğinde değişiyor mu.