--- title: 'Geri İzleme' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/geri-izleme' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # Geri İzleme Budamanın doğruluğu koruyan tek kısaltma olduğu ve ölçütü bozulduğunda ne olduğu: yedi vezirlik tahtada budamalı arama 552, budamasız arama 960.800 düğüm geziyor, ama komşu sütunu da kesen aşırı budama 82 düğümde bitip çözümlerin tamamını kaybediyor. 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 ```python # 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. ```python # 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. ```python # 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. ```python # 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.