Hamilton Yolları

At turunda son satır bir ayrım açtı: dörde dörtlük tahtada tur yoktu ve iki sıralama da tam olarak aynı sayıda düğüm gezdi. Evet yanıtı ucuzlayabiliyordu, hayır yanıtı ucuzlamıyordu. Bu ders o ayrımı konunun ana sorusu yapar.

Hamilton yolu, bir çizgenin bütün düğümlerinden tam bir kez geçen yoldur. At turu bunun özel bir halidir: kareler düğüm, at hamleleri kenardır. Buradaki soru artık “en iyi hangisi” değil, “var mı” sorusudur. Bu, bir karar problemidir ve yanıtı tek bir sözcüktür. Yanında iki soru daha durur: arama problemi bir yol ister, sayma problemi kaç tane olduğunu ister. Üç soru aynı girdiye bakar ve üçünün maliyeti ayrı ayrı ölçülür.

• KP50. Çizgeler ortak tanımın üretecinden gelir: 8 düğüm, her düğüm ikilisi yüzde 38 payla bağlı, yönsüz. Tohum 20260218, ikinci dağarcık 20260219, dağarcık başına 40 çizge.
• KP51. Karar problemi: bütün düğümlerden geçen bir yol var mı. Yordam ilk yolu bulunca durur; yol yoksa arama alanının tamamını tarar.
• KP52. Arama problemi: böyle bir yol varsa hangisi. Bu derste karar yordamı yolu zaten üretiyor; arama ile kararın adımı bu problemde aynıdır ve bu ölçülmüş bir sonuçtur, genel bir kural değildir.
• KP53. Sayma problemi: kaç tane var. Yordam hiç durmaz, uzayın tamamını tarar. Her yol iki uçtan da gezildiği için sayım her yolu iki kez içerir; ölçülen şey adım, sayının kendisi değildir.
• KP54. Doğrulama: verilen bir aday yolun gerçekten Hamilton yolu olup olmadığı sınanır. Bir adım, ardışık iki düğümün komşuluk denetimidir.
• KP55. Kâhin sayma yordamıdır: uzayı tamamen tarar, bu yüzden yanıtı tanım gereği doğrudur. Kararın yanıtı her çizgede kâhinin sayısıyla karşılaştırılır.
• KP56. Ölçü adımdır; bir adım, arama ağacında bir düğüm ziyaretidir.
• KP57. Evet çizgeleri ile hayır çizgeleri ayrı toplanır. İkisini tek ortalamada birleştirmek dersin ölçtüğü farkı yok ederdi.
• KP58. Karmaşıklık sınıflarının adları bu derste yazılmaz. Doğrulama ile aramanın farkının nasıl adlandırıldığı M01/K08 Hesaplama Kuramı kursuna aittir.
• KP59. Ucuz sınama yalnız gerek koşulları denetler. Yanlış sayısı kâhinle ölçülür; sıfır çıkması varsayılmaz, sayılır.

Üç Soru, Bir Girdi

Aşağıdaki blok her çizgede kararı ve saymayı ayrı ayrı koşturur, bulunan yolu doğrular ve sonuçları evet ile hayır çizgeleri için ayrı toplar.

TOHUM = 20260218
N = 8


def uretec(tohum):
    d = tohum

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


def cizgeler(tohum=TOHUM, ornek=40, pay=38, n=N):
    """Yonsuz cizge: her ikili yuzde pay olasilikla bagli."""
    r = uretec(tohum)
    kume = []
    for _ in range(ornek):
        komsu = {i: set() for i in range(n)}
        for i in range(n):
            for j in range(i + 1, n):
                if r(100) < pay:
                    komsu[i].add(j)
                    komsu[j].add(i)
        kume.append(komsu)
    return kume


class Sayac:
    def __init__(self):
        self.adim = 0

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


def ara(komsu, s, dur, n=N):
    """dur=True: ilk Hamilton yolunda durur. dur=False: hepsini sayar."""
    bulunan, sayi = [], 0

    def gez(v, yol):
        nonlocal sayi
        s.say()
        if len(yol) == n:
            sayi += 1
            if not bulunan:
                bulunan.append(tuple(yol))
            return True
        for k in sorted(komsu[v]):
            if k not in yol:
                yol.append(k)
                bitti = gez(k, yol)
                yol.pop()
                if bitti and dur:
                    return True
        return False

    for bas in range(n):
        if gez(bas, [bas]) and dur:
            break
    return (bulunan[0] if bulunan else None), sayi


def dogrula(komsu, yol, n=N):
    """Hakem: aday yol n dugum mu, ardisik ikililer komsu mu."""
    adim = 0
    if yol is None or len(set(yol)) != n:
        return False, adim
    for a, b in zip(yol, yol[1:]):
        adim += 1
        if b not in komsu[a]:
            return False, adim
    return True, adim


for tohum in (20260218, 20260219):
    evet = {"n": 0, "karar": 0, "sayma": 0, "dogrulama": 0}
    hayir = {"n": 0, "karar": 0, "sayma": 0}
    esit = 0
    for komsu in cizgeler(tohum):
        s1, s2 = Sayac(), Sayac()
        yol, _ = ara(komsu, s1, True)
        _, kac = ara(komsu, s2, False)
        if yol is not None:
            ok, d = dogrula(komsu, yol)
            evet["n"] += 1
            evet["karar"] += s1.adim
            evet["sayma"] += s2.adim
            evet["dogrulama"] += d
        else:
            hayir["n"] += 1
            hayir["karar"] += s1.adim
            hayir["sayma"] += s2.adim
            if s1.adim == s2.adim:
                esit += 1
    print("tohum", tohum)
    print("  evet ", evet, "oran", round(evet["sayma"] / evet["karar"], 2))
    print("  hayir", hayir, "karar=sayma olan cizge:", esit, "/", hayir["n"])

tohum 20260218
  evet  {'n': 25, 'karar': 1526, 'sayma': 29270, 'dogrulama': 175} oran 19.18
  hayir {'n': 15, 'karar': 2538, 'sayma': 2538} karar=sayma olan cizge: 15 / 15
tohum 20260219
  evet  {'n': 23, 'karar': 915, 'sayma': 26792, 'dogrulama': 161} oran 29.28
  hayir {'n': 17, 'karar': 4390, 'sayma': 4390} karar=sayma olan cizge: 17 / 17

Hayır Yanıtı Neden İndirim Kabul Etmiyor

İlk dağarcıkta 40 çizgenin 25’inde yol var, 15’inde yok. Evet çizgelerinde karar toplam 1526 adım, sayma 29.270 adım harcıyor; oran 19,18. Karar yordamı ilk yolu bulur bulmaz duruyor ve uzayın geri kalanına hiç girmiyor.

Hayır çizgelerinde iki sayı birebir aynı: 2538 ve 2538. Üstelik bu eşitlik toplamda değil, 15 çizgenin 15’inde tek tek sağlanıyor. Bunun nedeni yordamsal değil mantıksaldır. Karar yordamı “yok” diyebilmek için tek bir dalın da yol vermediğini görmek zorundadır; görmediği bir dal kalırsa yanıtı bir tahmindir. Yol yokken erken durma noktası hiç oluşmaz, bu yüzden karar yordamı tam olarak sayma yordamının gezdiği ağacı gezer.

İkinci dağarcık aynı yapıyı veriyor: 23 evet, 17 hayır, oran 29,28, ve hayır çizgelerinin 17’sinde 17’si için karar adımı sayma adımına eşit. Evet çizgelerindeki oran 19,18’den 29,28’e çıkıyor, yani oranın büyüklüğü dağarcığa bağlıdır; ama hayır çizgelerindeki tam eşitlik iki dağarcıkta da istisnasız duruyor. Biri ölçülen bir değer, öteki yordamın yapısından gelen bir sonuçtur, ve ikisi aynı cümlede yazılmaz.

Buradan bir önceki dersin at turu satırı yeniden okunabilir. Dörde dörtlük tahtada iki sıralamanın da 29.976 düğüm gezmesi bir rastlantı değildi: yanıt hayır olduğu için erken durma noktası yoktu ve sıralama ancak erken durmayı öne çekerek kazandırabilirdi.

Tek Yöne Çalışan Ucuz Sınama

Hayır yanıtının pahalı olması, her hayır yanıtının pahalı olduğu anlamına gelmiyor. Bazı çizgelerde yolun olmadığı aramaya hiç girmeden görülebilir: çizge parçalıysa hiçbir yol bütün düğümlere ulaşamaz, ve ikiden çok düğümün yalnız tek komşusu varsa bunların hepsi yolun ucunda olamaz. Bunlar gerek koşullardır: sağlanmazsa yol yoktur, sağlanırsa hiçbir şey söylemezler.

from collections import deque

TOHUM, N = 20260218, 8


def uretec(tohum):
    d = tohum

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


def cizgeler(tohum=TOHUM, ornek=40, pay=38, n=N):
    r = uretec(tohum)
    kume = []
    for _ in range(ornek):
        komsu = {i: set() for i in range(n)}
        for i in range(n):
            for j in range(i + 1, n):
                if r(100) < pay:
                    komsu[i].add(j)
                    komsu[j].add(i)
        kume.append(komsu)
    return kume


class Sayac:
    def __init__(self):
        self.adim = 0

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


def ucuz_sinama(komsu, s, n=N):
    """Gerek kosullari sinar. 'yok' diyebilir, 'var' diyemez."""
    kuyruk, gorulen = deque([0]), {0}
    while kuyruk:
        v = kuyruk.popleft()
        for k in komsu[v]:
            s.say()
            if k not in gorulen:
                gorulen.add(k)
                kuyruk.append(k)
    if len(gorulen) < n:
        return "yok"
    tek = 0
    for v in range(n):
        s.say()
        if len(komsu[v]) <= 1:
            tek += 1
    return "yok" if tek > 2 else "bilinmiyor"


def karar(komsu, s, n=N):
    def gez(v, yol):
        s.say()
        if len(yol) == n:
            return True
        for k in sorted(komsu[v]):
            if k not in yol:
                yol.append(k)
                if gez(k, yol):
                    return True
                yol.pop()
        return False
    return any(gez(bas, [bas]) for bas in range(n))


for tohum in (20260218, 20260219):
    ucuz_yok, ucuz_adim, yanlis = 0, 0, 0
    kalan_hayir, kalan_adim = 0, 0
    for komsu in cizgeler(tohum):
        s1, s2 = Sayac(), Sayac()
        y = ucuz_sinama(komsu, s1)
        var = karar(komsu, s2)
        ucuz_adim += s1.adim
        if y == "yok":
            ucuz_yok += 1
            if var:
                yanlis += 1
        elif not var:
            kalan_hayir += 1
            kalan_adim += s2.adim
    print("tohum", tohum, "| ucuz sinama 'yok' dedigi:", ucuz_yok,
          "| yanlis:", yanlis, "| ucuz toplam adim:", ucuz_adim)
    print("   ucuzun cozemedigi hayir cizgesi:", kalan_hayir,
          "| tam tarama adimi:", kalan_adim)

tohum 20260218 | ucuz sinama 'yok' dedigi: 11 | yanlis: 0 | ucuz toplam adim: 1092
   ucuzun cozemedigi hayir cizgesi: 4 | tam tarama adimi: 676
tohum 20260219 | ucuz sinama 'yok' dedigi: 13 | yanlis: 0 | ucuz toplam adim: 1102
   ucuzun cozemedigi hayir cizgesi: 4 | tam tarama adimi: 1638

İlk dağarcıkta 15 hayır çizgesinin 11’i ucuz sınamayla çözülüyor ve yanlış sayısı 0: sınama, yolu olan hiçbir çizgeye “yok” demiyor. Geriye 4 çizge kalıyor ve onlar için tam tarama kaçınılmaz, 676 adım. İkinci dağarcıkta 17 hayır çizgesinin 13’ü çözülüyor, yine 0 yanlış, yine 4 çizge kalıyor, bu kez 1638 adıma.

Sınamanın kırk çizgenin tamamı için harcadığı 1092 adım, hayır çizgelerinde tam taramanın harcadığı 2538 adımın altındadır. Ama tasarrufun tamamı tek yönlüdür. Sınama hiçbir çizgede “var” diyemez; “bilinmiyor” dediği 29 çizgenin 25’inde yol vardır, 4’ünde yoktur ve bu ikisini ayırmak için yine tam tarama gerekir. Ucuz kanıt her zaman bir yöne çalışır, ve hangi yöne çalıştığı yazılmadan sayısı okunamaz.

Aramak ile Doğrulamak

Dördüncü sayı doğrulamadır. Evet çizgelerinde toplam 175 adım, yani çizge başına 7 adım: sekiz düğümlü bir yolda yedi ardışık ikili. Aynı çizgelerde yolu bulmak ortalama 61 adım harcıyor, yani doğrulamanın 8,7 katı.

Bu iki sayı arasındaki fark, bu ders için tek bir çizgede küçüktür, ama iki sayının ölçekle ne yaptığı aynı değildir. Doğrulama, düğüm sayısı eksi bir adımdır ve düğüm sayısıyla düz büyür. Aramanın adımı ise gezilen ağacın büyüklüğüne bağlıdır. Aşağıdaki blok düğüm sayısını süpürüp iki büyümeyi yan yana koyar.

TOHUM = 20260218


def uretec(tohum):
    d = tohum

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


def cizgeler(n, pay, tohum=TOHUM, ornek=20):
    r = uretec(tohum)
    kume = []
    for _ in range(ornek):
        komsu = {i: set() for i in range(n)}
        for i in range(n):
            for j in range(i + 1, n):
                if r(100) < pay:
                    komsu[i].add(j)
                    komsu[j].add(i)
        kume.append(komsu)
    return kume


class Sayac:
    def __init__(self):
        self.adim = 0

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


def karar(komsu, n, s):
    """Ilk Hamilton yolunda durur; yol yoksa uzayin tamami taranir."""
    bulunan = []

    def gez(v, yol):
        s.say()
        if len(yol) == n:
            bulunan.append(tuple(yol))
            return True
        for k in sorted(komsu[v]):
            if k not in yol:
                yol.append(k)
                bitti = gez(k, yol)
                yol.pop()
                if bitti:
                    return True
        return False

    for bas in range(n):
        if gez(bas, [bas]):
            return bulunan[0]
    return None


print(" n | evet | evet ortalama adim | hayir ortalama adim | dogrulama adimi")
for n, pay in ((6, 30), (8, 30), (10, 30), (12, 30)):
    e = h = ea = ha = 0
    for komsu in cizgeler(n, pay):
        s = Sayac()
        y = karar(komsu, n, s)
        if y is None:
            h, ha = h + 1, ha + s.adim
        else:
            e, ea = e + 1, ea + s.adim
    print(f"{n:2d} | {e:4d} | {(ea // e if e else 0):18d} |"
          f" {(ha // h if h else 0):19d} | {n - 1:15d}")

 n | evet | evet ortalama adim | hayir ortalama adim | dogrulama adimi
 6 |    2 |                  8 |                  23 |               5
 8 |    6 |                121 |                  92 |               7
10 |    9 |                164 |                 757 |               9
12 |   10 |               1054 |               11601 |              11

Üç sütun üç ayrı büyüme gösteriyor. Doğrulama 5, 7, 9, 11: düğüm sayısıyla birlikte birer birer artıyor. Evet çizgelerinde karar 8, 121, 164, 1054. Hayır çizgelerinde karar 23, 92, 757, 11.601; altı düğümden on iki düğüme çıkarken beş yüz kattan fazla büyüyor. Sekiz düğümlük satırda hayır ortalaması evet ortalamasının altında kalıyor; bu tek satırlık ters yön, o dağarcıkta hayır çizgelerinin seyrek olmasından gelir ve genellenmez.

Ölçülen şey şu: bir yanıtın doğrulanması ile bulunması aynı büyüklükte değildir, ve aradaki açıklık düğüm sayısıyla açılır. On iki düğümde bir aday yolu sınamak 11 adımdır; böyle bir yolun olmadığını göstermek ortalama 11.601 adımdır. Aynı çizge, aynı soru, bin kat fark.

Adlandırma Nereye Ait

Buraya kadar dört sayı ölçüldü: karar, arama, sayma, doğrulama. Ölçülmeyen bir şey kaldı ve bilerek bırakıldı. Doğrulaması ucuz olup bulunması pahalı görünen problemlerin ortak bir adı vardır; bu problemlerin birbirine çevrilmesinin bir yordamı, ve “pahalı görünüyor” ile “pahalıdır” arasındaki farkın bir kuramı vardır.

Bunların hiçbiri bu kursta kurulmaz. Gezgin satıcı dersinde “neden zor” sorusu M01/K08 Hesaplama Kuramı kursuna havale edilmişti; buradaki adlandırma sorusu da aynı yere gider. Bu kursun yaptığı, o kursun üzerine konuşacağı farkı ölçüp masaya koymaktır: 11 adıma karşı 11.601 adım, ve bunun bir gözlem olduğu, bir kanıt olmadığı.

Bu ayrım işe yarar bir alışkanlık bırakır. Bir problemi zor diye adlandırmadan önce, o problemin hangi sorusunun pahalı olduğu yazılmalıdır. Aynı çizge için karar 1526 adım, sayma 29.270 adım, doğrulama 175 adım harcadı. “Hamilton yolu pahalıdır” cümlesi bu üç sayıdan hangisini kastettiğini söylemeden bir şey anlatmaz.

Özet

• Bir varlık sorusu karar problemi olarak kurulur; yanında arama ve sayma problemleri durur ve üçünün maliyeti aynı girdide ayrı ayrı ölçülür.
• Yol bulunan 25 çizgede karar 1526, sayma 29.270 adım harcıyor; oran 19,18 ve ikinci dağarcıkta 29,28, yani oranın büyüklüğü dağarcığa bağlıdır.
• Yol bulunmayan çizgelerin hepsinde karar adımı sayma adımına tam olarak eşit: ilk dağarcıkta 15’te 15, ikincisinde 17’de 17. Hayır yanıtı erken durma noktası bırakmaz.
• Doğrulama çizge başına 7 adım, arama ortalama 61 adım; düğüm sayısı süpürüldüğünde doğrulama birer birer artarken hayır yanıtının bedeli 23’ten 11.601’e çıkıyor.
• Ölçülen bu fark bir gözlemdir; adlandırılması ve kanıtlanması M01/K08 Hesaplama Kuramı kursuna aittir ve bu derste yapılmaz.

Sonraki Adım

Klasik Problemler konusu altı problemde aynı yordamı izledi: kâhini kur, kalıbı ölç, ayrılan girdiyi say. Sonraki konu bu yordamı problemden bağımsız hale getirir. Alıştırma Disiplini, bir problemin kısıtlarından hangi kalıbın adım bütçesine sığdığını çıkarmayı ve bir çözümü kâhinle karşılaştırmayı bir alışkanlığa dönüştürür. İlk soru şudur: girdi büyüklüğü verildiğinde hangi kalıbın bütçeye sığdığı, tahmin edilmeden sayılarak nasıl bulunur.