--- title: 'Gezgin Satıcı Problemi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/gezgin-satici-problemi' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # Gezgin Satıcı Problemi Sekiz şehirde tam sayımla alınan en iyi turun kâhin yapılması ve iki yaklaşık çözümün ondan yüzde kaç saptığının ölçülmesi: en yakın komşu 20 örneğin 17'sinde kâhinden ayrılıyor, ortalama sapma yüzde 9,3 ve en kötüsü yüzde 33,33; iki-değişim iyileştirmesi ayrılan örneği 2'ye, ortalama sapmayı yüzde 0,49'a indiriyor ve bunu 819 adımda yapıyor. Kâhin aynı 20 örnek için 352.800 adım harcıyor. Arama alanının büyümesi koşturularak değil sayılarak gösteriliyor; on sekiz şehirde tur sayısı 177.843.714.048.000. Neden zor sorusu Hesaplama Kuramı kursuna havale ediliyor. 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. ```python 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. ```python 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. ```python 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.