At Turu ve Labirent Problemleri

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.

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.

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.

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.