--- title: 'At Turu ve Labirent Problemleri' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/at-turu-ve-labirent-problemleri' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # At Turu ve Labirent Problemleri Aynı ızgaranın iki ayrı modelle temsil edilmesi ve arama alanının modelle birlikte değişmesi: beşe beşlik ızgarada çözüm adayı yol sayılınca 8512 basit yol ve 90.111 adım, hücre sayılınca 25 adım; oran 3604 ve iki model aynı en kısa uzunluğu veriyor. At turunda en az seçenek bırakan kareyi önce deneme sırası beşe beşlik tahtada dört başlangıcın dördünde de turu 25 düğümde buluyor, doğal sıra 182 ile 101.718 arasında düğüm geziyor. Dörde dörtlük tahtada hiç tur yok ve iki sıralama da tam olarak 29.976 düğüm geziyor: sıralama sezgiseli hayır yanıtında hiçbir şey kazandırmıyor. N vezirde arama alanı tahtadan okunuyordu: her satıra bir vezir, her vezire n seçenek. Uzayın büyüklüğü problemin tanımından çıkıyordu ve tartışılacak bir yanı yoktu. Bu ders o rahatlığı kaldırır. At turu ve labirent aynı ızgara üzerinde tanımlanır, ama taranacak nesnenin ne olduğuna karar veren şey problem değil **modeldir**, ve iki model arasındaki fark binlerce kata çıkar. Labirent problemi şudur: bir ızgaranın sol üst hücresinden sağ alt hücresine, komşu hücreler arasında ilerleyerek gidilecek. At turu problemi şudur: beşe beşlik bir tahtada bir attan başlanıp her kareye tam bir kez uğranacak. İkisi de bir arama problemidir, ve ikisinde de sorulacak ilk soru "hangi algoritma" değil, **"neyin arandığı"** sorusudur. - **KP40.** Labirentte iki model karşılaştırılır. **Birinci modelde** çözüm adayı bir **yoldur**; taranan nesne, sol üstten sağ alta giden bütün basit yollardır. **İkinci modelde** çözüm adayı bir **hücredir**; her hücre en çok bir kez açılır. - **KP41.** İkinci model, M01/K03 Veri Yapıları kursunun Çizgeler konusunda kurulan **enine aramadır**. Yordam **tekrarlanmaz**, doğrudan kullanılır. - **KP42.** Kâhin birinci modeldir: bütün basit yolları tarar ve en kısasını bulur. İkinci modelin verdiği uzunluk bununla karşılaştırılır. - **KP43.** Izgara engelsizdir. Engel eklemek yol sayısını değiştirir ama iki modelin **oranını değiştirmez**; ölçülen şey oranın büyüklük düzenidir. **Bu dersin girdisi de üreteçten gelmez:** ızgara boyu ve tahta boyu tek girdidir, bütün sayılar tam sayımdır. İkinci dağarcık kuralının yerini **boy süpürmesi** alır ve tohuma bağlı hiçbir değer yoktur. - **KP44.** Ölçü **adımdır**. Birinci modelde bir adım bir kısmi yol düğümü, ikinci modelde bir hücre açılışıdır. - **KP45.** At turunda iki sıralama karşılaştırılır: kareleri **doğal sırada** denemek, ve **en az seçenek bırakan** kareyi önce denemek. İkinci sıralama bir budama değildir; hiçbir dal kesilmez, yalnız denenme sırası değişir. - **KP46.** İkinci sıralama bir sezgiseldir ve doğruluğu **varsayılmaz**. Bulduğu her tur kâhinle doğrulanır: bütün kareler bir kez mi ziyaret edilmiş, her adım geçerli bir at hamlesi mi. - **KP47.** Beşe beşlik tahtada dört başlangıç karesi ölçülür. Bütün kareleri ölçmek, tur bulunmayan karelerde arama alanının tamamının taranmasını gerektirir ve koşum bütçesini aşar. - **KP48.** Tur bulunmayan durum **dörde dörtlük tahtada** ölçülür; orada hiçbir kareden tur yoktur ve arama alanının tamamı taranabilir. - **KP49.** Ucuz modelin sınırı, soruyu değiştirerek sınanır. Aynı sayımdan hem en kısa yol hem de bütün hücrelerden geçen yol sayılır; bir modelin yeterliliği sorudan bağımsız yazılmaz. ## Aynı Izgara, İki Model Birinci model soruyu şöyle kurar: sol üstten sağ alta giden bütün yolları üret, en kısasını seç. İkinci model şöyle kurar: sol üstten başlayarak hücreleri uzaklık sırasına göre aç, sağ alta ilk varışta dur. İkisi de doğru yanıtı verir; ölçülen şey neye mal olduğudur. ```python from collections import deque class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def komsular(h, r, c): for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): i, j = h[0] + dr, h[1] + dc if 0 <= i < r and 0 <= j < c: yield (i, j) def kahin_butun_yollar(r, c, s): """Model 1: cozum adayi bir YOLDUR. Butun basit yollar taranir.""" hedef, sayi, en_kisa = (r - 1, c - 1), 0, None def gez(h, gorulen): nonlocal sayi, en_kisa s.say() if h == hedef: sayi += 1 if en_kisa is None or len(gorulen) < en_kisa: en_kisa = len(gorulen) return for k in komsular(h, r, c): if k not in gorulen: gez(k, gorulen | {k}) gez((0, 0), {(0, 0)}) return sayi, en_kisa def kalip_enine(r, c, s): """Model 2: cozum adayi bir HUCREDIR. Her hucre en cok bir kez acilir.""" hedef = (r - 1, c - 1) kuyruk, gorulen = deque([((0, 0), 1)]), {(0, 0)} while kuyruk: h, u = kuyruk.popleft() s.say() if h == hedef: return u for k in komsular(h, r, c): if k not in gorulen: gorulen.add(k) kuyruk.append((k, u + 1)) return None print(" izgara | basit yol sayisi | kahin adim | enine adim | oran | en kisa") for n in (3, 4, 5): s1, s2 = Sayac(), Sayac() sayi, en_kisa = kahin_butun_yollar(n, n, s1) u = kalip_enine(n, n, s2) print(f" {n}x{n:2d} | {sayi:16d} | {s1.adim:10d} | {s2.adim:10d} |" f" {s1.adim // s2.adim:5d} | {en_kisa} ve {u}") ``` ``` izgara | basit yol sayisi | kahin adim | enine adim | oran | en kisa 3x 3 | 12 | 51 | 9 | 5 | 5 ve 5 4x 4 | 184 | 1271 | 16 | 79 | 7 ve 7 5x 5 | 8512 | 90111 | 25 | 3604 | 9 ve 9 ``` ## Uzayı Belirleyen Şey Model Son sütun iki modelin **aynı yanıtı** verdiğini gösteriyor: üç ızgaranın üçünde de en kısa uzunluk aynı, ayrılan girdi 0. İkinci model bir yaklaşık çözüm değil, kâhinle tam olarak uyuşan bir çözümdür. Ama maliyetleri aynı değil. Beşe beşlik ızgarada birinci model **8512 basit yol** üretmek için **90.111 adım** harcıyor; ikinci model **25 adım** harcıyor, yani hücre başına bir adım. Oran **3604**. Üçe üçlük ızgarada oran 5, dörde dörtlükte 79, beşe beşlikte 3604. Oran ızgara büyüdükçe hızla açılıyor. Farkın kaynağı algoritma değil, **sayılan nesnedir**. Birinci modelde aday bir yoldur ve yol sayısı hücre sayısıyla üstel büyür. İkinci modelde aday bir hücredir ve hücre sayısı ızgaranın alanı kadardır. İkinci model, birinci modelin ürettiği 8512 yolu **üretmeden** aralarındaki en kısayı bulur, çünkü aynı hücreye farklı yollardan varmanın sonrasını değiştirmediğini kullanır. Buradan kursun ölçü okumasına bağlanan bir cümle çıkar: **arama alanının büyüklüğü problemin değil, modelin özelliğidir.** Bir problem için "arama alanı çok büyük" demek, ancak hangi modelin kastedildiği söylendiğinde bir anlam taşır. Aynı labirent bir modelde 8512 adaya, başka bir modelde 25 adaya sahiptir. ## Ucuz Modelin Yanıtlayamadığı Soru Ucuz modelin bir bedeli var ve şimdiye kadar görünmedi. Enine arama, aynı hücreye farklı yollardan varmanın sonrasını değiştirmediğini kullanıyordu. Bu varsayım en kısa yol sorusunda doğrudur, ama her soruda doğru değildir. Aşağıdaki blok aynı sayımı yapıp yolları **uzunluklarına göre** ayırır. ```python from collections import Counter class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def yollar(n, s): """Butun basit yollar; uzunluklarina gore sayilir.""" hedef, sayim = (n - 1, n - 1), Counter() def gez(h, gorulen): s.say() if h == hedef: sayim[len(gorulen)] += 1 return for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): k = (h[0] + dr, h[1] + dc) if 0 <= k[0] < n and 0 <= k[1] < n and k not in gorulen: gez(k, gorulen | {k}) gez((0, 0), {(0, 0)}) return sayim for n in (4, 5): s = Sayac() sayim = yollar(n, s) tam = sayim[n * n] print(f"{n}x{n} | yol {sum(sayim.values()):5d} | adim {s.adim:6d}" f" | en kisa {min(sayim)} uzunlugunda {sayim[min(sayim)]:3d} yol" f" | butun hucreleri gezen {tam:3d} yol") print(" uzunluga gore:", dict(sorted(sayim.items()))) ``` ``` 4x4 | yol 184 | adim 1271 | en kisa 7 uzunlugunda 20 yol | butun hucreleri gezen 0 yol uzunluga gore: {7: 20, 9: 36, 11: 48, 13: 48, 15: 32} 5x5 | yol 8512 | adim 90111 | en kisa 9 uzunlugunda 70 yol | butun hucreleri gezen 104 yol uzunluga gore: {9: 70, 11: 224, 13: 510, 15: 956, 17: 1586, 19: 2224, 21: 2106, 23: 732, 25: 104} ``` Beşe beşlik ızgarada 8512 yolun **70'i** en kısa uzunluktadır ve **104'ü bütün 25 hücreden** geçer. Enine arama birinci sayıyı 25 adımda verir. İkinci sayı için hiçbir şey söyleyemez: hücre başına tek bir değer tuttuğu için, bir hücreye hangi hücreler kullanılarak gelindiğini unutur, ve "bütün hücrelerden geçen bir yol var mı" sorusu tam olarak bu bilgiyi ister. Soru değişince 25 adımlık model düşer, geriye 90.111 adımlık sayım kalır. Dörde dörtlük satır aynı sorunun **hayır** yanıtını gösteriyor: 184 yolun hiçbiri 16 hücrenin tamamından geçmiyor, en uzunu 15 hücrelik. Bu hayır yanıtı da 1271 adımın tamamı harcanmadan alınamaz. Aramanın bir sorusu ucuzlarken ötekinin ucuzlamadığını görmek, modelin **soruyla birlikte** seçildiğinin kanıtıdır. ## At Turunda Sıralamanın Payı At turunda ikinci model doğrudan kurulamaz. Bir kareye hangi yoldan gelindiği **önemlidir**, çünkü hangi karelerin kullanıldığı sonrasını belirler. Aday, hücre değil **kısmi turdur** ve arama alanı üsteldir. Elde kalan tek araç, dalların **denenme sırasıdır**. Sezgi şudur: seçeneği en az olan kareye erken gidilmezse o kare sonradan erişilemez hale gelir ve arama boşa dolaşır. Aşağıdaki blok bu sırayı doğal sırayla karşılaştırır ve bulunan her turu kâhinle doğrular. ```python HAMLE = ((1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)) class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def secenekler(h, gidilen, n): r, c = h return [(r + a, c + b) for a, b in HAMLE if 0 <= r + a < n and 0 <= c + b < n and (r + a, c + b) not in gidilen] def tur(bas, n, siralama, s): """Ilk tam turda durur. siralama=True: en az secenek birakan kare once.""" def gez(h, gidilen): s.say() if len(gidilen) == n * n: return [h] aday = secenekler(h, gidilen, n) if siralama: aday.sort(key=lambda k: len(secenekler(k, gidilen | {k}, n))) for k in aday: y = gez(k, gidilen | {k}) if y: return [h] + y return None return gez(bas, {bas}) def dogrula(yol, n): """Hakem: her kare bir kez mi, her adim gecerli bir at hamlesi mi.""" if yol is None or len(set(yol)) != n * n: return False return all((abs(a[0] - b[0]), abs(a[1] - b[1])) in ((1, 2), (2, 1)) for a, b in zip(yol, yol[1:])) print("5x5 | baslangic | dogal sira dugum | en az secenek dugum | dogrulanan tur") for bas in ((0, 0), (0, 2), (2, 2), (4, 0)): s1, s2 = Sayac(), Sayac() y1, y2 = tur(bas, 5, False, s1), tur(bas, 5, True, s2) print(f" | {str(bas):9s} | {s1.adim:16d} | {s2.adim:19d} |" f" {dogrula(y1, 5)} ve {dogrula(y2, 5)}") t1 = t2 = bulan = 0 for i in range(4): for j in range(4): s1, s2 = Sayac(), Sayac() y1, y2 = tur((i, j), 4, False, s1), tur((i, j), 4, True, s2) t1, t2 = t1 + s1.adim, t2 + s2.adim bulan += 1 if dogrula(y1, 4) else 0 print(f"4x4 | 16 kare | {t1:16d} | {t2:19d} | bulunan tur {bulan}") ``` ``` 5x5 | baslangic | dogal sira dugum | en az secenek dugum | dogrulanan tur | (0, 0) | 70716 | 25 | True ve True | (0, 2) | 101718 | 25 | True ve True | (2, 2) | 25542 | 25 | True ve True | (4, 0) | 182 | 25 | True ve True 4x4 | 16 kare | 29976 | 29976 | bulunan tur 0 ``` ## Evet Ucuz, Hayır Değil Beşe beşlik tahtada en az seçenek sırası dört başlangıcın dördünde de turu **25 düğümde** buluyor. Yirmi beş, tahtadaki kare sayısıdır: arama hiç geri dönmüyor, her karede doğru hamleyi ilk denemede seçiyor. Doğal sıra aynı turları 182 ile **101.718** düğüm arasında buluyor. Kareler farklı olduğu için satırlar birbiriyle değil, kendi içinde karşılaştırılmalıdır; her satırda oran en az 7, en çoğu 4068. Doğrulama sütunu bu satırların hepsinde `True`. Sezgiselin bulduğu turlar gerçekten turdur: yirmi beş karenin hepsi bir kez ziyaret edilmiş ve her adım geçerli bir at hamlesidir. Sezgisel hızlandırmıyor demek yetmez, **yanlış da yapmıyor** ve bu ayrıca ölçülmüştür. Son satır dersin en sert sayısıdır. Dörde dörtlük tahtada hiçbir kareden tur yoktur. İki sıralama da bunu bulmak için **tam olarak 29.976 düğüm** geziyor. Sayılar eşit, fark sıfır. Sıralama sezgiseli burada hiçbir şey kazandırmıyor, çünkü kazandırdığı şey **doğru dalı erken bulmaktı**; doğru dal yoksa bütün dallar denenir ve denenme sırası toplamı değiştirmez. Bu, sıralama sezgiselleriyle budamanın arasındaki farkın ölçülmüş halidir. Budama arama uzayından **parça siler**, bu yüzden yanıt evet de olsa hayır da olsa kazandırır. Sıralama uzaydan hiçbir şey silmez, yalnız gezinme yönünü değiştirir; bu yüzden yalnız **evet** yanıtında kazandırır. Bir sezgiselin sayısı, hangi yanıt için ölçüldüğü söylenmeden okunamaz. ## Özet - Aynı labirent iki modelde iki ayrı arama alanı üretir: çözüm adayı yol sayılınca beşe beşlik ızgarada 8512 aday ve 90.111 adım, hücre sayılınca 25 adım; oran 3604. - İki model üç ızgaranın üçünde de aynı en kısa uzunluğu veriyor; ayrılan girdi 0, yani ucuz model bir yaklaşım değil tam çözümdür. - Arama alanının büyüklüğü problemin değil modelin özelliğidir; "uzay çok büyük" cümlesi hangi modelin kastedildiği söylenmeden anlam taşımaz. - Ucuz modelin sınırı soruyla belirlenir: 8512 yolun 104'ü bütün hücrelerden geçiyor, ama enine arama bu sayıyı veremez ve soru değişince 90.111 adımlık sayıma dönülür. - At turunda en az seçenek bırakan kareyi önce deneme sırası, beşe beşlik tahtada dört başlangıcın dördünde de turu 25 düğümde buluyor; doğal sıra 182 ile 101.718 düğüm arasında. - Dörde dörtlük tahtada tur yoktur ve iki sıralama da 29.976 düğüm geziyor: sıralama sezgiseli hayır yanıtında hiçbir şey kazandırmaz, çünkü uzaydan parça silmez. ## Sonraki Adım Bu dersin son satırı bir ayrım açtı: bir aramanın evet yanıtı ile hayır yanıtı aynı şeye mal olmuyor. Sonraki ders bu ayrımı konunun ana sorusu yapar. Hamilton yolu problemi bir **varlık** sorusudur ve karar problemi olarak kurulur; ölçülecek şey karar vermek, yolu bulmak ve verilen bir yolu doğrulamak arasındaki adım farkıdır. Sınıf adları yine M01/K08'e bırakılacak, ama fark burada sayılacak.