--- title: 'En Uzun Yol Problemi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/en-uzun-yol-problemi' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # En Uzun Yol Problemi En kısa yol gevşetmesinin en uzun yola çevrilmesi ve iki çizge ailesinde ölçülmesi: çevrimsiz çizgelerde 40 girdinin 40'ında kâhinle aynı yanıt, çevrimli çizgelerde 40 girdinin 38'inde ayrılma ve en büyük fazla tahmin 228 ağırlık birimi; ikinci dağarcıkta 39. Ayrılmanın nedeni yordamın yavaşlaması değil, aradığı nesnenin değişmesidir: gevşetme en çok ağırlıklı yürüyüşü bulur, problem ise en çok ağırlıklı basit yolu ister. Kâhin sekiz düğümde kalıptan ucuzdur; on üç düğümde 86,37 kat pahalı hale gelir. Gezgin satıcıda kalıp bir yaklaşık çözümdü ve yanılması beklenen bir şeydi. Bu ders daha rahatsız edici bir duruma bakar: kalıp **kanıtlanmış** bir yordamdır, kodu doğrudur, hiçbir hata içermez, ve yine de yanlış yanıt verir. Değişen tek şey uygulandığı problemdir. En kısa yol problemi M01/K04 Algoritmalar kursunun Çizge Algoritmaları konusunda kuruldu. Dijkstra Algoritması ve Bellman–Ford Algoritması dersleri gevşetme işlemini, algoritmanın değişmezini ve negatif ağırlık kısıtını ölçtü; **bu ders o yordamları tekrarlamaz**. Burada tek bir değişiklik yapılır: gevşetmedeki karşılaştırma **küçüktür**'den **büyüktür**'e çevrilir ve aynı yordam en uzun yolu aramaya koşulur. Sorulan şey, bu tek karakterlik değişikliğin kaç çizgede yanlış yanıt ürettiğidir. - **KP20.** Çizgeler ortak tanımın üretecinden gelir: 8 düğüm, her yönlü kenar yüzde 45 payla var, ağırlık 1 ile 9 arasında. Tohum **20260218**, ikinci dağarcık **20260219**. - **KP21.** İki çizge ailesi kullanılır. **Çevrimsiz** ailede kenar yalnız küçük numaralı düğümden büyüğe gider, bu yüzden hiçbir çevrim oluşamaz. **Çevrimli** ailede bu kısıt yoktur. - **KP22.** Sorulan soru her iki ailede de aynıdır: sıfırıncı düğümden yedinci düğüme giden **en çok ağırlıklı basit yol**. Basit yol, hiçbir düğümü tekrarlamayan yoldur. - **KP23.** Kâhin, bütün basit yolları derine arama ile tarar ve en ağırlıklısını alır. Bu, problemin tanımının doğrudan karşılığıdır. - **KP24.** Kalıp, en kısa yol gevşetmesinin en uzuna çevrilmiş halidir: bütün kenarlar üzerinde düğüm sayısı eksi bir kez geçilir ve her geçişte daha büyük değer kabul edilir. - **KP25.** Ölçü **adımdır**. Kâhinde bir adım bir düğüm ziyareti, kalıpta bir kenar gevşetmesidir. İki sayı aynı birimde değildir ve öyle okunur. - **KP26.** Ayrılan girdi 40 üzerindendir; 3'ün altındaki fark ölçülmemiş sayılır. - **KP27.** Hedef düğüme hiç yol yoksa her iki yordam da yanıtsız döner; bu bir ayrılma sayılmaz, çünkü ikisi de aynı yanıtı verir. - **KP28.** Düğüm sayısı ayrıca süpürülür. Kâhinin pahalı olduğu bir varsayım değil, ölçülen bir eşiktir. - **KP29.** Optimal alt yapının düşüşünü gösteren altı düğümlük çizge **elle kurulmuştur**, üreteçten gelmez. Tek bir mekanizmayı en küçük halinde göstermek için seçilmiştir. ## Aynı Yordam, İki Çizge Ailesi Aşağıdaki blok iki aileyi de üretir, kâhini ve kalıbı her çizgede yan yana koşturur ve ayrılan girdi sayısını iki dağarcık için ayrı ayrı yazar. ```python 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, cevrimli=False, n=N): """Yonlu cizge: cevrimsiz surumde kenar yalnizca kucukten buyuge gider.""" r = uretec(tohum) kume = [] for _ in range(ornek): kenar = [] for i in range(n): for j in range(n): if i == j or (not cevrimli and j < i): continue if r(100) < 45: kenar.append((i, j, r(9) + 1)) kume.append(kenar) return kume class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_en_uzun(kenar, s, n=N): """Butun basit yollar taranir: 0'dan n-1'e, hicbir dugum tekrarlanmadan.""" komsu = {} for i, j, w in kenar: komsu.setdefault(i, []).append((j, w)) en = None def gez(v, gorulen, agirlik): nonlocal en s.say() if v == n - 1: if en is None or agirlik > en: en = agirlik return for j, w in komsu.get(v, []): if j not in gorulen: gez(j, gorulen | {j}, agirlik + w) gez(0, {0}, 0) return en def kalip_gevsetme(kenar, s, n=N): """En kisa yol gevsetmesinin en uzuna cevrilmisi: kucuk yerine buyuk.""" en = [None] * n en[0] = 0 for _ in range(n - 1): for i, j, w in kenar: s.say() if en[i] is not None and (en[j] is None or en[i] + w > en[j]): en[j] = en[i] + w return en[n - 1] for ad, cevrimli in (("cevrimsiz", False), ("cevrimli ", True)): for tohum in (20260218, 20260219): ayrilan, ak, ah, fazla = [], 0, 0, 0 for no, kenar in enumerate(cizgeler(tohum, cevrimli=cevrimli), 1): s1, s2 = Sayac(), Sayac() a = kalip_gevsetme(kenar, s1) b = kahin_en_uzun(kenar, s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan.append(no) if a is not None and b is not None: fazla = max(fazla, a - b) print(ad, tohum, "| ayrilan", len(ayrilan), "/40", ayrilan[:6], "| kalip adim", ak, "| kahin adim", ah, "| en buyuk fazla", fazla) ``` ``` cevrimsiz 20260218 | ayrilan 0 /40 [] | kalip adim 3626 | kahin adim 562 | en buyuk fazla 0 cevrimsiz 20260219 | ayrilan 0 /40 [] | kalip adim 3696 | kahin adim 536 | en buyuk fazla 0 cevrimli 20260218 | ayrilan 38 /40 [1, 2, 3, 4, 5, 6] | kalip adim 7210 | kahin adim 3235 | en buyuk fazla 228 cevrimli 20260219 | ayrilan 39 /40 [1, 2, 3, 4, 5, 6] | kalip adim 7203 | kahin adim 3272 | en buyuk fazla 226 ``` ## Çevrimsizde Doğru, Çevrimlide Değil Çevrimsiz ailede ayrılan girdi **0**. Aynı yordam, aynı kod, 40 çizgenin 40'ında kâhinle aynı yanıtı veriyor ve ikinci dağarcıkta da 0'da kalıyor. Çevrimli ailede ayrılan girdi **38**, ikinci dağarcıkta **39**. Yordam bozulmadı, çizge değişti. Ayrılmanın **yönü** de ölçülüyor: kalıbın verdiği değer kâhinin değerinden hiç küçük olmuyor, en büyük fark **228 ağırlık birimi**. Kalıp fazla tahmin ediyor, yani var olmayan bir yolun ağırlığını bildiriyor. Bu, iki yordamın **farklı nesneleri** aradığının doğrudan kanıtıdır. Gevşetme yordamının hesapladığı şey, en çok ağırlıklı **yürüyüştür**: bir düğümden ötekine kenarları izleyerek gitmek, düğüm tekrarına izin vererek. Sorulan şey ise en çok ağırlıklı **basit yoldur**: düğüm tekrarı yasak. Çevrimsiz çizgede bu iki nesne çakışır, çünkü çevrim olmadığında hiçbir yürüyüş bir düğümü iki kez ziyaret edemez. Çevrim varsa çakışma biter ve gevşetme, çevrimin etrafında dönerek ağırlık biriktirmeye başlar. Biriktirmenin sonsuza gitmemesinin tek nedeni geçiş sayısının sınırlı olmasıdır. Ama bu sınır sanıldığı kadar dar değildir: tek bir geçiş içinde kenarlar sabit bir sırayla işlendiği için bir kenarın ürettiği değer aynı geçişte sonraki kenarlara zincirlenebilir. Elde edilen yürüyüş bu yüzden geçiş sayısından çok daha uzun olabilir, ve fazla tahminin 228'e kadar çıkmasının nedeni budur. Kenarların işlenme sırası değişirse dönen yanlış değer de değişir — **yanlış yanıt kararlı bile değildir**. ## Optimal Alt Yapının Düşmesi En kısa yolun kanıtı tek bir özelliğe dayanır: bir en kısa yolun her parçası da bir en kısa yoldur. Bu özellik sayesinde bir düğümün en iyi değeri, komşularının en iyi değerlerinden kurulabilir ve gevşetme çalışır. En uzun basit yolda bu özellik düşer. Sıfırıncı düğümden beşinci düğüme en uzun basit yol, ve beşinci düğümden yedinci düğüme en uzun basit yol ayrı ayrı bulunabilir; ama ikisini uç uca eklemek bir **basit yol vermeyebilir**, çünkü iki parça ortak bir düğümden geçiyor olabilir. Birleştirme yasaksa alt problemlerin çözümü ana problemin çözümüne taşınmaz, ve gevşetmenin dayandığı zemin kalkar. Bu düşüş altı düğümlük tek bir çizgede açıkça gösterilebilir. Aşağıdaki blok üç sayıyı yan yana basar: iki alt problemin ayrı ayrı en iyi çözümlerinin toplamı, gerçek en iyi çözüm, ve gevşetmenin verdiği değer. ```python KENAR = [(0, 1, 5), (1, 2, 5), (2, 3, 5), (0, 3, 1), (3, 2, 5), (2, 4, 5), (4, 5, 5), (3, 5, 1)] N = 6 def kahin_yol(kenar, bas, son): """Butun basit yollar taranir; en agirliklisi yoluyla birlikte doner.""" komsu = {} for i, j, w in kenar: komsu.setdefault(i, []).append((j, w)) en = (None, None) def gez(v, yol, agirlik): nonlocal en if v == son: if en[0] is None or agirlik > en[0]: en = (agirlik, tuple(yol)) return for j, w in komsu.get(v, []): if j not in yol: gez(j, yol + [j], agirlik + w) gez(bas, [bas], 0) return en def kalip_gevsetme(kenar, son, n=N): en = [None] * n en[0] = 0 for _ in range(n - 1): for i, j, w in kenar: if en[i] is not None and (en[j] is None or en[i] + w > en[j]): en[j] = en[i] + w return en[son] a, b, c = kahin_yol(KENAR, 0, 3), kahin_yol(KENAR, 3, 5), kahin_yol(KENAR, 0, 5) print("0'dan 3'e en uzun basit yol:", a) print("3'ten 5'e en uzun basit yol:", b) print("iki parcanin toplami :", a[0] + b[0], "| ortak dugum:", sorted(set(a[1]) & set(b[1]))) print("0'dan 5'e en uzun basit yol:", c) print("gevsetmenin verdigi :", kalip_gevsetme(KENAR, 5)) ``` ``` 0'dan 3'e en uzun basit yol: (15, (0, 1, 2, 3)) 3'ten 5'e en uzun basit yol: (15, (3, 2, 4, 5)) iki parcanin toplami : 30 | ortak dugum: [2, 3] 0'dan 5'e en uzun basit yol: (20, (0, 1, 2, 4, 5)) gevsetmenin verdigi : 70 ``` Üç sayı ayrı ayrı okunmalı. Alt problemlerin en iyi çözümleri 15 ve 15; toplamları **30**. Bu 30 hiçbir yolun ağırlığı değildir, çünkü iki parça 2 ve 3 numaralı düğümleri paylaşıyor. Gerçek yanıt **20** ve karşılık geldiği yol iki alt çözümün hiçbirini içermiyor. Gevşetmenin verdiği değer ise **70**: çevrimin etrafında birden çok kez dönerek biriktirilmiş bir yürüyüşün ağırlığı. Otuz ile yetmiş arasındaki fark önemlidir. Optimal alt yapı düşünce yalnız "alt çözümler birleştirilemez" olmuyor; gevşetme, birleştirilemeyen parçaları da aşıp tamamen farklı bir nesneyi ölçmeye başlıyor. Çıktıya bakan biri bunu anlayamaz: dönen değer bir tam sayıdır, işaretlenmemiştir, ve hiçbir uyarı taşımaz. Kursun kuralı burada da geçerlidir — **yanlışlık çıktısına bakarak seçilemez**, ancak kâhinle görülür. Aynı gözlem tersinden okunduğunda kullanışlı bir kural verir: bir yordamı yeni bir probleme taşırken sorulacak soru "kod çalışıyor mu" değil, **"kanıtın dayandığı özellik hâlâ duruyor mu"** sorusudur. Çevrimsizlik kısıtı bu derste tam olarak o özelliği ayakta tutan koşuldur. ## Kâhin Ne Zaman Pahalı Yukarıdaki çıktıda dikkat çeken bir aykırılık var: sekiz düğümde kâhin **562 adım**, kalıp **3626 adım** harcıyor. Kâhin kalıptan ucuz. Ortak tanımın "kâhin her zaman pahalıdır" okuması burada ölçülen sayıyla uyuşmuyor, ve sayı gizlenmez. Pahalılık bir tanım değil, bir **ölçek işlevidir**. Düğüm sayısı süpürülünce eşik görünür. ```python 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, tohum=TOHUM, ornek=10): r = uretec(tohum) return [[(i, j, r(9) + 1) for i in range(n) for j in range(n) if i != j and r(100) < 45] for _ in range(ornek)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_en_uzun(kenar, n, s): komsu = {} for i, j, w in kenar: komsu.setdefault(i, []).append((j, w)) en = None def gez(v, gorulen, agirlik): nonlocal en s.say() if v == n - 1: en = agirlik if en is None or agirlik > en else en return for j, w in komsu.get(v, []): if j not in gorulen: gez(j, gorulen | {j}, agirlik + w) gez(0, {0}, 0) return en def kalip_gevsetme(kenar, n, s): en = [None] * n en[0] = 0 for _ in range(n - 1): for i, j, w in kenar: s.say() if en[i] is not None and (en[j] is None or en[i] + w > en[j]): en[j] = en[i] + w return en[n - 1] print(" n | kahin adim | kalip adim | oran") for n in (6, 8, 10, 12, 13): ah = ak = 0 for kenar in cizgeler(n): s1, s2 = Sayac(), Sayac() kalip_gevsetme(kenar, n, s1) kahin_en_uzun(kenar, n, s2) ak, ah = ak + s1.adim, ah + s2.adim print(f"{n:2d} | {ah:10d} | {ak:10d} | {round(ah / ak, 2)}") ``` ``` n | kahin adim | kalip adim | oran 6 | 102 | 655 | 0.16 8 | 746 | 1785 | 0.42 10 | 10210 | 3762 | 2.71 12 | 196705 | 6677 | 29.46 13 | 747243 | 8652 | 86.37 ``` Eşik on düğümdedir. Altı düğümde kâhin kalıbın altıda biri kadar adım harcıyor; on üç düğümde **86,37 kat** fazla harcıyor. Kalıbın adımı 655'ten 8652'ye, yani on üç katına çıkıyor; kâhinin adımı 102'den 747.243'e, yani yedi bin katına. Aradaki fark, kalıbın çevrimli çizgede **hâlâ yanlış** yanıt vermesini değiştirmiyor: ucuzlaşan şey doğru yanıt değil, yanlış yanıttır. Bu tablo bir önceki dersle birlikte okunmalıdır. Gezgin satıcıda kâhin küçük girdide koşturulabiliyordu ve büyük girdide koşturulamıyordu; burada kâhin küçük girdide **kalıptan ucuz**. İki durumda da kâhinin bedeli ölçülmüştür, varsayılmamıştır. ## Özet - En uzun basit yol, en kısa yolun ters çevrilmiş hali değildir; gevşetme yordamı en çok ağırlıklı **yürüyüşü** bulur, problem ise en çok ağırlıklı **basit yolu** ister. - Çevrimsiz çizgede iki nesne çakışır ve kalıp 40 girdinin 40'ında kâhinle aynı yanıtı verir; ikinci dağarcıkta da ayrılan girdi 0. - Çevrimli çizgede kalıp 40 girdinin **38'inde** ayrılıyor, ikinci dağarcıkta 39, ve fazla tahminin en büyüğü **228 ağırlık birimi**. - Ayrılmanın kaynağı optimal alt yapının düşmesidir: iki alt yolun birleşimi ortak düğüm içerebileceği için basit yol olmayabilir. - Kâhinin pahalılığı ölçekle gelir; sekiz düğümde kâhin kalıptan ucuz, on üç düğümde 86,37 kat pahalıdır. Bir yordamın pahalı sayılması ölçülmeden yazılamaz. ## Sonraki Adım Bu derste kalıp yanlış yanıt verdi, kâhin doğru yanıtı verdi ve kâhinin bedeli ölçüldü. Sonraki ders kâhinin **kendisini** hızlandırmayı ele alır. N vezir probleminde geri izleme bütün yerleşimleri taramak yerine çatışan dalları keser; ortak tanım bunun sayılarını çoktan verdi. Sorulacak yeni soru şudur: tahtanın simetrilerini eleyerek arama alanı ne kadar küçülür, ve bu küçülme üstel büyümeyi değiştirir mi.