--- title: 'Izgara Gezinmesi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/izgara-gezinmesi' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # Izgara Gezinmesi Matriste bağlı bileşen arama; komşuluk tanımının 38 ızgarada değiştirdiği yanıt ve işaretleme ile gezinme seçiminin tutulan hücre sayısına etkisi. Bu konunun yedi kalıbı da tek boyutlu veriyle çalıştı: bir dizi, bir akış, bir ardıl zinciri. Son kalıp veriyi **iki boyutta** ele alır. Bir ızgarada dolu hücreler vardır ve soru şudur: birbirine bağlı kaç hücre kümesi var. Izgara aslında yeni bir yapı değildir. Her dolu hücre bir düğüm, her komşu hücre çifti bir kenardır; sorulan şey **bağlı bileşen** sayısıdır ve yordam Veri Yapıları kursunda kuruldu. Enine ve derine aramanın kendisi, ziyaret işaretlemesinin neden zorunlu olduğu ve $O(V + E)$ maliyeti orada ölçüldü; burada **tekrarlanmaz**, doğrudan kullanılır. Kalıbın eklediği şey modellemedir ve ön koşulu da orada durur: **komşuluğun ne demek olduğu**. Bu ders iki komşuluk tanımının aynı ızgarada kaç farklı yanıt ürettiğini sayar. ## Problem, Kâhin ve Kalıp Kâhin hiçbir gezinme yapmaz. Bütün dolu hücre çiftlerini tarar, bitişik olanları aynı gruba alır ve hiçbir birleşme kalmayana kadar yineler. Kalıp her ziyaret edilmemiş dolu hücreden bir enine arama başlatır ve her arama bir bileşen sayar. **PK56.** Dağarcık 40 ızgaradır; her ızgara 8×8'dir ve her hücre 100'de 30 olasılıkla doludur. Tohum `20260218`. **PK57.** İki komşuluk tanımı ölçülür: **dört komşuluk** (yalnız kenardaş hücreler) ve **sekiz komşuluk** (köşedeş hücreler de dahil). **PK58.** Kâhin ve kalıp **ayrı ayrı** komşuluk tanımıyla çalıştırılır; dört bileşim de ölçülür. Böylece ayrılmanın kalıptan mı tanım farkından mı geldiği görülür. **PK59.** Ziyaret işaretlemesi kuyruğa **eklerken** yapılır; bu, enine arama dersinde kurulan kuraldır ve burada gerekçesi tekrarlanmaz. ```python from collections import deque TOHUM, BOY, DAGARCIK = 20260218, 8, 40 def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def izgara_dagarcik(tohum=TOHUM, n=DAGARCIK, boy=BOY): r = uretec(tohum) return [{"no": i + 1, "izgara": [[1 if r(101) < 30 else 0 for _ in range(boy)] for _ in range(boy)]} for i in range(n)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def bitisik(a, b, komsuluk): di, dj = abs(a[0] - b[0]), abs(a[1] - b[1]) return di + dj == 1 if komsuluk == 4 else max(di, dj) == 1 and (di or dj) def kahin_bilesen(izgara, komsuluk, s): """Butun hucre ciftlerini tarar, bitisik olanlari ayni gruba alir, degisiklik bitene kadar yineler. Her zaman dogru, her zaman pahali.""" hucre = [(i, j) for i, satir in enumerate(izgara) for j, v in enumerate(satir) if v] grup = {h: i for i, h in enumerate(hucre)} degisti = True while degisti: degisti = False for a in range(len(hucre)): for b in range(a + 1, len(hucre)): s.say() if bitisik(hucre[a], hucre[b], komsuluk) and \ grup[hucre[a]] != grup[hucre[b]]: eski, yeni = grup[hucre[b]], grup[hucre[a]] for h in hucre: if grup[h] == eski: grup[h] = yeni degisti = True return len(set(grup.values())) YON4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) YON8 = YON4 + ((-1, -1), (-1, 1), (1, -1), (1, 1)) def kalip_enine(izgara, komsuluk, s): """Veri Yapilari kursunun enine aramasi dogrudan kullanilir: isaretleme kuyruga EKLERKEN yapilir.""" yon = YON4 if komsuluk == 4 else YON8 n, m = len(izgara), len(izgara[0]) ziyaret, bilesen, en_genis = set(), 0, 0 for i in range(n): for j in range(m): if not izgara[i][j] or (i, j) in ziyaret: continue bilesen += 1 ziyaret.add((i, j)) kuyruk = deque([(i, j)]) while kuyruk: en_genis = max(en_genis, len(kuyruk)) x, y = kuyruk.popleft() s.say() for dx, dy in yon: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and izgara[a][b] \ and (a, b) not in ziyaret: ziyaret.add((a, b)) kuyruk.append((a, b)) return bilesen, en_genis K = izgara_dagarcik() dolu = sum(sum(sum(s) for s in k["izgara"]) for k in K) print("dagarcik:", len(K), "izgara x", BOY, "x", BOY, "| dolu hucre:", dolu, "| ortalama", round(dolu / len(K), 2)) print("kalip komsulugu kahin komsulugu ayrilan/40 kalip kahin oran") for kk in (4, 8): for hk in (4, 8): ayrilan, ak, ah = 0, 0, 0 for kayit in K: s1, s2 = Sayac(), Sayac() a, _ = kalip_enine(kayit["izgara"], kk, s1) b = kahin_bilesen(kayit["izgara"], hk, s2) ak, ah = ak + s1.adim, ah + s2.adim ayrilan += (a != b) print(f"{kk:15d} {hk:15d} {ayrilan:10d} {ak:5d} {ah:6d}" f" {ah / ak:6.1f}") ``` ``` dagarcik: 40 izgara x 8 x 8 | dolu hucre: 723 | ortalama 18.07 kalip komsulugu kahin komsulugu ayrilan/40 kalip kahin oran 4 4 0 723 12768 17.7 4 8 38 723 12834 17.8 8 4 38 723 12768 17.7 8 8 0 723 12834 17.8 ``` Köşegen satırlar sıfır, diğer ikisi **38**. Kalıp, kâhinle **aynı komşuluk tanımını** kullandığında 40 ızgaranın 40'ında aynı yanıtı veriyor; tanımlar ayrıldığında 40 ızgaranın 38'i ayrılıyor. Bu tablo bir şeyi kesin kılıyor: **ayrılma kalıptan gelmiyor.** Enine arama her iki tanımla da doğru çalışır; bozulan şey kalıbın kendisi değil, kalıba verilen **komşuluk tanımıdır**. Kalıbın adımı iki tanımda da **723**, kâhinin adımı 12.768 ile 12.834; oran **17,7**. Adım sütunu dört satırda da neredeyse aynı ve ayrılan girdi sütununu hiç haber vermiyor. ## Komşuluk Bir Veri Özelliği Değil, Bir Karardır Önceki yedi kalıpta ön koşul girdinin bir özelliğiydi: sıralı mı, negatif var mı, tekrar var mı. Burada ön koşul girdide değildir; **modelleyenin verdiği bir karardır** ve veriye bakarak doğrulanamaz. Aşağıdaki küçük ızgara farkı bir bakışta gösterir. **PK60.** Küçük örnek elle kurulmuştur; üreteçten gelmez ve yalnız iki tanımın ayrımını göstermek içindir. **PK61.** İkinci dağarcık `20260219` tohumundan gelir. Ölçülen şey, iki tanımın **kaç ızgarada** farklı bileşen sayısı verdiğidir. ```python from collections import deque def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def izgara_dagarcik(tohum, n=40, boy=8): r = uretec(tohum) return [[[1 if r(101) < 30 else 0 for _ in range(boy)] for _ in range(boy)] for _ in range(n)] YON4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) YON8 = YON4 + ((-1, -1), (-1, 1), (1, -1), (1, 1)) def bilesen(izgara, komsuluk): """Enine arama ile bagli bilesen sayimi; isaretleme eklerken yapilir.""" yon = YON4 if komsuluk == 4 else YON8 n, m = len(izgara), len(izgara[0]) ziyaret, say = set(), 0 for i in range(n): for j in range(m): if not izgara[i][j] or (i, j) in ziyaret: continue say += 1 ziyaret.add((i, j)) kuyruk = deque([(i, j)]) while kuyruk: x, y = kuyruk.popleft() for dx, dy in yon: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and izgara[a][b] \ and (a, b) not in ziyaret: ziyaret.add((a, b)) kuyruk.append((a, b)) return say kucuk = [[1, 0, 0, 0, 1], [0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 1]] for satir in kucuk: print(" ", "".join("#" if v else "." for v in satir)) print(" 4 komsuluk:", bilesen(kucuk, 4), "bilesen") print(" 8 komsuluk:", bilesen(kucuk, 8), "bilesen") print() print("tohum 4 komsuluk toplam 8 komsuluk toplam farkli izgara/40") for tohum in (20260218, 20260219): K = izgara_dagarcik(tohum) d4 = [bilesen(g, 4) for g in K] d8 = [bilesen(g, 8) for g in K] farkli = sum(1 for a, b in zip(d4, d8) if a != b) print(f"{tohum} {sum(d4):17d} {sum(d8):17d} {farkli:16d}") ``` ``` #...# .#.#. ..#.. .#.#. #...# 4 komsuluk: 9 bilesen 8 komsuluk: 1 bilesen tohum 4 komsuluk toplam 8 komsuluk toplam farkli izgara/40 20260218 387 233 38 20260219 377 227 38 ``` Beş satırlık ızgarada dokuz hücre var ve hiçbiri kenardaş değil; hepsi köşegen üzerinde duruyor. Dört komşulukla **9 ayrı bileşen**, sekiz komşulukla **tek bir bileşen** çıkıyor. Aynı veri, aynı yordam, dokuz kat fark. Kırk ızgaralık dağarcıkta toplam bileşen sayısı **387'den 233'e** iniyor ve **38 ızgarada** iki tanım farklı yanıt veriyor. İkinci dağarcıkta sayılar 377 ve 227, farklı ızgara yine **38**; sonuç dağarcığa bağlı değildir. Bu ölçümün pratik sonucu şudur: **bir ızgara problemi okunurken sorulacak ilk soru komşuluğun tanımıdır.** Tanım problem metninde yazmıyorsa, kalıbın verdiği yanıtın doğruluğu sınanamaz — kâhin bile kurulamaz, çünkü kâhinin de aynı tanıma ihtiyacı vardır. Bu, konudaki tek ön koşuldur ki **veriye bakarak** saptanamaz. ## İşaretleme ve Gezinme Yanıtı Değil, Tutulanı Değiştirir Komşuluk tanımı sabitlendiğinde geriye iki uygulama kararı kalır: işaretleme kuyruğa eklerken mi çıkarırken mi yapılacak, ve gezinme enine mi derine mi olacak. İkisi de bileşen sayısını değiştirmez. Değiştirdikleri şey **aynı anda tutulan hücre sayısıdır**. **PK62.** Bu ölçüm daha büyük ızgarada yapılır: 10 ızgara, her biri 20×20, hücreler 100'de 60 olasılıkla dolu. Küçük ve seyrek ızgarada bu üç yordamın farkı çözünürlüğün altında kalır. **PK63.** Ölçülen şey, enine aramada **kuyruğun en geniş hâli**, derine aramada **özyineleme derinliğinin en büyük değeridir**. ```python from collections import deque def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def izgara_dagarcik(tohum=20260218, n=10, boy=20): r = uretec(tohum) return [[[1 if r(101) < 60 else 0 for _ in range(boy)] for _ in range(boy)] for _ in range(n)] YON4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) def enine(izgara, eklerken): """Isaretleme kuyruga EKLERKEN mi, kuyruktan CIKARIRKEN mi yapiliyor.""" n, m = len(izgara), len(izgara[0]) ziyaret, bilesen, adim, en_cok = set(), 0, 0, 0 for i in range(n): for j in range(m): if not izgara[i][j] or (i, j) in ziyaret: continue bilesen += 1 kuyruk = deque([(i, j)]) if eklerken: ziyaret.add((i, j)) while kuyruk: en_cok = max(en_cok, len(kuyruk)) x, y = kuyruk.popleft() adim += 1 if not eklerken: if (x, y) in ziyaret: continue ziyaret.add((x, y)) for dx, dy in YON4: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and izgara[a][b] \ and (a, b) not in ziyaret: if eklerken: ziyaret.add((a, b)) kuyruk.append((a, b)) return bilesen, adim, en_cok def derine(izgara): """Ozyinelemeli derine arama; en derin yigit boyu olculur.""" n, m = len(izgara), len(izgara[0]) ziyaret, bilesen, adim, en_derin = set(), 0, 0, 0 def gez(x, y, derinlik): nonlocal adim, en_derin adim += 1 en_derin = max(en_derin, derinlik) ziyaret.add((x, y)) for dx, dy in YON4: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and izgara[a][b] \ and (a, b) not in ziyaret: gez(a, b, derinlik + 1) for i in range(n): for j in range(m): if izgara[i][j] and (i, j) not in ziyaret: bilesen += 1 gez(i, j, 1) return bilesen, adim, en_derin K = izgara_dagarcik() temel = [enine(g, True) for g in K] print("dagarcik: 10 izgara x 20 x 20 | dolu hucre:", sum(sum(sum(s) for s in g) for g in K)) print("gezinme ayni bilesen adim en cok tutulan hucre") for ad, sonuc in (("enine, eklerken isaretle ", temel), ("enine, cikarirken isaretle", [enine(g, False) for g in K]), ("derine (ozyinelemeli) ", [derine(g) for g in K])): ayni = sum(1 for a, b in zip(sonuc, temel) if a[0] == b[0]) print(f"{ad} {ayni:12d} {sum(x[1] for x in sonuc):4d}" f" {max(x[2] for x in sonuc):20d}") ``` ``` dagarcik: 10 izgara x 20 x 20 | dolu hucre: 2378 gezinme ayni bilesen adim en cok tutulan hucre enine, eklerken isaretle 10 2378 18 enine, cikarirken isaretle 10 2887 24 derine (ozyinelemeli) 10 2378 103 ``` Üç satırın üçünde de bileşen sayısı aynı: on ızgaranın onunda aynı yanıt. Ayrılan girdi **sıfırdır** ve bu satırlar bir doğruluk ölçümü değildir. Ölçülen fark iki sütundadır. İşaretlemeyi kuyruktan çıkarırken yapmak adımı 2378'den **2887'ye**, en geniş kuyruğu 18'den **24'e** çıkarıyor: aynı hücre ziyaret edilmeden önce birden çok kez kuyruğa giriyor. Derine arama adım sayısında enine aramayla **birebir aynı** (2378), ama en derin yığıt **103** hücre tutuyor — enine aramanın en geniş kuyruğunun yaklaşık **beş buçuk katı**. Son sayı pratik bir sınırdır. Yoğun ve büyük bir ızgarada özyinelemeli derine arama, ızgara büyüklüğüyle orantılı bir yığıt derinliği ister; enine arama ise en geniş katmanla orantılı bir kuyruk ister. Hangisinin daha ucuz olduğu ızgaranın **biçimine** bağlıdır ve bu ayrım Veri Yapıları kursunun karşılaştırma tablosunda kurulmuştu; burada aynı ayrım sayıyla doğrulanmış oluyor. ## Üç Sayı | Ölçüt | Kâhin | Kalıp | Ayrılan girdi | |---|---|---|---| | Dört komşuluk, dört komşuluk | 12.768 adım | 723 adım | **0/40** | | Sekiz komşuluk, dört komşuluk | 12.768 adım | 723 adım | **38/40** | | Enine arama, 20×20 ızgara | — | 2378 adım / 18 hücre | **0/10** | | Derine arama, 20×20 ızgara | — | 2378 adım / 103 hücre | **0/10** | İlk iki satırda kalıbın adımı **birebir aynıdır** ve ayrılan girdi 0 ile 38 arasında değişir; son iki satırda ayrılan girdi aynıdır ve tutulan hücre sayısı beş buçuk kat değişir. İki tür karar, iki ayrı sütunda görünür — ve hiçbiri öbürünün sütununda iz bırakmaz. ## Özet - Izgara bir çizgedir: dolu hücreler düğüm, komşu hücre çiftleri kenardır; bağlı bileşen sayımı Veri Yapıları kursunun enine ve derine aramasıyla yapılır. - Kalıp, kâhinle aynı komşuluk tanımını kullandığında 40 ızgaranın 40'ında doğru; tanımlar ayrıldığında **38 ızgarada** ayrılıyor ve kalıbın adımı iki durumda da 723'tür. - Komşuluk tanımı verinin değil modelleyenin bir kararıdır; veriye bakarak saptanamaz ve tanım belirlenmeden kâhin bile kurulamaz. - Dokuz köşegen hücreden oluşan ızgarada dört komşuluk 9, sekiz komşuluk 1 bileşen veriyor; 40 ızgaralık dağarcıkta toplam 387'den 233'e iniyor. - İşaretlemeyi çıkarırken yapmak yanıtı değiştirmiyor ama adımı 2378'den 2887'ye, kuyruğu 18'den 24'e çıkarıyor; derine arama aynı adımda 103 hücrelik yığıt tutuyor. ## Sonraki Adım Bu konu sekiz kalıbı aynı çerçeveyle ölçtü: bir kâhin, bir kalıp ve ikisinin ayrıldığı girdi sayısı. Sekiz dersin sekizinde de ayrılmanın kaynağı kalıbın hatası değil, **kabul edilip denetlenmeyen bir ön koşuldu** — sıra, işaret, tek ardıl, sıralama anahtarı, değer aralığı, denge, sorunun tanımı ve komşuluk. Sonraki konu kalıplardan **adı olan problemlere** geçer: sırt çantası, gezgin satıcı, en uzun yol, vezir yerleşimi. Orada sorulacak soru değişir — bir kalıbın ön koşulunun bozulup bozulmadığı değil, bir problemin **neden zor** olduğu sorulur; ve kâhin, o zorluğun ölçüldüğü araç olarak kalır.