Gezgin Satıcı Problemi

Sırt çantasında kâhin altı eşyanın 64 alt kümesini taradı ve bu tarama ucuzdu. Aday çözüm sayısı eşya sayısının üstel bir işleviydi, ama üs tabanı ikiydi ve altı eşya için 64 küçük bir sayı kaldı. Gezgin satıcı probleminde aday sayısı alt küme değil sıralama sayısıdır ve o sayı çok daha hızlı büyür.

Problem şudur: şehirler ve aralarındaki uzaklıklar verilir; her şehre tam bir kez uğrayıp başlangıç şehrine dönen en kısa kapalı tur aranır. Bu ders iki soruyu ayrı ayrı yanıtlar. Birincisi ölçülebilir: yaklaşık bir çözüm kâhinden yüzde kaç sapıyor. İkincisi bu kursta yanıtlanmaz: bu problem neden zor. İkinci soru bir sınıflandırma sorusudur ve M01/K08 Hesaplama Kuramı kursuna aittir; burada yalnız sorunun kendisi kurulur.

• KP10. Şehir konumları ortak tanımın üretecinden gelir: 30’a 30’luk bir ızgarada rastgele nokta. Tohum 20260218, ikinci dağarcık 20260219.
• KP11. Her dağarcıkta 20 örnek, örnek başına 8 şehir. Şehir sayısı kâhin koşturulabilsin diye küçük tutulur; büyük şehir sayısı sayılarak anlatılır.
• KP12. Uzaklık tam sayıdır: koordinat farklarının karelerinin toplamının tam sayı karekökü. Kayan noktalı sayı kullanılmaz, böylece iki tur eşitliği kesin olarak sınanır.
• KP13. Kâhin tam sayımdır: sıfırıncı şehir sabitlenir, kalan yedi şehrin bütün sıraları denenir; her turun tersi aynı tur olduğu için yarısı elenir, geriye 2520 tur kalır.
• KP14. Ölçü adımdır. Bir adım, bir kenar uzunluğunun hesaplanmasıdır.
• KP15. Sapma yüzde olarak yazılır: kalıbın turu eksi en iyi tur, bölü en iyi tur. Ortalama sapmanın yanına en kötü sapma da konur; ortalama tek başına yanıltıcıdır.
• KP16. İki-değişim iyileştirmesi, turdaki iki kenarı kaldırıp aradaki parçayı ters çevirerek yeniden bağlar. Hiçbir iyileştirme kalmayana kadar sürer.
• KP17. Büyük şehir sayıları koşturulmaz, sayılır. Tam sayım tablosu çarpanların hesaplanmasıyla üretilir, hiçbir tur gerçekten taranmaz.
• KP18. Zorluğun adı bu derste yazılmaz. Karmaşıklık sınıfları, indirgeme ve yaklaşım oranı kavramları M01/K08’e aittir.
• KP19. Sapmanın şehir sayısıyla nasıl değiştiği ayrıca süpürülür. Her şehir sayısı için ayrı bir dağarcık üretilir; satırlar birbirinin genişletilmişi değildir.

Kâhin ve İki Yaklaşık Çözüm

En yakın komşu yordamı sezgiyi doğrudan izler: bulunulan şehirden en yakın uğranmamış şehre git, bu bitince başa dön. İki-değişim ise elde edilen turu alıp yerel olarak düzeltir; turda kesişen iki kenar varsa onları kaldırıp aradaki parçayı ters çevirmek turu kısaltır.

İkisinin de doğruluğu iddia edilmez. Kâhin her örnekte en iyi turu tam sayımla bulur ve iki kalıp ona göre ölçülür.

from itertools import permutations
from math import isqrt

TOHUM = 20260218


def uretec(tohum):
    d = tohum

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


def sehirler(tohum=TOHUM, ornek=20, n=8):
    """Ortak tanimin ureteci; her ornek n sehrin (x, y) konumu."""
    r = uretec(tohum)
    return [[(r(30), r(30)) for _ in range(n)] for _ in range(ornek)]


def uzaklik(p, q):
    return isqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)


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

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


def kahin_tam(k, s):
    """Sifirinci sehir sabit; kalan sehirlerin butun siralari denenir."""
    en = None
    for p in permutations(range(1, len(k))):
        if p[0] > p[-1]:
            continue
        tur, onceki = 0, 0
        for i in p:
            s.say()
            tur += uzaklik(k[onceki], k[i])
            onceki = i
        tur += uzaklik(k[onceki], k[0])
        if en is None or tur < en:
            en = tur
    return en


def en_yakin_komsu(k, s):
    kalan, yol, simdi, tur = set(range(1, len(k))), [0], 0, 0
    while kalan:
        en_i, en_d = None, None
        for i in kalan:
            s.say()
            d = uzaklik(k[simdi], k[i])
            if en_d is None or d < en_d:
                en_i, en_d = i, d
        kalan.remove(en_i)
        yol.append(en_i)
        tur, simdi = tur + en_d, en_i
    return tur + uzaklik(k[simdi], k[0]), yol


def iki_degisim(k, yol, s):
    n = len(yol)
    tur = sum(uzaklik(k[yol[i]], k[yol[(i + 1) % n]]) for i in range(n))
    iyilesti = True
    while iyilesti:
        iyilesti = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                s.say()
                a, b, c, d = yol[i - 1], yol[i], yol[j], yol[(j + 1) % n]
                fark = (uzaklik(k[a], k[c]) + uzaklik(k[b], k[d])
                        - uzaklik(k[a], k[b]) - uzaklik(k[c], k[d]))
                if fark < 0:
                    yol[i:j + 1] = reversed(yol[i:j + 1])
                    tur, iyilesti = tur + fark, True
    return tur


for tohum in (20260218, 20260219):
    ha, top = 0, {"en yakin komsu": [0, 0, 0.0, 0.0], "iki degisim   ": [0, 0, 0.0, 0.0]}
    for k in sehirler(tohum):
        sh = Sayac()
        eniyi = kahin_tam(k, sh)
        ha += sh.adim
        s1, s2 = Sayac(), Sayac()
        t1, yol = en_yakin_komsu(k, s1)
        t2 = iki_degisim(k, list(yol), s2)
        for ad, t, s in (("en yakin komsu", t1, s1), ("iki degisim   ", t2, s2)):
            r = top[ad]
            r[0] += 0 if t == eniyi else 1
            r[1] += s.adim
            sap = 100.0 * (t - eniyi) / eniyi
            r[2], r[3] = r[2] + sap, max(r[3], sap)
    print("tohum", tohum, "| kahin adim", ha)
    for ad, r in top.items():
        print(f"  {ad} ayrilan {r[0]:2d}/20 | kalip adim {r[1]:4d}"
              f" | ortalama sapma yuzde {round(r[2] / 20, 2)}"
              f" | en kotu yuzde {round(r[3], 2)}")

tohum 20260218 | kahin adim 352800
  en yakin komsu ayrilan 17/20 | kalip adim  560 | ortalama sapma yuzde 9.3 | en kotu yuzde 33.33
  iki degisim    ayrilan  2/20 | kalip adim  819 | ortalama sapma yuzde 0.49 | en kotu yuzde 7.59
tohum 20260219 | kahin adim 352800
  en yakin komsu ayrilan 18/20 | kalip adim  560 | ortalama sapma yuzde 10.65 | en kotu yuzde 26.67
  iki degisim    ayrilan  6/20 | kalip adim  924 | ortalama sapma yuzde 1.13 | en kotu yuzde 6.59

Sapmanın Okunması

Üç sayı yan yana: kâhin 352.800 adım, en yakın komşu 560 adım, ayrılan örnek 17. Kalıp 630 kat az adım harcıyor ve 20 örneğin 17’sinde en iyi turu bulamıyor. Ama ayrılan örnek sayısı burada tek başına yeterli değildir, çünkü soru “doğru mu” değil, “ne kadar uzak” sorusudur. Ortalama sapma yüzde 9,3 ve en kötü sapma yüzde 33,33. Ortalamanın tek başına yazılması, üçte bir uzunluğunda bir turun varlığını gizlerdi.

İki-değişim aynı turu alıp yerel düzeltmeler yapıyor. Ayrılan örnek 17’den 2’ye, ortalama sapma yüzde 9,3’ten yüzde 0,49’a, en kötü sapma yüzde 33,33’ten yüzde 7,59’a iniyor. Bunun bedeli 560 adım yerine 819 adım, yani yüzde 46 daha çok iş. Aynı yordam hâlâ kâhin değildir: iki örnekte en iyiyi bulamıyor ve bulamadığını kendisi bilemez.

İkinci dağarcık zorunludur. 20260219 tohumunda en yakın komşu 18 örnekte ayrılıyor, ortalama sapma yüzde 10,65; iki-değişim 6 örnekte ayrılıyor, ortalama sapma yüzde 1,13. En yakın komşunun sonucu iki dağarcıkta da aynı: neredeyse her örnekte en iyiyi kaçırıyor. İki-değişimin ayrılan örneği 2’den 6’ya çıkıyor ve bu fark çözünürlüğün üstündedir; yani iki-değişimin kaç örnekte en iyiyi bulacağı dağarcığa bağlıdır ve tek bir dağarcıktan genellenemez. Ortalama sapmanın büyüklük düzeni ise değişmiyor: yüzde bir mertebesinde kalıyor.

Kâhinin Nerede Bittiği

Kâhinin sekiz şehirde 352.800 adım harcaması sorun değildir. Sorun, bu sayının şehir sayısıyla nasıl büyüdüğüdür. Tur sayısı, sıfırıncı şehir sabitlendikten sonra kalan şehirlerin bütün sıralamalarının yarısıdır. Bu sayı koşturularak değil sayılarak gösterilir.

from math import factorial


def bic(x):
    return f"{x:,}".replace(",", ".")


print(" n | tur sayisi | kahin adimi | en yakin komsu adimi | oran")
for n in (8, 10, 12, 14, 16, 18):
    tur = factorial(n - 1) // 2
    kahin = tur * (n - 1)
    kalip = n * (n - 1) // 2
    print(f"{n:2d} | {bic(tur):>22s} | {bic(kahin):>25s} |"
          f" {kalip:4d} | {bic(kahin // kalip)}")

 n | tur sayisi | kahin adimi | en yakin komsu adimi | oran
 8 |                  2.520 |                    17.640 |   28 | 630
10 |                181.440 |                 1.632.960 |   45 | 36.288
12 |             19.958.400 |               219.542.400 |   66 | 3.326.400
14 |          3.113.510.400 |            40.475.635.200 |   91 | 444.787.200
16 |        653.837.184.000 |         9.807.557.760.000 |  120 | 81.729.648.000
18 |    177.843.714.048.000 |     3.023.343.138.816.000 |  153 | 19.760.412.672.000

Sekiz şehirden on sekiz şehre çıkıldığında kâhinin adımı 17.640’tan 3.023.343.138.816.000’e çıkıyor; en yakın komşunun adımı ise 28’den 153’e. Oran 630’dan on dokuz trilyonun üzerine tırmanıyor. Bu tablo bir hız iddiası değildir; kâhinin nerede koşturulamaz hale geldiğinin sayımıdır.

Buradan çıkan sonuç, kursun üçüncü iddiasının en sert biçimidir. Kaba kuvvet bir kâhindir, ama her ölçekte kâhin olamaz. Sekiz şehirde ölçülen yüzde 9,3’lük sapma on sekiz şehirde ölçülemez, çünkü karşılaştırılacak en iyi tur bilinmez. Yaklaşık bir çözümün büyük girdideki kalitesi hakkında yazılan her cümle, ya küçük girdide ölçülmüş bir sapmadan genelleme yapar ya da bir alt sınır kullanır. İkisi de kanıt değildir ve bu ders ikisini de kanıt diye sunmaz.

Sapma Şehir Sayısıyla Ne Yapıyor

Bir önceki bölümün son cümlesi bir soru bırakıyor: küçük girdide ölçülen sapma büyük girdi için ne söyler. Bu soruya tam olarak yanıt verilemez, ama sapmanın kâhinin koşturulabildiği aralıkta hangi yöne gittiği ölçülebilir. Şehir sayısı beşten dokuza kadar süpürülür.

from itertools import permutations
from math import isqrt

TOHUM = 20260218


def uretec(tohum):
    d = tohum

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


def sehirler(tohum=TOHUM, ornek=20, n=8):
    r = uretec(tohum)
    return [[(r(30), r(30)) for _ in range(n)] for _ in range(ornek)]


def uzaklik(p, q):
    return isqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)


def kahin_tam(k):
    en = None
    for p in permutations(range(1, len(k))):
        if p[0] > p[-1]:
            continue
        tur, onceki = 0, 0
        for i in p:
            tur += uzaklik(k[onceki], k[i])
            onceki = i
        tur += uzaklik(k[onceki], k[0])
        if en is None or tur < en:
            en = tur
    return en


def en_yakin_komsu(k):
    kalan, simdi, tur = set(range(1, len(k))), 0, 0
    while kalan:
        en_i = min(kalan, key=lambda i: uzaklik(k[simdi], k[i]))
        tur += uzaklik(k[simdi], k[en_i])
        kalan.remove(en_i)
        simdi = en_i
    return tur + uzaklik(k[simdi], k[0])


print(" n | ayrilan / 20 | ortalama sapma | en kotu sapma")
for n in (5, 6, 7, 8, 9):
    ay, top, kot = 0, 0.0, 0.0
    for k in sehirler(n=n):
        e, t = kahin_tam(k), en_yakin_komsu(k)
        if t != e:
            ay += 1
        sap = 100.0 * (t - e) / e
        top, kot = top + sap, max(kot, sap)
    print(f"{n:2d} | {ay:11d}  | yuzde {round(top / 20, 2):5} "
          f"   | yuzde {round(kot, 2)}")

 n | ayrilan / 20 | ortalama sapma | en kotu sapma
 5 |          12  | yuzde  5.03    | yuzde 16.67
 6 |          14  | yuzde  6.29    | yuzde 17.57
 7 |          15  | yuzde  7.17    | yuzde 17.86
 8 |          17  | yuzde   9.3    | yuzde 33.33
 9 |          14  | yuzde  9.77    | yuzde 22.99

Ortalama sapma beş şehirde yüzde 5,03, dokuz şehirde yüzde 9,77. Beş satırın beşinde de artıyor ve yaklaşık iki katına çıkıyor. Ayrılan örnek sayısı ise düzenli değil: 12, 14, 15, 17, sonra 14. Bu düzensizlik beklenir, çünkü her satır kendi şehir sayısına göre üretilmiş ayrı bir dağarcıktır; dokuz şehirlik örnekler sekiz şehirlik örneklerin genişletilmişi değildir.

Tablodan çıkarılabilecek tek şey yönün kendisidir: sapma şehir sayısıyla artıyor. Bu, sekiz şehirde ölçülen yüzde 9,3’ün büyük girdiler için bir alt tahmin olduğunu düşündürür. Düşündürür — kanıtlamaz. Beşten dokuza uzanan beş nokta üzerinden on sekiz şehir hakkında bir şey söylemek, ölçülmüş bir aralığın dışına çıkmaktır ve bu ders o çıkışı yapmaz.

Neden Zor Sorusu Nereye Ait

Buraya kadar ölçülen her şey somuttur: adım, sapma, ayrılan örnek. Ölçülmeyen bir şey kaldı. Tam sayımdan köklü biçimde daha ucuz bir yordam var mı, yoksa bu problemin doğasında mı bir zorluk var.

Bu soru bu kursta yanıtlanmaz ve yanıtlanmaya çalışılmaz. Sorunun yanıtı problemleri zorluk derecesine göre sınıflandırmayı, bir problemi bir başkasına çevirmeyi ve yaklaşık çözümün en iyiden ne kadar sapabileceğine dair kanıtlanmış sınırlar kurmayı gerektirir. Bu araçların tamamı M01/K08 Hesaplama Kuramı kursuna aittir. Burada yapılan tek şey soruyu ölçülebilir parçasından ayırmaktır: sapma ölçülür, zorluğun adı ölçülmez.

Bu ayrımın pratik bir karşılığı vardır. Bir problemin zor olduğunu bilmek, yaklaşık çözümün sapmasını bilmenin yerine geçmez. Sapma ölçülmeden “zaten zor bir problem” demek, kalıbı kâhinsiz bırakmaktır.

Özet

• Gezgin satıcı probleminde aday çözüm sayısı alt küme değil sıralama sayısıdır; sekiz şehirde 2520 tur, on sekiz şehirde 177.843.714.048.000 tur.
• Kâhin 20 örnek için 352.800 adım harcıyor; en yakın komşu 560 adımda bitiriyor ama 20 örneğin 17’sinde en iyi turu kaçırıyor.
• Sapma ortalama yüzde 9,3, en kötü yüzde 33,33; ortalamanın tek başına yazılması en kötü durumu gizler.
• İki-değişim ayrılan örneği 2’ye ve ortalama sapmayı yüzde 0,49’a indiriyor, bedeli 560 yerine 819 adım; ikinci dağarcıkta ayrılan örnek 6’ya çıktığı için bu sayı dağarcığa bağlıdır.
• Kâhin her ölçekte koşturulamaz; büyük girdide ölçülen bir sapma yoktur, yalnız küçük girdiden yapılmış bir genelleme vardır.
• Problemin neden zor olduğu sorusu M01/K08 Hesaplama Kuramı kursuna aittir ve burada yanıtlanmaz.

Sonraki Adım

Gezgin satıcıda kâhin tam sayımdı ve kalıp yaklaşık bir turdu. Sonraki ders daha rahatsız edici bir durumu ele alır: kalıbın kanıtlanmış bir yordam olduğu, ama uygulandığı problemin değiştiği durum. En kısa yol algoritmaları M01/K04 Algoritmalar kursunda kanıtlanmıştı; aynı yordam en uzun yola çevrildiğinde kaç çizgede yanlış yanıt veriyor, ve bu yanlışın kaynağı hangi varsayımın düşmesi.