Bölüm 10: Dal Sınır Algoritmaları

10.1Dal sınır fikri

Karmaşık bir problemi çözmek bazen bir yol ayrımında doğru yönü bulmaya benzer. Her ayrımda birkaç seçenek vardır ve her seçenek yeni ayrımlara götürür. Hedef, sonunda en iyi noktaya varan yolu bulmaktır. Bütün yolları sonuna kadar yürümek kesin sonuç verir ama çok uzun sürer. Dal sınır yöntemi bir ara yol önerir: her ayrımda, o yönde en iyi durumda nereye varılabileceği tahmin edilir. Tahmin, elde bulunan en iyi sonuçtan kötüyse o yöne hiç gidilmez.

10.1.1Kombinatoryal optimizasyon ve kaba kuvvetin sınırı

Dal sınır yönteminin hedefi kombinatoryal optimizasyon problemleridir. Bu problemlerde çözüm sonlu sayıda ayrık seçimden kurulur: hangi eşyaların alınacağı, şehirlerin hangi sırayla gezileceği, hangi kişiye hangi işin verileceği. Olası çözümlerin sayısı sonludur ama çok büyüktür. Aranan, bir amaç fonksiyonunu en büyükleyen ya da en küçükleyen çözümdür. Yöntem kesin, yani en iyi (optimal) çözümü bulmayı amaçlar; yaklaşık bir çözümle yetinmez.

Bu tür problemlerin en basit çözümü kaba kuvvettir: bütün adaylar üretilir, her biri değerlendirilir ve en iyisi seçilir. Sorun, aday sayısının büyüme hızıdır. n eşyalı bir sırt çantası probleminde her eşya ya alınır ya alınmaz; 2ⁿ alt küme vardır. n şehirli gezgin satıcı probleminde başlangıç şehri sabitlenince kalan şehirlerin her sıralaması ayrı bir turdur; (n − 1)! tur vardır. Tablo 10.1 bu iki sayının nasıl büyüdüğünü gösterir.

Saniyede bir milyar tur değerlendiren bir bilgisayar, 20 şehirli bütün turları yaklaşık 1,2 · 10⁸ saniyede, yani üç yılı aşkın sürede bitirir. 40 şehir için gereken süre evrenin yaşının çok ötesindedir. Sırt çantasında büyüme daha yavaştır ama 40 eşyada da trilyon mertebesinde alt küme denenir. Bu problemlerin çoğu NP-zordur (NP-hard): bilinen hiçbir algoritma onları en kötü durumda polinom sürede çözemez. Dal sınır da en kötü durumu değiştirmez. Değiştirdiği şey, pratikte incelenen aday sayısıdır.

Yöntemin temel fikri tek cümleyle şöyle söylenebilir: bir dalın en fazla ne kadar iyi olabileceği önceden tahmin edilir; tahmin yeterince iyi değilse o dala hiç girilmez. Bu tahmin doğru kurulursa en iyi çözüm hiçbir zaman kaybedilmez, ama adayların büyük bölümü hiç üretilmeden elenir.

10.1.2Dallanma, sınırlama, budama

Yöntemin adı iki temel işleminden gelir. Dört adımda şöyle özetlenir:

1. Dallanma (branching): Problem daha küçük alt problemlere ayrılır. Sırt çantasında “eşya 1 alınsın mı?” sorusu iki alt problem doğurur: eşya 1'in alındığı ve alınmadığı durumlar.
2. Sınırlama (bounding): Her alt problem için ulaşılabilecek en iyi değer tahmin edilir. Bu tahmine sınır (bound) denir.
3. Budama (pruning): Sınırı, o ana kadar bulunan en iyi çözümden daha iyi olmayan alt problemler elenir. Elenen alt problemin altındaki hiçbir çözüm üretilmez.
4. Tekrar: İşlem kalan bütün alt problemler için sürdürülür. Gereksiz dallar budandıkça arama kısalır.

Şekil 10.1 yöntemi bir ağaç üzerinde gösterir. Kökten başlanır ve her düğümde bir karar verilerek aşağı inilir. Sağ üstteki düğüm budanmıştır. Altındaki yedi düğüm soluk çizilmiştir, çünkü algoritma onları hiç üretmez. Bu tasarruf, ağacın derinliği arttıkça katlanarak büyür. Kökün hemen altında budanan bir düğüm ağacın neredeyse yarısını tek hamlede eler.

Yöntem geniş bir alanda kullanılır. Gezgin satıcı, sırt çantası, çizelgeleme, kutu paketleme ve tam sayılı programlama bunların başında gelir. Endüstride üretim planlama, havayolu ekip ataması ve lojistik rotalama gibi problemleri çözen ticari eniyileme yazılımlarının çekirdeğinde de dal sınır vardır.

10.1.3Temel kavramlar

Dal sınır algoritmaları bir ağaç üzerinde çalışır ve bu ağacın düğümleri çeşitli durumlarda bulunur. Kavramların adlarını baştan koymak, sonraki izlemeleri okumayı kolaylaştırır.

Durum uzayı ağacı programda bütünüyle kurulmaz. Algoritma düğümleri gerektikçe üretir ve işi biten düğümleri unutur. Bu yüzden düğümlerin durumunu adlandırmak gerekir:

• Dallanma ve E-düğüm. Bir düğümün çocuklarını, yani alt problemlerini üretmeye dallanma denir. O anda çocukları üretilen düğüme E-düğüm (expanding node, genişletilen düğüm) denir.
• Sınır. Düğümün altındaki hiçbir çözümün geçemeyeceği iyimser değerdir. En büyüklemede bir üst sınır, en küçüklemede bir alt sınırdır.
• Canlı düğüm (live node). Üretilmiş ama henüz genişletilmemiş, hâlâ umut vaat eden düğümdür. Canlı düğümlerin hepsi bir kuyruk yapısında bekler. Bu yapı sıradan bir kuyruk, bir yığın ya da öncelikli kuyruk olabilir.
• Ölü düğüm (dead node). Genişletilmiş, olursuz bulunmuş ya da sınırı yetersiz olduğu için budanmış düğümdür. Ölü bir düğüm bir daha ele alınmaz.
• enİyi (incumbent). Şimdiye kadar bulunan en iyi tam çözümün değeridir. Budama kararları bu değere göre verilir. Arama ilerledikçe enIyi yalnız iyileşir: en büyüklemede artar, en küçüklemede azalır.

Bir çözüm problemin bütün kısıtlarını sağlıyorsa olurlu (feasible) çözümdür. Kısıtlardan birini ihlal eden düğüme olursuz düğüm denir. Örneğin ağırlığı kapasiteyi aşan bir sırt çantası olursuzdur.

Şekil 10.2 bu türleri tek bir ağaçta gösterir. Bir düğümün yaşam döngüsü şöyledir. Düğüm üretilir ve sınırı hesaplanır. Sınırı umut vaat ediyorsa canlı düğüm olarak kuyruğa girer, etmiyorsa hemen budanır. Sırası geldiğinde kuyruktan çıkar ve E-düğüm olur. Çocukları üretildikten sonra ölü düğüme dönüşür.

10.2Paradigma

Dal sınır algoritmalarının hepsi aynı iskeleti izler. Problemden probleme değişen üç şey vardır: düğümün nasıl temsil edildiği, çocukların nasıl üretildiği ve sınırın nasıl hesaplandığı. Bu kesim önce iskeleti verir, sonra sınırın, budama kurallarının ve arama stratejisinin seçimini tartışır.

10.2.1Genel şema

Aşağıdaki kod, bir en büyükleme problemi için dal sınır iskeletidir. Java'ya yakın bir sözde koddur: kuyruk, sinir(), olurluMu(), tamCozumMu() ve deger() her problemde başka bir anlam kazanır.

int enIyi = -∞;
kuyruk.ekle(kök);
while (!kuyruk.bosMu()) {
  Dugum u = kuyruk.cikar();   // strateji
  if (sinir(u) <= enIyi) continue;
  for (Dugum c : u.cocuklar()) {
    if (!olurluMu(c)) continue;
    if (tamCozumMu(c) && deger(c) > enIyi)
      enIyi = deger(c);      // yeni aday
    if (sinir(c) > enIyi)
      kuyruk.ekle(c);        // canlı düğüm
  }
}
return enIyi;

Kod bir döngüden ibarettir. Döngünün her turu beş adımdan oluşur:

1. Seç: Kuyruktan bir canlı düğüm çıkarılır. Hangi düğümün çıkacağını arama stratejisi belirler: ilk giren (FIFO), son giren (LIFO) ya da sınırı en iyi olan.
2. Tekrar sına: if (sinir(u) <= enIyi) continue; satırı düğümü bir kez daha sınar. Düğüm kuyruğa girerken umut vaat ediyordu. Ama kuyrukta beklerken enIyi büyümüş olabilir. Sınırı artık yetersizse düğüm hiç genişletilmeden atılır.
3. Dallan: for döngüsü düğümün çocuklarını üretir. Olursuz çocuklar continue ile hemen elenir.
4. Güncelle: Çocuk bir tam çözümse ve değeri enIyi'den büyükse enIyi yükseltilir. Bu çözüm yeni adaydır.
5. Sınırla: Yalnız sınırı enIyi'yi geçebilen çocuklar kuyruğa konur. Öbürleri budanır.

Döngü kuyruk boşalınca durur. O anda enIyi en iyi çözümün değeridir. Bu iddianın gerekçesi basittir. Her düğüm ya genişletilmiş ya da budanmıştır. Budanan düğümlerin altındaki çözümler enIyi'yi geçemez, çünkü sınır bunu garanti eder. Genişletilen düğümlerin altındaki çözümler ise tek tek incelenmiştir. Dolayısıyla enIyi'den iyi hiçbir çözüm atlanmamıştır.

Kod en büyükleme için yazılmıştır. En küçüklemede yönler ters çevrilir. Sınır bir alt sınırdır, enIyi başta +∞'dur ve alt(c) ≥ enIyi olan düğüm budanır. Gezgin satıcı ve atama problemleri bu biçimde çözülür.

İskelette çözümün kendisi değil yalnız değeri tutulur. Hangi eşyaların alındığı ya da turun hangi sırayla gezildiği de isteniyorsa her düğüm kendi kısmi çözümünü taşır. Bunun için bir boolean[] dizisi ya da bit maskesi yeterlidir. enIyi güncellenirken bu bilgi de kopyalanır.

10.2.2Sınır nasıl seçilir?

Dal sınırın bütün başarısı sınır fonksiyonuna bağlıdır. İyi bir sınırın dört özelliği vardır. Bunlardan biri zorunludur, öbür üçü verimlilikle ilgilidir.

• Geçerli (iyimser) olmalıdır. Bu özellik zorunludur. Sınır gerçek değerin altında kalırsa (en büyüklemede) optimumu içeren dal “yeterince iyi değil” diye budanabilir. Algoritma hata vermeden yanlış bir sonuç döndürür.
• Sıkı olmalıdır. Sınır gerçek değere ne kadar yakınsa o kadar çok dal budanır. Sonsuz büyük bir “sınır” geçerlidir ama hiçbir şeyi budamaz; algoritma kaba kuvvete döner.
• Ucuz hesaplanmalıdır. Sınır her düğümde hesaplanır. Çok pahalı bir sınır, budadığı düğümlerden daha fazla zaman harcatabilir.
• Gevşetme ile kurulur. Sınır elde etmenin genel yolu gevşetmedir (relaxation). Problemin zor kısıtlarından biri kaldırılır ve geriye kalan kolay problem çözülür. Kısıt kaldırılınca olurlu çözümler kümesi büyür. Bu yüzden gevşetilmiş problemin en iyi değeri asıl problemin en iyi değerinden kötü olamaz; geçerli bir sınırdır.

Gevşetmenin üç örneği bu notta ayrıntılı işlenir. Sırt çantasında “eşya bölünemez” kısıtı kaldırılır ve kesirli sırt çantası çözülür. Tam sayılı programlamada “değişkenler tam sayı olmalı” kısıtı kaldırılır ve sıradan doğrusal program çözülür. Gezgin satıcıda “çıkılan kenarlar tek bir tur oluşturmalı” kısıtı kaldırılır ve her şehirden en ucuz kenarla çıkılır.

Sıkılık ile ucuzluk arasında bir denge vardır. En küçüklemede alt sınır, en iyi senaryoda elde edilebilecek en küçük değerdir. Zayıf bir alt sınır neredeyse hiç budamaz ve arama süresini uzatır. Çok güçlü bir alt sınır ise her düğümde pahalı bir hesap gerektirir. Seçim, budanan düğüm sayısı ile düğüm başına yapılan iş arasındaki dengeye göre yapılır.

10.2.3Bir düğüm ne zaman budanır?

Dal sınır algoritmalarında bir düğüm üç nedenle budanır. Kuralların üçü de aynı soruyu yanıtlar: bu düğümün altında enIyi'den iyi bir çözüm olabilir mi?

1. Olursuzluk. Düğüm bir kısıtı ihlal ediyorsa altında hiçbir geçerli çözüm yoktur. Örnekler: ağırlık kapasiteyi aşmıştır, bir şehre ikinci kez gidilmiştir, doğrusal programın çözümü yoktur.
2. Sınır. En büyüklemede sinir(u) ≤ enIyi, en küçüklemede alt(u) ≥ enIyi ise altındaki çözümler en iyiyi geçemez. Düğüm olurlu olsa bile budanır.
3. Tamlık. Düğüm tam bir çözümse (yapraksa) ya da gevşetmenin çözümü zaten olurluysa dallanmaya gerek kalmaz. Örneğin tam sayılı programlamada doğrusal programın çözümü tam sayı çıkmışsa o düğümün altında daha iyi bir tam sayı çözüm yoktur. Değeri enIyi ile karşılaştırılır ve düğüm kapanır.

Eşitlik durumuna dikkat edilmelidir. sinir(u) = enIyi olan düğüm de budanır. Altında en fazla enIyi kadar iyi bir çözüm vardır ve o değerde bir çözüm zaten elde bulunur. Yalnız en iyi çözümün değeri değil bütün en iyi çözümler isteniyorsa eşitlikte budanmaz; bu, ayrı bir problemdir.

Geri izleme yalnız birinci kuralı ve tamlığı kullanır. Dal sınırı ondan ayıran şey ikinci kuraldır: düğüm geçerli olsa bile “yeterince iyi değilse” kesilir. Bu yüzden geri izlemeyle yazılmış bir aramaya tek bir sınır satırı eklemek onu dal sınıra dönüştürür.

10.2.4Arama stratejileri

Genel şemada “kuyruktan bir canlı düğüm çıkarılır” denmişti. Hangi canlı düğümün çıkacağı, kuyruk yapısının türüne bağlıdır. Üç yaygın strateji vardır (Tablo 10.2).

FIFO (first in, first out, ilk giren ilk çıkar) stratejisinde canlı düğümler sıradan bir kuyrukta bekler. Ağaç düzey düzey gezilir; bu, genişlik öncelikli aramadır. Kökün çocukları, sonra torunları, sonra onların çocukları genişletilir. Sığ düzeylerdeki çözümler erken bulunur. Ama derin düzeylere inmeden önce bütün sığ düğümler kuyrukta birikir. Dallanma derecesi 2 olan bir ağaçta k. düzey 2^k düğüm içerir; budama zayıfsa kuyruk üstel büyür.

LIFO (last in, first out, son giren ilk çıkar) stratejisinde canlı düğümler bir yığında bekler ya da arama doğrudan özyinelemeyle yazılır. Ağaç derinlik öncelikli gezilir. Yığında yalnız geçerli yoldaki düğümlerin henüz denenmemiş kardeşleri bulunur. Bu yüzden bellek, derinlik ile dallanma derecesinin çarpımıyla sınırlıdır. Bir başka yararı da kısa sürede bir yaprağa inmesidir. Erken bulunan bir tam çözüm enIyi'ye bir değer verir ve budama daha ilk adımlarda başlar.

En düşük maliyet (least cost, LC) stratejisinde canlı düğümler bir öncelikli kuyrukta bekler. Her adımda sınırı en umut verici olan düğüm, yani en büyüklemede sınırı en büyük, en küçüklemede sınırı en küçük düğüm genişletilir. Bu stratejiye en iyi önce arama (best-first search) da denir. En umut verici dala önce bakıldığı için iyi bir çözüm erken bulunur ve kalan düğümlerin çoğu budanır. Bedeli öncelikli kuyruğun bellek tüketimi ve her ekleme ile çıkarmanın O(log k) sürmesidir; k, kuyruktaki düğüm sayısıdır.

Üç strateji de sınır geçerli olduğu sürece aynı en iyi değeri bulur. Strateji yalnız iş miktarını, yani üretilen ve genişletilen düğüm sayısını, ve belleği değiştirir. Bu farklar sırt çantası örneğinde sayılarla görülecektir.

10.2.5En düşük maliyetli arama ve maliyet tahmini

LC aramanın genel biçiminde her düğüme bir tahmini maliyet atanır:

ĉ(x) = f(x) + ĝ(x)

Burada f(x), kökten x'e kadar ödenmiş maliyettir; örneğin x'in derinliği ya da o ana kadar gidilen yolun uzunluğu. ĝ(x) ise x'ten bir çözüme kalan maliyetin tahminidir. Canlı düğümlerden ĉ'si en küçük olan genişletilir.

İki uç seçim, öbür stratejileri verir. ĝ = 0 alınır ve f düğümün derinliği olursa hep en sığ düğüm seçilir; arama FIFO'ya yaklaşır. f = 0 alınırsa yalnız kalan maliyet tahminine bakılır; arama, hedefe en yakın görünen dala dalan açgözlü bir derinlik aramasına yaklaşır. İkisinin toplamı, ödenmiş maliyeti ve kalan tahmini birlikte tartar.

Tahminin iyi bir özelliği, gerçek kalan maliyetten hiçbir zaman büyük olmamasıdır. Böyle bir tahmine kabul edilebilir sezgisel (admissible heuristic) denir. Bu özellik, dal sınırdaki geçerli sınırın karşılığıdır: kalan maliyet olduğundan az gösterilir, yani tahmin iyimserdir.

Klasik örnek 8 bulmacasıdır. 3 × 3'lük bir çerçevede 1'den 8'e kadar numaralı taşlar ve bir boşluk vardır. Bir hamlede boşluğa komşu bir taş boşluğa kaydırılır. Hedef, taşları 1 2 3 / 4 5 6 / 7 8 düzenine getirmektir; boşluk sağ alt köşededir. Bu problemde f(x) o ana kadar yapılan hamle sayısı, ĝ(x) ise yerinde olmayan taş sayısıdır. Her yanlış yerdeki taş en az bir hamle ister. Bu yüzden ĝ kalan hamle sayısını hiçbir zaman fazla tahmin etmez.

Şekil 10.4 aramanın ilk adımını gösterir. Başlangıç durumu 1 2 3 / 4 □ 6 / 7 5 8'dir (□ boşluk). Yalnız 5 ve 8 yanlış yerdedir; kökün ĉ değeri 0 + 2 = 2'dir. Kök genişletilince dört çocuk oluşur:

• Boşluk yukarı: 2 aşağı iner; 1 □ 3 / 4 2 6 / 7 5 8. Yanlış taşlar 2, 5, 8: ĉ = 1 + 3 = 4.
• Boşluk aşağı: 5 yukarı çıkar; 1 2 3 / 4 5 6 / 7 □ 8. Yalnız 8 yanlış: ĉ = 1 + 1 = 2.
• Boşluk sola: 4 sağa kayar; 1 2 3 / □ 4 6 / 7 5 8. Yanlış taşlar 4, 5, 8: ĉ = 4.
• Boşluk sağa: 6 sola kayar; 1 2 3 / 4 6 □ / 7 5 8. Yanlış taşlar 6, 5, 8: ĉ = 4.

En küçük ĉ'li çocuk “boşluk aşağı”dır ve o genişletilir. Onun çocuklarından “boşluk sağa” 8'i sola kaydırır ve hedefe ulaşır: ĉ = 2 + 0 = 2. Çözüm 2 hamledir ve yalnız 2 genişletme yapılmıştır. FIFO ise ĉ değerlerine bakmaz. Birinci düzeydeki düğümleri üretim sırasıyla genişletir ve “boşluk yukarı” gibi umutsuz bir dala da zaman harcar. Yol bulmadaki A* algoritması bu fikrin ağırlıklı çizgelerdeki karşılığıdır; ilişki notun sonunda ayrıca tartışılır.

10.2.6Geri izleme ile karşılaştırma

Dal sınır ile geri izleme (backtracking) aynı ağacı gezer ve kodları birbirine çok benzer. İkisi de kısmi çözümleri genişletir ve umutsuz dalları keser. Farkları neyi aradıklarında ve neye göre kestiklerindedir (Tablo 10.3).

Geri izleme N vezir problemini çözerken bir vezirin başka bir veziri tehdit edip etmediğine bakar. Tehdit varsa dalı keser. Bütün çözümler ya da bir çözüm aranır; çözümler arasında “daha iyi” diye bir sıralama yoktur. Dal sınır ise çözümler arasında bir sıralama olduğunda anlamlıdır. Bir dal hiçbir kısıtı ihlal etmese bile, içinden çıkabilecek en iyi çözüm elde bulunandan kötüyse kesilir.

Bu farkın kod karşılığı tek bir satırdır. Gezgin satıcı ya da maksimum klik için yazılmış ve sınır testi içermeyen bir arama aslında geri izlemedir; bütün ağacı gezer. if (altSinir(...) < enIyi) gibi tek bir sınır satırı eklenince arama dal sınıra dönüşür.

10.2.7Avantajlar ve dezavantajlar

Yöntemin güçlü yanları şunlardır:

• Karmaşık optimizasyon problemlerinde kesin en iyi çözümü bulur. Yaklaşık yöntemlerin aksine sonucun en iyi olduğu kanıtlıdır.
• Arama alanını daraltır ve gereksiz olasılıkları eler. İyi bir sınırla ağacın çok küçük bir kesri gezilir.
• En iyi rotayı ya da seçimi bulmayı gerektiren problemler için doğal bir çerçevedir.
• Çözümleri ağaç olarak temsil edilebilen çok çeşitli problemlere uygulanır.
• Erken durdurulabilir. Arama yarıda kesilirse elde bir çözüm (enIyi) ve kuyruktaki en iyi sınır bulunur. İkisinin farkı, eldeki çözümün en iyiden en fazla ne kadar uzak olduğunu söyler. Bu bilgi bir kalite garantisidir.

Zayıf yanları da vardır:

• En kötü durumda süre yine üsteldir. Çok fazla olasılık içeren ve sınırın iyi budamadığı durumlarda süre kabul edilemez ölçüde uzar.
• FIFO ve en iyi önce stratejilerinde bellek de üstel büyüyebilir.
• Başarı iyi bir sınır tahminine bağlıdır; zayıf bir sınır neredeyse hiç budamaz.
• Her probleme özgü bir sınır ve dallanma kuralı tasarlamak gerekir. Uygulaması geri izlemeden karmaşıktır.

10.30/1 sırt çantası

Yöntemin bütün parçalarını görmek için ilk uygulama olarak 0/1 sırt çantası problemi seçilir. Problem tanıdıktır, durum uzayı ağacı ikilidir ve sınırı kolay hesaplanır. Aynı örnek üç farklı stratejiyle çalıştırılacak ve sonuçlar karşılaştırılacaktır.

10.3.1Problem ve durum uzayı ağacı

Problemi kısaca hatırlatmak yeterlidir. n eşya vardır; i. eşyanın kazancı p_i, ağırlığı w_i'dir. Çantanın kapasitesi W'dir. Her eşya için bir karar verilir: x_i ∈ {0, 1}. Eşya ya bütünüyle alınır (1) ya hiç alınmaz (0); bölünemez. Amaç

Σ w_i x_i ≤ W koşuluyla Σ p_i x_i en büyük

olacak biçimde kararları vermektir. Bu notta sırt çantasının dinamik programlama çözümü kullanılmaz. Dinamik programlama kapasite W'ye bağlı bir tablo kurar ve O(nW) sürer. W çok büyükse ya da ağırlıklar tam sayı değilse bu tablo kurulamaz; dal sınır ise ağırlıkların büyüklüğünden etkilenmez.

Dal sınır için eşyalar önce kazanç/ağırlık oranına göre azalan sırada dizilir. Bu sıra, sınır hesabının geçerli olması için gereklidir. Durum uzayı ağacı ikilidir. Kök hiçbir kararın verilmediği durumdur. i. düzeyde i. eşyanın kararı verilir: sol dal “eşya i alındı” (1), sağ dal “alınmadı” (0). Dört eşyalı bir problemde ağacın beş düzeyi vardır ve tam ağaç 2⁵ − 1 = 31 düğüm içerir. Bunların 16'sı yapraktır; her yaprak bir alt kümeye karşılık gelir.

Bu notta kullanılan örnek Tablo 10.4'da verilmiştir. Kapasite W = 16'dır. Eşyalar oranlarına göre zaten azalan sıradadır: 20, 6, 5, 2.

Optimum, eşya 1 ile eşya 3'ün alınmasıdır: kazanç 40 + 50 = 90, ağırlık 2 + 10 = 12. Kaba kuvvet bu sonucu 16 alt kümenin hepsini deneyerek bulur. Dal sınır ise 31 düğümün tamamını üretmeden aynı sonuca ulaşır. Ne kadar az düğüm üretildiği, kullanılan stratejiye bağlıdır.

10.3.2Üst sınır: kesirli sırt çantası gevşetmesi

Sırt çantası bir en büyükleme problemidir; her düğüm için bir üst sınır gerekir. Bu sınır gevşetmeyle kurulur. “Eşya bölünemez” kısıtı kaldırılınca problem kesirli sırt çantasına (fractional knapsack) dönüşür. Kesirli sırt çantasında bir eşyanın istenen bir kesri alınabilir ve kazancın da aynı kesri elde edilir. Bu problemi açgözlü yöntem en iyi biçimde çözer: eşyalar oran sırasıyla, sığdığı kadar tam alınır; ilk sığmayan eşyanın sığan kesri alınır ve çanta dolar.

Bir düğümün sınırı aynı fikirle hesaplanır. u düğümünde verilmiş kararlar sabittir: u'nun kazancı k, ağırlığı a, düzeyi i olsun. Henüz karar verilmemiş eşyalar i + 1, i + 2, … oran sırasıyla, sığdığı kadar tam eklenir. İlk sığmayan eşya m olsun; onun sığan kesri eklenir:

sinir(u) = k + Σ_{j = i+1}^m−1 p_j + (W − a − Σ_{j = i+1}^m−1 w_j) · p_m / w_m

Bütün kalan eşyalar sığıyorsa m yoktur ve son terim eklenmez. Düğümün kendisi olursuzsa, yani a > W ise sınır 0 alınır. Bu, düğümün hiçbir zaman enIyi'yi geçemeyeceğini ve kuyruğa girmeyeceğini garanti eder.

İspatın iki dayanağı vardır: her 0/1 çözümün bir kesirli çözüm olması ve açgözlü yöntemin kesirli problemde en iyi olması. İkinci dayanak, oran sırasına bağlıdır. Eşyalar oran sırasında değilse açgözlü yöntem kesirli problemde de en iyiyi bulamaz. Bu durumda hesaplanan değer gerçek optimumun altında kalabilir ve sınır geçerliliğini yitirir.

Kökün sınırı örnekte şöyle hesaplanır. Eşya 1 ve 2 tam sığar: 40 + 30 = 70, ağırlık 7. Eşya 3'ün ağırlığı 10'dur ve kalan 9 birime sığmaz. Eşya 3'ün 9/10'u alınır: 9 · 50/10 = 45. Böylece sinir(kök) = 70 + 45 = 115 olur. Bu sayının anlamı şudur: dört eşyadan hangi alt küme seçilirse seçilsin kazanç 115'i geçemez. Gerçek optimum 90'dır; sınır iyimserdir ama geçerlidir.

10.3.3Kod izleme: sinir(kök)

Sınır fonksiyonunun Java karşılığı aşağıdadır. Diziler sıfırdan başlar: p[0] ve w[0] eşya 1'e aittir. n eşya sayısı, W kapasitedir. Dugum sınıfı seviye, kazanc, agirlik ve sinir alanlarını taşır. Kökün seviyesi −1'dir; henüz hiçbir eşyanın kararı verilmemiştir.

double sinir(Dugum u) {
  if (u.agirlik > W) return 0;   // olursuz
  double sonuc = u.kazanc;
  int toplamAg = u.agirlik;
  int j = u.seviye + 1;
  while (j < n && toplamAg + w[j] <= W) {
    toplamAg += w[j];
    sonuc += p[j];
    j++;
  }
  if (j < n)                // kesirli parça
    sonuc += (W - toplamAg) * (double) p[j] / w[j];
  return sonuc;
}

Satırların görevi şöyledir:

• if (u.agirlik > W) return 0; olursuz düğümü yakalar. Ağırlık kapasiteyi aşmışsa düğümün altında hiçbir olurlu çözüm yoktur; 0 dönen sınır onun kuyruğa girmesini engeller.
• sonuc düğümün kendi kazancıyla, toplamAg kendi ağırlığıyla başlar. j, kararı verilmemiş ilk eşyayı gösterir.
• while döngüsü, sığdığı sürece eşyaları tam ekler. Koşulun iki parçası vardır: eşya kalmalıdır (j < n) ve eşya j kalan kapasiteye tam sığmalıdır.
• Döngü bittiğinde ya eşya kalmamıştır ya da j, ilk sığmayan eşyadır. İkinci durumda (W - toplamAg) * (double) p[j] / w[j] kadar kesirli kazanç eklenir. (double) dönüşümü tam sayı bölmesini önler.

Fonksiyon bir düğüm için en fazla n eşyaya bakar; süresi O(n)'dir. Ek bellek kullanmaz. Tablo 10.5 kök için çağrının izlemesidir.

Şekil 10.6 aynı hesabı bir çubuk üzerinde gösterir. Çubuğun yeşil kısmı tam alınan eşyalardır, taralı kısım kesirli parçadır. Kesirli parça 0/1 problemde alınamaz; sınırın gerçek değerden büyük olmasının nedeni budur.

10.3.4En iyi önce dal sınır adım adım

Şimdi asıl örnek (W = 16) en iyi önce stratejisiyle çözülür. Her düğüm bir harfle adlandırılır ve “kazanç / ağırlık” çifti ile sınırı (s) birlikte verilir. Kuyruk bir öncelikli kuyruktur; her adımda sınırı en büyük düğüm çıkar. Bir çocuk üretildiğinde, olurluysa ve kazancı enIyi'den büyükse enIyi hemen güncellenir. Sırt çantasında her olurlu düğüm, alınan eşyalardan oluşan geçerli bir çözümdür; güncelleme için yaprağa inmek gerekmez.

1. Başlangıç. Kök A: hiçbir eşya seçilmedi; 0 / 0, s = 115. enIyi = 0. Kuyruk: A (115).
2. A çıkarılır ve dallanır. B (eşya 1 alındı): 40 / 2, olurlu; enIyi = 40. B'nin sınırı kökünküyle aynıdır, çünkü kökün sınırı zaten eşya 1'i tam alıyordu: s = 115. C (eşya 1 yok): 0 / 0. Sınır hesabında eşya 2 ve eşya 3 tam sığar: 30 + 50 = 80, ağırlık 5 + 10 = 15. Eşya 4 sığmaz; kalan 1 birim için 1 · 10/5 = 2 eklenir. s = 82. Kuyruk: B (115), C (82).
3. B çıkarılır ve dallanır. D (eşya 2 alındı): 70 / 7; enIyi = 70, s = 115. E (eşya 2 yok): 40 / 2; eşya 3 tam sığar (90, ağırlık 12), eşya 4'ün 4/5'i eklenir (8): s = 98. Kuyruk: D (115), E (98), C (82).
4. D çıkarılır ve dallanır. F (eşya 3 alındı): ağırlık 7 + 10 = 17 > 16; olursuz, sınırı 0, budanır. G (eşya 3 yok): 70 / 7; eşya 4 tam sığar (80, ağırlık 12), başka eşya yok: s = 80. 80 > 70 olduğu için G kuyruğa girer. Kuyruk: E (98), C (82), G (80).
5. E çıkarılır ve dallanır. H (eşya 3 alındı): 90 / 12, olurlu; enIyi = 90. H'nin sınırı 90 + 4 · 2 = 98'dir ve kuyruğa girer. I (eşya 3 yok): 40 / 2; eşya 4 tam sığar: s = 50 ≤ 90, budanır. Kuyruk: H (98), C (82), G (80).
6. H çıkarılır ve dallanır. J (eşya 4 alındı): ağırlık 17; olursuz. K (eşya 4 yok): 90 / 12, son eşya; s = 90 ≤ 90, budanır. Kuyruk: C (82), G (80).
7. C ve G atılır. C çıkarılır: 82 ≤ 90, tekrar sınamada atılır. G çıkarılır: 80 ≤ 90, atılır. Kuyruk boşalır.

Sonuç enIyi = 90'dır ve H düğümünde bulunmuştur: eşya 1 ve 3. Tam ağacın 31 düğümünden yalnız 11'i üretilmiştir: A'dan K'ye kadar. Bunların 5'i genişletilmiştir: A, B, D, E, H. Kuyruk hiçbir anda 3 düğümü aşmamıştır.

Şekil 10.7 aramanın bitmiş ağacını gösterir. İzlemenin iki anı öğreticidir. Birincisi 4. adımdır. D'nin sınırı 115'tir ama D'nin “al” çocuğu olursuzdur ve “alma” çocuğunun sınırı 80'e düşer. Sınır, karar verildikçe gerçeğe yaklaşır. İkincisi son adımdır. C ve G kuyruğa girdikleri anda umut vaat ediyordu: C girdiğinde enIyi 40, G girdiğinde 70'ti. Sıraları geldiğinde enIyi 90 olmuştu. Tekrar sınama olmasaydı ikisi de genişletilirdi; sonuç değişmezdi ama boşuna iş yapılırdı.

10.3.5Java kodu: dalSinir()

En iyi önce dal sınırın Java kodu aşağıdadır. Öncelikli kuyruk olarak PriorityQueue kullanılır.

int dalSinir() {
  PriorityQueue<Dugum> kuyruk = new PriorityQueue<>(
      (a, b) -> Double.compare(b.sinir, a.sinir));
  Dugum kok = new Dugum(-1, 0, 0);
  kok.sinir = sinir(kok);
  kuyruk.add(kok);  int enIyi = 0;
  while (!kuyruk.isEmpty()) {
    Dugum u = kuyruk.poll();           // en büyük sınır
    if (u.sinir <= enIyi || u.seviye == n - 1) continue;
    int i = u.seviye + 1;
    // sol çocuk: i. eşyayı al
    Dugum al = new Dugum(i, u.kazanc + p[i],
                         u.agirlik + w[i]);
    if (al.agirlik <= W && al.kazanc > enIyi)
      enIyi = al.kazanc;
    al.sinir = sinir(al);
    if (al.sinir > enIyi) kuyruk.add(al);
    // sağ çocuk: i. eşyayı alma
    Dugum alma = new Dugum(i, u.kazanc, u.agirlik);
    alma.sinir = sinir(alma);
    if (alma.sinir > enIyi) kuyruk.add(alma);
  }
  return enIyi;
}

Kodun önemli noktaları şunlardır:

• Karşılaştırıcı terstir. PriorityQueue varsayılan olarak en küçük öğeyi önce verir. (a, b) -> Double.compare(b.sinir, a.sinir) karşılaştırıcısı sırayı tersine çevirir; böylece poll() sınırı en büyük düğümü döndürür.
• Tekrar sınama. if (u.sinir <= enIyi || u.seviye == n - 1) continue; satırı iki şeyi yakalar. Birincisi, kuyrukta beklerken eskiyen düğümlerdir (örnekte C ve G). İkincisi, son düzeydeki düğümlerdir; onların çocuğu yoktur. Sınırın kendisi kuyrukta değişmez; değişen enIyi'dir.
• Sol çocuk. al düğümü i. eşyayı ekler. Ağırlık kapasiteyi aşmıyor ve kazanç enIyi'den büyükse enIyi güncellenir. Sonra sınırı hesaplanır ve sınır enIyi'yi geçiyorsa kuyruğa girer. Olursuz bir al düğümünün sınırı 0'dır; kuyruğa hiç girmez.
• Sağ çocuk. alma düğümü ebeveyninin kazanç ve ağırlığını aynen taşır. Ebeveyn olurluysa alma da olurludur ve kazancı enIyi'yi değiştirmez. Bu yüzden yalnız sınırı denetlenir.
• Strateji değişikliği. FIFO için ArrayDeque ile add()/poll(), LIFO için push()/pop() kullanılır. Kodun geri kalanı aynıdır.

Kod yalnız en iyi değeri döndürür. Seçilen eşyalar da isteniyorsa Dugum sınıfına bir boolean[] dizisi ya da bir bit maskesi eklenir. Her çocuk ebeveyninin dizisini kopyalar ve kendi kararını işler. enIyi güncellenirken bu dizi de saklanır.

Maliyet. En kötü durumda tam ağacın bütün düğümleri üretilir: O(2ⁿ) düğüm. Her düğümde sınır hesabı O(n), kuyruk işlemi O(log k) sürer. En kötü süre O(n · 2ⁿ)'dir. Bellek kuyruktaki düğüm sayısıyla orantılıdır ve en kötü durumda o da üsteldir. Pratikte iyi bir sınırla üretilen düğüm sayısı bunun çok altında kalır.

10.3.6FIFO dal sınır: kod izleme

Aynı örnek bu kez FIFO kuyrukla çözülür. Kod, öncelikli kuyruk yerine ArrayDeque kullanır. Çocuklar cocuk(u, al) yardımcı metoduyla üretilir; metot çocuğu kurar ve sınırını da hesaplar. Döngü önce “al” (al = 1), sonra “alma” (al = 0) çocuğunu üretir.

int fifoDalSinir() {
  ArrayDeque<Dugum> kuyruk = new ArrayDeque<>();
  kuyruk.add(kok);  int enIyi = 0;
  while (!kuyruk.isEmpty()) {
    Dugum u = kuyruk.poll();          // ilk giren
    if (u.sinir <= enIyi || u.seviye == n - 1) continue;
    for (int al = 1; al >= 0; al--) { // önce al
      Dugum c = cocuk(u, al);         // sinir(c) dahil
      if (c.agirlik <= W && c.kazanc > enIyi)
        enIyi = c.kazanc;               // yeni aday
      if (c.sinir > enIyi) kuyruk.add(c);
    }
  }
  return enIyi;
}

Bu kodda kok önceden kurulmuş ve sınırı hesaplanmıştır. Döngünün yapısı en iyi önce koduyla aynıdır; tek fark, poll()'un kuyruğa ilk giren düğümü döndürmesidir. Tablo 10.6 izlemenin her adımını verir. Harfler üretim sırasını izlemez; C'nin çocukları L ve M diye adlandırılmıştır.

Sonuç yine 90'dır. FIFO 13 düğüm üretmiş ve 6 düğüm genişletmiştir: A, B, C, D, E, H. Kuyruk en çok 3 düğüm tutmuştur. En iyi önce stratejisiyle farkın kaynağı C düğümüdür. En iyi önce, C'nin sınırı (82) kuyruktaki öbür düğümlerden küçük olduğu için C'yi sona bırakmıştı; o sıraya gelindiğinde enIyi 90 olmuş ve C hiç genişletilmemişti. FIFO ise C'yi düzey sırasına göre üçüncü olarak genişletir. O anda enIyi yalnız 70'tir ve C'nin sınırı 82 olduğu için C atılamaz. C'nin genişletilmesi iki fazla düğüm (L ve M) üretir ve bir fazla genişletme demektir. L de sonunda boşuna kuyrukta bekler.

10.3.7Üç stratejinin karşılaştırılması

Aynı örnek LIFO stratejisiyle de çözülebilir. LIFO'da canlı düğümler bir yığında bekler. Çocuklar yığına “önce al çıksın” diye konursa, yani önce “alma”, sonra “al” çocuğu eklenirse arama hep sol daldan derine iner. A'dan sonra B, sonra D genişletilir. D'nin “al” çocuğu olursuzdur; “alma” çocuğu G (70/7, 80) genişletilir. G'nin “al” çocuğu eşya 4'ü ekler: 80/12. Bu olurlu bir çözümdür ve enIyi 80'e çıkar. Arama sonra E'ye döner ve H'de 90'ı bulur. Sonunda yığında kalan C (82) atılır. LIFO da 13 düğüm üretir ve 6 düğüm genişletir: A, B, D, G, E, H.

Şekil 10.9 üç aramayı yan yana gösterir; Tablo 10.7 sayıları özetler.

Tablodan üç sonuç çıkar. Birincisi, üç strateji de aynı optimumu bulur; strateji yalnız iş miktarını etkiler. İkincisi, en iyi önce bu örnekte en az düğümü üretmiştir. Bu genel bir eğilimdir ama garanti değildir. Üçüncüsü, küçük örnekte bellek farkı görünmez: üçünde de kuyruk en çok 3 düğüm tutar. Büyük örneklerde fark açılır. FIFO ve en iyi önce stratejilerinde kuyruk üstel büyüyebilir; LIFO'da yığın derinlikle orantılı kalır.

Çocukların yığına konma sırası LIFO'da önemlidir. Sıra tersine çevrilirse, yani “alma” çocuğu önce çıkarsa, arama önce eşya 1'in alınmadığı dala dalar. O dalda iyi çözümler yoktur; enIyi önce 40, sonra 50, 60, 80 diye yavaşça yükselir. Bu sürüm 21 düğüm üretir ve 10 düğüm genişletir. Derinlik öncelikli aramada iyi bir çözümü erken bulmak bütün aramayı hızlandırır. Bu yüzden çocuklar, umut vaat eden dal önce çıkacak biçimde sıralanır.

10.4Gezgin satıcı problemi

Gezgin satıcı problemi (travelling salesman problem, TSP) bir en küçükleme problemidir. Kısaca hatırlatmak gerekirse: n şehir ve her şehir çifti arasındaki uzaklık verilir. Her şehri tam bir kez ziyaret edip başlangıca dönen en kısa tur aranır. Uzaklıklar bir d matrisinde tutulur; d[i][j], i'den j'ye gitmenin maliyetidir. d[i][j] = d[j][i] ise problem simetriktir. Problem NP-zordur ve kaba kuvvet (n − 1)! tur dener. Bu kesimde aynı dört şehirli örnek üç farklı alt sınırla incelenir.

10.4.1Durum uzayı ve en ucuz çıkış kenarı sınırı

Tur her zaman şehir 0'dan başlar. Durum uzayı ağacının her düğümü 0'dan başlayan bir kısmi yoldur. Kök yalnız 0'ı içerir. Bir düğümün çocukları, yolun son şehrinden henüz ziyaret edilmemiş bir şehre gidilerek elde edilir. n − 1 derinliğindeki düğümler bütün şehirleri içerir; son şehirden 0'a dönülünce tur tamamlanır.

Problem en küçükleme olduğu için her düğüme bir alt sınır gerekir: o kısmi yolu tamamlayan hiçbir turun maliyeti bu değerin altına inemez. En basit alt sınır şu gözleme dayanır. Turu tamamlamak için bulunulan son şehirden ve henüz ziyaret edilmemiş her şehirden tam bir kez çıkılmak zorundadır. Her çıkış, o şehrin en ucuz kenarı kadar tutar. Şehir v'nin en ucuz çıkış kenarının maliyeti enKucuk[v] olsun. Bu değerler arama başlamadan bir kez hesaplanır. Alt sınır şöyledir:

alt(yol) = maliyet(yol) + enKucuk[son şehir] + Σ_{v ziyaret edilmemiş} enKucuk[v]

Bu sınır bir gevşetmedir. Asıl problemde çıkılan kenarlar tek bir tur oluşturmalıdır. Gevşetmede bu koşul kaldırılır: her şehir kendi en ucuz kenarıyla çıkar, kenarların bir tur oluşturup oluşturmadığına bakılmaz. Kaldırılan kısıt yüzünden gevşetmenin değeri hiçbir turun maliyetinden büyük olamaz.

Bu notta kullanılan dört şehirli simetrik matris Tablo 10.8'te verilmiştir. Son sütun her satırın en küçüğüdür, yani enKucuk dizisidir.

Kökte yol yalnız 0'dır ve maliyeti 0'dır. Son şehir 0'dır ve 1, 2, 3 ziyaret edilmemiştir. Alt sınır 0 + 2 + 3 + 2 + 5 = 12 olur. Şekil 10.10'de kalın çizilen dört kenar bir tur oluşturmaz: 0-2 kenarı iki kez seçilmiştir ve 3'e hiç girilmez. Gevşetmenin değeri bu yüzden gerçek turdan küçüktür.

Yol 0 → 1 için sınır şöyledir. Yolun maliyeti d[0][1] = 3'tür. Son şehir 1'den çıkılacaktır: enKucuk[1] = 3. Ziyaret edilmemiş şehirler 2 ve 3'tür: 2 + 5. Toplam 3 + 3 + 7 = 13'tür. Sınır kökünkinden büyüktür; karar verildikçe sınır gerçeğe yaklaşır.

10.4.2Kod izleme: tsp(0, 0, 1)

Gezgin satıcı için dal sınır, sınırlı bir derinlik öncelikli arama olarak yazılır. Bu bir LIFO dal sınırdır; yığın görevini özyineleme üstlenir.

void tsp(int sehir, int maliyet, int sayac) {
  if (sayac == n) {           // tur tamam
    int tur = maliyet + d[sehir][0];
    if (tur < enIyi) enIyi = tur;
    return;
  }
  for (int s = 0; s < n; s++) {
    if (ziyaret[s]) continue;
    int yeni = maliyet + d[sehir][s];
    ziyaret[s] = true;
    if (altSinir(s, yeni) < enIyi) // sınır
      tsp(s, yeni, sayac + 1);
    ziyaret[s] = false;      // geri al
  }
}

Metodun parametreleri yolun son şehri (sehir), yolun maliyeti (maliyet) ve yoldaki şehir sayısıdır (sayac). ziyaret dizisi yoldaki şehirleri işaretler; enIyi başta sonsuzdur. İlk çağrıdan önce ziyaret[0] = true yapılır ve tsp(0, 0, 1) çağrılır. Satırların görevi şöyledir:

• if (sayac == n) taban durumdur. Bütün şehirler yoldadır; son şehirden 0'a dönülür ve tur tamamlanır. Tur enIyi'den kısaysa enIyi güncellenir.
• for döngüsü dallanmadır. Ziyaret edilmemiş her şehir s bir çocuktur. Ziyaret edilmiş şehirler continue ile atlanır; bu, olursuzluk kuralıdır.
• ziyaret[s] = true; şehri yola ekler. Sınır hesabı bu işaretlemeden sonra yapılır; böylece altSinir şehir s'yi “ziyaret edildi” görür ve onu yalnız son şehir olarak sayar.
• if (altSinir(s, yeni) < enIyi) sınır kuralıdır. Alt sınır enIyi'den küçükse dala girilir; değilse dal budanır.
• ziyaret[s] = false; geri almadır. Döngü bir sonraki şehre geçmeden yol eski hâline döner.

Tablo 10.9 aramanın bütün adımlarını sırayla verir.

İzlemede dikkat çeken birkaç nokta vardır. İlk tur (47) kötüdür ama enIyi'ye sonlu bir değer verir. Hemen ardından 18 bulunur. 8. adımda 0 → 2 dalının sınırı 12'dir; 12 < 18 olduğu için dala girilir. Bu dalın iki çocuğu budanır. 10. adımda sınır enIyi'ye eşittir: 18 ≥ 18. Bu daldaki en iyi tur en fazla 18 olabilir ve 18'lik bir tur zaten bulunmuştur. 11. adımda kökün son çocuğu 0 → 3 doğrudan budanır ve altındaki iki tur hiç denenmez.

Sonuç en kısa tur 0 → 1 → 3 → 2 → 0'dır ve uzunluğu 3 + 5 + 8 + 2 = 18'dir. Tam durum uzayı ağacında 1 + 3 + 6 + 6 = 16 düğüm vardır. Dal sınır, kök dahil 10 düğüm üretmiş ve tsp metodunu 7 kez çağırmıştır. Budamasız arama 16 düğümün hepsini üretir ve metodu 16 kez çağırır.

Kodda en iyi turun kendisi saklanmaz. Saklamak için bir int[] yol dizisi tutulur. Döngüde dala girmeden önce yol[sayac] = s yazılır. Taban durumda tur enIyi'den kısaysa enIyiYol = yol.clone() ile kopyalanır. Kopya gereklidir, çünkü yol dizisi aramanın geri kalanında değişmeye devam eder.

10.4.3Kod izleme: altSinir(3, 8)

Sınır fonksiyonu kısadır:

int altSinir(int son, int maliyet) {
  int alt = maliyet + enKucuk[son];
  for (int v = 0; v < n; v++)
    if (!ziyaret[v])       // gidilmemiş
      alt += enKucuk[v];
  return alt;
}

alt önce yolun maliyeti ile son şehrin en ucuz çıkışını toplar. Döngü bütün şehirleri gezer ve ziyaret edilmemiş her şehrin enKucuk değerini ekler. Ziyaret edilmiş bir şehir iki türlüdür. Ya yolun içindedir ve çıkış kenarı zaten maliyete katılmıştır, ya da son şehirdir ve çıkışı en başta eklenmiştir. Her iki durumda da yeniden eklenmemelidir. Fonksiyon O(n) sürer.

tsp izlemesinin 5. adımındaki çağrı altSinir(3, 8)'dir. Yol 0 → 1 → 3'tür, maliyeti 3 + 5 = 8'dir ve ziyaret = {0, 1, 3}'tür.

Fonksiyon 15 döndürür. Bu daldaki her tur en az 15 tutar. Gerçek tur 0 → 1 → 3 → 2 → 0'dır ve 18 tutar. Arama sırasında enIyi 47 olduğu için 15 < 47 sağlanır ve dala girilir.

10.4.4Daha sıkı sınır: iki en kısa kenar

En ucuz çıkış sınırı her şehirden yalnız bir kenar sayar. Oysa bir turda her şehre bir kenarla girilir ve bir kenarla çıkılır. Simetrik problemde giriş ve çıkış ayrımı yoktur: her şehir tam olarak iki tur kenarına değer. Şehrin bu iki kenarının toplamı, ona değen en kısa iki kenarın toplamından küçük olamaz. Bu gözlem tüm şehirler için toplanırsa her tur kenarı iki kez sayılır: bir kez bir ucunda, bir kez öbür ucunda. Böylece daha sıkı bir alt sınır elde edilir:

tur ≥ ½ · Σ_v (v'ye değen en kısa iki kenarın toplamı)

Kökte bu sınırı hesaplayan kod şöyledir:

double ikiKenarSinir() {
  int toplam = 0;
  for (int v = 0; v < n; v++) {
    int m1 = INF, m2 = INF;     // en küçük iki
    for (int u = 0; u < n; u++) {
      if (u == v) continue;
      if (d[v][u] < m1) { m2 = m1; m1 = d[v][u]; }
      else if (d[v][u] < m2) m2 = d[v][u];
    }
    toplam += m1 + m2;
  }
  return toplam / 2.0;  // her kenar iki kez
}

Dış döngü şehirleri gezer. İç döngü, şehre değen kenarlar arasından en küçük iki değeri m1 ≤ m2 olacak biçimde bulur. Yeni bir kenar m1'den küçükse eski m1 ikinci sıraya kayar ve yeni kenar birinci olur. Yalnız m2'den küçükse ikinci sıraya yazılır. Bu, iki öğeli bir “en küçükler listesi”nin güncellenmesidir. Toplam her kenarı iki kez saydığı için sonuç 2.0'a bölünür; double bölme, toplam tek sayıysa yarımı korur. Süre O(n²)'dir.

v = 0 satırı iç döngünün nasıl çalıştığını gösterir. Başta m1 = m2 = ∞'dur. u = 1'de 3 < ∞: m1 = 3 olur, eski m1 (∞) m2'ye kayar. u = 2'de 2 < 3: m2 = 3, m1 = 2 olur. u = 3'te 15 ikisinden de büyüktür; değişiklik yoktur. Toplama 2 + 3 = 5 eklenir. Sonunda toplam 36'dır ve fonksiyon 36 / 2 = 18 döndürür.

Sonuç dikkat çekicidir: sınır 18'dir ve en kısa turun uzunluğuna eşittir. Şekil 10.13'de görüldüğü gibi her şehrin seçtiği iki kenar birlikte gerçek bir tur oluşturur. Gevşetmenin çözümü olurlu çıkmıştır; bu yüzden sınır sıkıdır. Kökte sınır optimuma eşit olduğu için, ilk tam tur bulunur bulunmaz kalan bütün dallar alt ≥ enIyi koşuluyla budanır. Kısmi yollarda aynı fikir, yoldaki kenarlar sabitlenerek uygulanır. Yoldaki bir şehrin kenarlarından biri ya da ikisi zaten bellidir. En kısa kenarlar yalnız eksik kalanlar için aranır.

10.4.5İndirgenmiş maliyet matrisi

Üçüncü bir alt sınır, maliyet matrisinin satır ve sütunlarına bakar. Fikir şudur. Her tur, matrisin her satırından tam bir hücre (bir şehirden çıkış) ve her sütunundan tam bir hücre (bir şehre giriş) kullanır. Bir satırın bütün hücrelerinden aynı sayı çıkarılırsa her turun maliyeti tam o sayı kadar azalır. Turların sıralaması değişmez. Satırlardan ve sütunlardan çıkarılan sayıların toplamı, her turun maliyetinden düşülmüştür. Kalan matris negatif olmadığı için bu toplam bir alt sınırdır.

İşlem şöyle yapılır. Köşegen ∞ yapılır; bir şehirden kendine gidilmez. Her satırdan o satırın en küçüğü çıkarılır. Ardından her sütundan o sütunun en küçüğü çıkarılır. Sonuçta her satırda ve her sütunda en az bir 0 bulunur. Bu matrise indirgenmiş maliyet matrisi (reduced cost matrix) denir.

int indirge(int[][] m) {
  int toplam = 0;
  for (int i = 0; i < n; i++) {       // satırlar
    int mn = satirMin(m, i);
    if (mn > 0 && mn < INF) {
      satirdanCikar(m, i, mn); toplam += mn;
    }
  }
  for (int j = 0; j < n; j++) {       // sütunlar
    int mn = sutunMin(m, j);
    if (mn > 0 && mn < INF) {
      sutundanCikar(m, j, mn); toplam += mn;
    }
  }
  return toplam;
}

satirMin, satirdanCikar, sutunMin ve sutundanCikar basit yardımcı metotlardır. Çıkarma yalnız ∞ olmayan hücrelere uygulanır. mn > 0 koşulu sıfır çıkarmayı atlar. mn < INF koşulu ise bütünüyle ∞ olan satır ve sütunları atlar; dallanmada bu tür satırlar oluşur. Metot matrisi yerinde değiştirir ve çıkarılan toplamı döndürür. İki geçiş de O(n²) sürer.

Satır indirgemesi bittiğinde toplam 12'dir. Bu sayı en ucuz çıkış kenarı sınırının aynısıdır; satır en küçükleri tam olarak enKucuk değerleridir. Sütun adımı yeni bilgi katar. Satır indirgemesinden sonra sütun 3'te hiç 0 yoktur: her şehrin en ucuz çıkışı 3'e gitmez. Oysa bir turda 3'e mutlaka girilir ve bu giriş en az 2 tutar. Sütun adımı “her şehre bir kez girilir” kısıtını da sınıra katar ve sınırı 14'e çıkarır. Tablo 10.13 indirgenmiş matrisin son hâlidir.

Bu yöntemle dallanma bir kenar seçerek yapılır. Ebeveyn düğümün indirgenmiş matrisinde i → j kenarı seçilsin. Çocuğun matrisi şöyle kurulur. i satırının ve j sütununun bütün hücreleri ∞ yapılır: i'den başka bir çıkış ve j'ye başka bir giriş olamaz. (j, i) hücresi de ∞ yapılır; j'den hemen i'ye dönmek erken kapanan bir döngü oluşturur. Matris yeniden indirgenir. Çocuğun sınırı şöyle hesaplanır:

sınır(çocuk) = sınır(ebeveyn) + indirgenmiş c[i][j] + yeni indirgemenin toplamı

İndirgenmiş matris yöntemi, Little ve arkadaşlarının 1963'te yayımladığı makaleye dayanır. Yöntemin önemli bir üstünlüğü vardır: simetri gerektirmez. d[i][j] ≠ d[j][i] olan asimetrik problemlerde de geçerlidir. Tek yönlü yollar ya da yokuş yukarı ve aşağı farklı yakıt harcayan araçlar asimetrik problemlere örnektir. İki en kısa kenar sınırı ise simetriye dayanır; asimetrik problemde doğrudan kullanılamaz.

10.4.6Üç sınırın karşılaştırması

Aynı dört şehirli örnekte üç alt sınır kökte üç farklı değer verir (Şekil 10.14).

Sıkı sınır daha çok budar ama her düğümde daha pahalıdır. En ucuz çıkış sınırı enKucuk dizisi sayesinde O(n)'de hesaplanır. Öbür ikisi her düğümde matrisin tamamına bakar. Sıralama her örnekte aynı olmak zorunda değildir. İndirgenmiş matris sınırı ile iki en kısa kenar sınırı farklı bilgileri kullanır ve başka bir örnekte sıraları değişebilir. En ucuz çıkış sınırı ise ikisinden de büyük olamaz. İndirgemenin satır adımı tek başına onu verir. İki kenar sınırında da her şehrin iki kenarının ortalaması en ucuz kenarından küçük değildir.

Büyük örneklerde daha da sıkı sınırlar kullanılır. 1-ağaç sınırı, bir şehir dışarıda bırakılarak kalanlar için minimum kapsayan ağaç kurar ve dışarıdaki şehri en kısa iki kenarıyla bağlar. Her tur bir 1-ağaçtır; bu yüzden en küçük 1-ağaç geçerli bir alt sınırdır. Doğrusal programlama gevşetmesi ise bugün binlerce şehirli örnekleri kesin çözen yazılımların temelidir. Hangi sınırın seçileceği, budanan düğüm sayısı ile düğüm başına yapılan iş arasındaki dengeye göre belirlenir.

10.4.7Daha büyük örnek: 6 şehir

Dört şehirli örnekte budamanın etkisi sınırlıdır; tam ağaç zaten küçüktür. Etkiyi görmek için altı şehirli simetrik bir örnek alınır (Tablo 10.15).

Kökün en ucuz çıkış sınırı 16 + 15 + 14 + 12 + 12 + 18 = 87'dir. En kısa tur 0 → 1 → 2 → 3 → 5 → 4 → 0'dır: 29 + 15 + 15 + 18 + 22 + 16 = 115. Aynı uzunlukta başka turlar da vardır; arama ilk bulduğunu saklar. Kök sınırı ile optimum arasındaki fark büyüktür (87 ile 115); en ucuz çıkış sınırı bu örnekte gevşektir.

Budamasız arama, durum uzayı ağacının bütün düğümlerini üretir: 1 + 5 + 20 + 60 + 120 + 120 = 326. Son düzeydeki 120 düğüm, (6 − 1)! = 120 turun her biridir. Sınırlı arama 210 düğüm üretir; yani 210 kez altSinir hesaplanır (kök dahil). Bunların yalnız 130'unda dala girilir ve tsp çağrılır. Çağrı sayısı 326'dan 130'a, yani yaklaşık beşte ikisine iner. Daha sıkı bir sınır bu sayıları belirgin biçimde düşürür. Örneğin iki en kısa kenar sınırı bu matriste kökte 100,5 verir; 87'den çok daha yakındır.

10.5Atama problemi

Atama problemi, dal sınırın en küçükleme yönünü küçük ve kolay izlenen bir örnekte göstermek için uygundur. Kod yapısı gezgin satıcı aramasına çok benzer; sınır ise daha da basittir.

10.5.1Problem ve alt sınır

Her atama, işlerin bir permütasyonudur; n! olası atama vardır. Durum uzayı ağacının i. düzeyinde i. kişiye henüz kimseye verilmemiş bir iş seçilir. Kök hiçbir kişiye iş verilmemiş durumdur; yapraklar tam atamalardır.

Alt sınır şu gözleme dayanır: henüz iş verilmemiş her kişi, en az kendi satırının en küçük maliyetini öder. Bu bir gevşetmedir. “Her işe tek bir kişi” kısıtı kaldırılmıştır; iki kişi aynı ucuz işi seçebilir. İş çakışmaları yok sayıldığı için sınır gerçek maliyetin üstüne çıkamaz. Sınırı her düğümde hızlı hesaplamak için satır en küçüklerinin sonek toplamları önceden tutulur:

kalanMin[i] = Σ_{r ≥ i} min_j c[r][j],   kalanMin[n] = 0

i. kişiye iş verildikten sonra yolun maliyeti yeni ise o düğümün alt sınırı yeni + kalanMin[i + 1]'dir. Hesap O(1) sürer. alt ≥ enIyi ise dal kesilir.

Örnekte satır en küçükleri 4, 3, 2'dir. Sonek toplamları kalanMin = [9, 5, 2, 0] olur. Kökün alt sınırı 9'dur: hangi atama yapılırsa yapılsın toplam 9'un altına inemez.

Atama probleminin polinom zamanlı bir algoritması da vardır: Macar yöntemi (Hungarian method) problemi O(n³) sürede çözer. Bu yüzden saf atama problemi için dal sınır gerekmez; burada yöntemi göstermek için kullanılır. Ek kısıtlı türevlerde ise durum değişir. Örneğin bazı işler aynı kişiye ya da birbirine bağlı iki kişiye verilemiyorsa Macar yöntemi doğrudan uygulanamaz. Bu tür problemlerde dal sınır gerçekten gerekir. Dallanmada Macar yönteminin sonucu da alt sınır olarak kullanılabilir.

10.5.2Kod izleme: ata(0, 0)

void ata(int i, int maliyet) {
  if (i == n) {                     // tam atama
    enIyi = Math.min(enIyi, maliyet);
    return;
  }
  for (int j = 0; j < n; j++) {
    if (kullanildi[j]) continue;
    int yeni = maliyet + c[i][j];
    if (yeni + kalanMin[i + 1] >= enIyi)
      continue;                     // sınır
    kullanildi[j] = true;
    ata(i + 1, yeni);
    kullanildi[j] = false;          // geri al
  }
}

Metodun yapısı tsp metoduyla aynıdır. i sıradaki kişi, maliyet o ana kadar yapılan atamaların toplamıdır. kullanildi dizisi verilmiş işleri işaretler; olursuzluk kuralı budur. Sınır testi kısmi atamaya iş eklemeden önce yapılır. Dal kesilirse kullanildi hiç değişmez; bu yüzden geri alma gerekmez. Taban durumda Math.min ile enIyi güncellenir.

İzlemenin özü şudur. İlk tam atama (iş 0, 1, 2) 13 tutar ve enIyi olur. Ardından üç dal, sınırı 13'e eşit olduğu için kesilir. 5. adımdaki kesme önemlidir: k0 → iş 1 dalının altında iki tam atama vardır ve hiçbiri denenmez. 6. adımda k0 → iş 2 dalı sınırı 9 ile açılır. Bu dalda k1 → iş 1 ve k2 → iş 0 atamaları 4 + 3 + 2 = 9 verir. Sonuç kökün alt sınırına eşittir; daha iyi bir atama olamayacağı bu eşitlikten hemen anlaşılır.

Arama toplam 7 çağrı yapmıştır: ata(0, 0), üç ara düğüm ve iki tam atama ile birlikte. Budamasız arama 3! = 6 atamanın hepsini gezer; bunun için 1 + 3 + 6 + 6 = 16 çağrı gerekir. Dört kişilik bir örnekte fark daha büyüktür. Tablo 10.19'teki matriste satır en küçükleri 3, 2, 3, 2'dir ve kökün alt sınırı 10'dur.

En iyi atama k0 → iş 3 (4), k1 → iş 2 (2), k2 → iş 0 (4), k3 → iş 1 (2) olup toplamı 12'dir. Dal sınır 21 çağrıda yalnız 4 tam atamaya ulaşır. Budamasız arama 4! = 24 tam atamanın hepsini dener ve 65 çağrı yapar.

10.6Tam sayılı doğrusal programlama

Dal sınırın endüstrideki en yaygın kullanımı tam sayılı doğrusal programlamadır. Yöntem bu alanda 1960'ta Land ve Doig'in makalesiyle ortaya konmuştur. Bugün üretim planlama, çizelgeleme ve dağıtım problemlerini çözen ticari yazılımlar aynı fikrin gelişmiş sürümlerini kullanır.

10.6.1Problem ve LP gevşetmesi

Tam sayı koşulu olmasaydı problem sıradan bir doğrusal program (linear program, LP) olurdu. Doğrusal programlar simpleks yöntemiyle pratikte çok hızlı, iç nokta yöntemleriyle de polinom sürede çözülür. İki değişkenli küçük örneklerde çözüm grafikle bulunur: kısıtlar düzlemde bir çokgen (olurlu bölge) tanımlar ve en iyi değer bu çokgenin köşelerinden birinde elde edilir. Tam sayı koşulu ise problemi NP-zor yapar.

Dal sınır bu iki gerçeği birleştirir:

• Sınır: Tam sayı koşulu kaldırılır ve LP gevşetmesi (LP relaxation) çözülür. Gevşetmenin olurlu bölgesi bütün tam sayı noktaları içerir. Bu yüzden en büyüklemede LP optimumu, ILP optimumu için bir üst sınırdır.
• Dallanma: LP çözümünde bir değişken kesirliyse, örneğin y = 1,5 ise, iki alt problem kurulur: birine y ≤ 1, öbürüne y ≥ 2 kısıtı eklenir. Aradaki kesirli bölge 1 < y < 2 atılır. Bu bölgede tam sayı nokta olmadığı için hiçbir tam sayı çözüm kaybolmaz.
• Tamlık: Bir düğümün LP çözümü zaten tam sayıysa o düğümün altında daha iyi bir tam sayı çözüm yoktur. Bu çözüm bir aday olur ve düğüm kapanır.

Örnek problem şudur:

en büyük Z = 5x + 4y;   6x + 4y ≤ 24,   x + 2y ≤ 6,   x, y ≥ 0 tam sayı

LP gevşetmesinin optimumu iki kısıt doğrusunun kesişimindedir. 6x + 4y = 24 ve x + 2y = 6 birlikte çözülür. İkinci denklem 2 ile çarpılıp birinciden çıkarılınca 4x = 12, yani x = 3 bulunur; buradan y = 1,5 çıkar. Değer Z = 15 + 6 = 21'dir. Öbür köşeler (0; 0), (4; 0) ve (0; 3)'tür; değerleri 0, 20 ve 12'dir. Şekil 10.16 bölgeyi ve iki optimumu gösterir.

10.6.2LP gevşetmeleriyle dallanma

Dal sınır ağacı adım adım şöyle kurulur:

1. Kök. LP optimumu (3; 1,5), Z = 21. Bu değer üst sınırdır: hiçbir tam sayı çözüm 21'i geçemez. y kesirlidir; y üzerinde dallanılır.
2. Dal y ≤ 1. Yeni LP'de y = 1 sınırına dayanılır. 6x + 4 ≤ 24'ten x ≤ 3,33, x + 2 ≤ 6'dan x ≤ 4 gelir. LP optimumu (3,33; 1), Z = 20,67'dir. x kesirlidir; x ≤ 3 ve x ≥ 4 dalları açılır.
3. Dal y ≤ 1, x ≤ 3. LP optimumu (3; 1), Z = 19. Çözüm tam sayıdır: ilk aday, enIyi = 19.
4. Dal y ≤ 1, x ≥ 4. 6 · 4 + 4y ≤ 24 kısıtı y = 0'ı zorlar. LP optimumu (4; 0), Z = 20. Tam sayıdır ve 20 > 19: enIyi = 20.
5. Dal y ≥ 2. x + 2y ≤ 6 kısıtı x ≤ 2'yi zorlar. LP optimumu (2; 2), Z = 18. 18 ≤ 20 olduğu için dal budanır. Bu dalın LP çözümü tam sayı olsa bile enIyi'yi geçemez.

Optimum x = 4, y = 0, Z = 20'dir. Bu örnek, LP çözümünü yuvarlamanın neden yetmediğini de gösterir. (3; 1,5) aşağı yuvarlanırsa (3; 1) elde edilir ve Z = 19 olur; en iyi değildir. Yukarı yuvarlanırsa (3; 2) elde edilir: 6 · 3 + 4 · 2 = 26 > 24, olursuzdur. Gerçek optimum (4; 0) LP noktasının yakınında değildir; ancak dallanmayla bulunur.

İkinci bir örnek tamlık kuralını gösterir: en büyük Z = 3x + 2y; x + y ≤ 4, x ≤ 3, y ≤ 2. Kaba kuvvet 0 ≤ x ≤ 3, 0 ≤ y ≤ 2 ızgarasındaki 12 noktanın hepsini dener ve (3; 1) noktasında Z = 11'i bulur. LP gevşetmesinin optimumu da (3; 1)'dir: x sınırına (3) ve x + y ≤ 4 doğrusuna dayanan köşe. Çözüm zaten tam sayı olduğu için dal sınır kökte biter; tek bir LP çözülmüştür.

Gerçek yazılımlar bu temel şemayı birkaç yönde geliştirir. Hangi kesirli değişkende dallanılacağı akıllıca seçilir. LP gevşetmesine, tam sayı noktaları kesmeden kesirli çözümü dışarıda bırakan ek kısıtlar (kesme düzlemleri) eklenir. Bu birleşime dal ve kesme (branch and cut) denir. Ayrıca bir alt problemin LP'si, ebeveynin çözümünden başlanarak birkaç adımda yeniden çözülür.

10.7Maksimum klik

Son uygulama bir çizge problemidir. Klik problemi sosyal ağlarda sıkı bağlı grupları, biyolojide birbirleriyle etkileşen protein kümelerini ve kodlama kuramında hata düzelten kodları bulmakta kullanılır.

10.7.1Problem ve sınır

Problem NP-zordur. Arama, mevcut kliği K adım adım büyütür. K'ye eklenebilecek düğümlere aday denir. Bir düğüm aday olabilmek için K'deki bütün düğümlere komşu olmalıdır. Aynı kliğin farklı sıralarla tekrar tekrar üretilmesini önlemek için düğümler artan numara sırasıyla eklenir: K'ye son eklenen düğümden büyük numaralı düğümler aday olabilir.

Sınır en büyükleme sınırıdır ve çok basittir. K en iyi durumda bütün adaylarla büyür. Bu yüzden bu dalda bulunabilecek en büyük klik |K| + |aday| düğümü geçemez. |K| + |aday| ≤ |enİyi| ise mevcut klik ne kadar büyütülse de enIyi'yi geçemez; dal budanır. Sınır geçerlidir, çünkü dal içindeki her klik K ile adayların bir alt kümesinin birleşimidir.

void klik(List<Integer> K, int bas) {
  if (K.size() > enIyi.size())
    enIyi = new ArrayList<>(K);
  List<Integer> aday = new ArrayList<>();
  for (int v = bas; v < n; v++)
    if (uygun(v, K)) aday.add(v);  // K'ye komşu
  if (K.size() + aday.size() <= enIyi.size())
    return;                        // sınır
  for (int v : aday) {
    K.add(v);
    klik(K, v + 1);
    K.remove(K.size() - 1);        // geri al
  }
}

Metodun satırları şöyle çalışır:

• İlk iki satır enIyi'yi günceller. Bir klik her an olurlu bir çözümdür; yaprağa inmek gerekmez. new ArrayList<>(K) bir kopya üretir, çünkü K aramanın geri kalanında değişir.
• for döngüsü adayları toplar. uygun(v, K), v'nin K'deki her düğüme komşu olup olmadığına bakar. Döngü bas'tan başlar; daha küçük numaralar zaten denenmiştir.
• if (K.size() + aday.size() <= enIyi.size()) return; sınır kuralıdır.
• Son döngü dallanmadır. Her aday sırayla K'ye eklenir, arama v + 1'den sürer ve aday geri çıkarılır.

Bir çağrıda aday listesi O(n · |K|) sürede kurulur; komşuluk bir matriste tutulursa her uygun denetimi O(|K|)'dir. Sınır satırı olmadan metot sıradan bir geri izlemedir ve bütün klikleri gezer.

10.7.2Kod izleme: klik({}, 0)

Arama boş klik ve bas = 0 ile başlar. Tablo 10.20 çağrıları sırayla verir.

İlk beş çağrı hep ilk adayı ekleyerek derine iner ve 6. çağrıda beş düğümlü kliğe ulaşır. Bu, tam çizgenin en büyük kliğidir. Bundan sonra açılan her dalın sınırı en fazla 5'tir ve hepsi hemen budanır. Örneğin 8. çağrıda K = {0, 1, 3}'tür; aday yalnız 4'tür. En iyi durumda dört düğümlü bir klik elde edilir ve bu 5'i geçemez. Kökte kalan adaylar 1–5 de tek tek denenir ve hepsi aynı biçimde kesilir. Örneğin K = {3} iken adaylar 4 ve 5'tir. 3, 4, 5 bir üçgen oluşturur ama sınır 1 + 2 = 3 ≤ 5'tir.

Sonuç {0, 1, 2, 3, 4}'tür. Sınırlı arama 17 çağrı yapar. Sınır satırı silinince arama bütün klikleri gezer ve 36 çağrı yapar. Bu sayı, boş küme dahil çizgedeki kliklerin sayısıdır: tam beşli kısımda 2⁵ = 32 klik, düğüm 5'i içeren {5}, {3, 5}, {4, 5}, {3, 4, 5} dört klik.

10.7.3Daha sıkı sınır: boyama

|K| + |aday| sınırı her adayın kliğe girebileceğini varsayar. Adaylar arasında komşu olmayan çiftler varsa bu varsayım çok iyimserdir. Daha sıkı bir sınır çizge boyamadan gelir. Bir kliğin her düğüm çifti komşudur; bu yüzden bir klikteki düğümlerin hepsi farklı renk almak zorundadır. Adaylar k renkle düzgün boyanabiliyorsa, adaylardan en çok k düğüm aynı kliğe girebilir. Yeni sınır şöyledir: |K| + renk(aday) ≤ |enİyi| ise dal budanır.

En az renk sayısını bulmak da NP-zordur. Ama en iyi boyama gerekmez. Açgözlü boyama düğümleri sırayla gezer ve her düğüme komşularında kullanılmamış en küçük rengi verir. O(aday²) sürer. Fazla renk kullanabilir; bu yalnız sınırı gevşetir, geçersiz kılmaz. Sınır yine de |aday|'dan büyük olamaz, çünkü her düğüm en kötü durumda kendi rengini alır.

Şekil 10.20'teki örnekte adaylar beş düğümlü bir halka oluşturur; K boştur ve |enİyi| = 3'tür. Eski sınır 0 + 5 = 5 > 3 verir ve dal açılır. Açgözlü boyama 0'a renk 1, 1'e renk 2, 2'ye renk 1, 3'e renk 2 verir. 4 hem 3'e hem 0'a komşudur; renk 3'ü alır. Renk sınırı 0 + 3 ≤ 3 verir ve dal budanır. Halkadaki en büyük klik zaten yalnız 2 düğümlüdür. En hızlı kesin klik algoritmalarının çoğu bu fikre dayanır. Tomita'nın MCQ ve MCS algoritmaları adayları renk sırasıyla dener ve renk sınırıyla budar.

10.8Diğer problemler ve A* ile ilişki

10.8.1Dal sınırla çözülen diğer problemler

Yöntem, çözümü bir dizi kararla kurulan hemen her optimizasyon problemine uygulanabilir. Her uygulamada sorulacak iki soru aynıdır: dallanma nasıl yapılır ve hangi gevşetme geçerli bir sınır verir?

• Hamilton yolu. Her düğümü tam bir kez ziyaret eden yol aranır. Ağırlıklı sürümü gezgin satıcıya çok benzer ve benzer sınırlarla çözülür.
• Boole sağlanabilirlik (SAT). Değişkenlere doğruluk değeri atanır; çelişen kısmi atamalar budanır. Bu, DPLL algoritmasının özüdür. En büyük SAT sürümünde, mümkün olduğu kadar çok tümcenin doğru olması istenir; sınır, kalan atamalarla sağlanabilecek en fazla tümce sayısıdır.
• Çizelgeleme. İşler makinelere dağıtılır; en büyük yük (makespan) ya da toplam gecikme en küçüklenir. Alt sınır, kalan işlerin en iyi durumda yaratacağı yüktür; örneğin kalan iş toplamının makinelere eşit bölünmesi.
• Kutu paketleme. Eşyalar en az sayıda kutuya yerleştirilir. Alt sınır ⌈Σ boyut / kutu kapasitesi⌉'dir: kutular kusursuz doldurulsa bile bu kadar kutu gerekir.
• Maksimum kapsama. En fazla öğeyi kapsayan k küme seçilir. Üst sınır, kalan en büyük kümelerin ekleyebileceği öğe sayısıdır.
• Atama problemi ve ek kısıtlı türevleri. Alt sınır, atanmamış her satırın en küçük maliyetidir.

Dal sınır NP-zor problemler için anlamlıdır. Maksimum akış, en kısa yol ya da minimum kapsayan ağaç gibi polinom zamanlı algoritması bilinen problemlerde dal sınıra gerek yoktur. Bu problemlerde polinom algoritma her zaman tercih edilir; dal sınır en kötü durumda üstel sürer.

10.8.2Dal sınır, A* ve derinlik öncelikli dal sınır

En iyi önce dal sınır ile yol bulmadaki A* algoritması aynı fikrin iki yüzüdür. Tablo 10.21 üç yakın yöntemi karşılaştırır.

A*, ağırlıklı bir çizgede yol arayan LC dal sınırdır. g(x) başlangıçtan x'e ödenen maliyettir; LC aramadaki f(x)'in karşılığıdır. h(x) ise x'ten hedefe kalan maliyetin bir alt sınırıdır; ĝ(x)'in karşılığıdır. 8 bulmacasındaki yanlış taş sayısı böyle bir tahmindir. h kabul edilebilirse, kuyruktan çıkarılan ilk hedef düğüm en kısa yolu verir. Gerekçe dal sınırdakiyle aynıdır. O hedefin maliyeti, kuyruktaki her düğümün f değerinden küçük ya da ona eşittir. f değerleri ise o düğümlerden geçen her yolun alt sınırıdır.

Derinlik öncelikli dal sınır, belleğin kısıtlı olduğu durumların yöntemidir. Bellek derinlikle sınırlıdır ve aramanın her anında elde bir çözüm bulunur. Bedeli, kötü bir dala girildiğinde iyi çözümün geç bulunmasıdır. İkisinin arası da vardır. IDA* (iterative deepening A*), derinlik öncelikli aramayı bir f eşiğiyle çalıştırır. Eşiği aşan düğümleri keser ve arama başarısız olursa eşiği yükseltip yeniden başlar. Bellek derinlikle sınırlı kalır, en iyi önce aramanın sırası da büyük ölçüde korunur.

10.9Tasarım paradigmalarının karşılaştırması

Dal sınır, algoritma tasarım paradigmaları arasında en son ele alınanlardandır ve ötekilerin bazı fikirlerini birleştirir. Tablo 10.22 altı paradigmayı aynı ölçütlerle yan yana koyar.

Bir problem için paradigma seçerken sorular belli bir sırayla sorulur. Alt problemler bağımsız mı? Öyleyse böl ve fethet uygundur. Alt problemler örtüşüyor ve sayıları polinom mu? Dinamik programlama uygundur. Yerel en iyi seçim küresel en iyiye götürüyor ve bu kanıtlanabiliyor mu? Açgözlü yaklaşım uygundur. Bunların hiçbiri yoksa ve problem NP-zorsa iki seçenek kalır. Kesin sonuç isteniyorsa geri izleme ya da dal sınır kullanılır. Polinom sürede, kalitesi garantili ama yaklaşık bir sonuç yetiyorsa yaklaşım algoritmasına başvurulur.

Aynı problem birden çok paradigmayla çözülebilir. 0/1 sırt çantası buna iyi bir örnektir. Dinamik programlama onu O(nW)'de çözer; kapasite küçükse en iyi seçimdir. Kapasite çok büyükse ya da ağırlıklar kesirliyse dal sınır öne çıkar. Açgözlü yöntem ise 0/1 sürümde en iyiyi garanti etmez; yalnız kesirli sürümde doğrudur. Dal sınır bu açgözlü yöntemi bir sınır hesabı olarak içine alır. Paradigmalar birbirine rakip değildir; çoğu zaman birbirinin içinde parça olarak kullanılır.

10.10Sık yapılan hatalar

• Geçersiz (kötümser) sınır kullanmak. Sırt çantasında yalnız tam sığan eşyaların kazancını toplamak bir üst sınır değildir; bir olurlu çözümün değeridir. Optimumu içeren dal budanabilir ve algoritma hata vermeden yanlış sonuç döndürür.
• Yönü karıştırmak. En büyüklemede sinir ≤ enİyi, en küçüklemede alt ≥ enİyi ise budanır. Tersini yazmak ya optimumu kaçırır ya da hiç budamaz. En küçüklemede enIyi'nin başta +∞, en büyüklemede −∞ ya da 0 olması gerektiği de unutulmamalıdır.
• Kuyruktan çıkınca tekrar sınamamak. Düğüm eklendiğinde umut vaat ediyordu. Beklerken enIyi büyüdüyse artık gereksizdir. Sırt çantası örneğinde C ve G böyle düğümlerdir. Tekrar sınama olmazsa sonuç değişmez ama gereksiz düğümler genişletilir.
• Eşyaları sıralamamak. Kesirli sınır, eşyalar p_i/w_i oranına göre azalan sırada değilse geçerli bir üst sınır vermeyebilir.
• enIyi'yi yalnız yapraklarda güncellemek. Sırt çantasında ve klikte her olurlu düğüm bir çözümdür. Erken güncelleme enIyi'yi hızla yükseltir ve daha çok budama sağlar.
• Dal sınırı geri izlemeyle aynı sanmak. Sınır testi içermeyen kod, örneğin budamasız TSP araması, dal sınır değildir; bütün ağacı gezer.
• Geri almayı unutmak. Özyinelemeli sürümlerde ziyaret[s] = false, kullanildi[j] = false ya da K.remove(...) satırı unutulursa sonraki dallar yanlış durumla çalışır ve olurlu çözümler kaybolur.
• enIyi'yi kopyalamadan saklamak. Klik aramasında enIyi = K yazmak, değişmeye devam eden listeyi saklar. Arama bittiğinde enIyi boş liste gösterir. Kopya (new ArrayList<>(K), yol.clone()) şarttır.

10.11Özet

• Dal sınır, optimizasyon problemlerinin çözüm uzayını bir durum uzayı ağacı olarak gezer. Döngü şöyledir: bir canlı düğüm seçilir, sınırı tekrar sınanır, düğüm dallanır, çocukların sınırı hesaplanır ve umutsuz olanlar budanır. enIyi, o ana kadar bulunan en iyi tam çözümün değerini tutar.
• Sınır geçerli (iyimser), sıkı ve ucuz olmalıdır. Geçerlilik zorunludur; sıkılık ve ucuzluk verimliliği belirler. Sınır çoğunlukla gevşetmeyle kurulur. En büyüklemede üst, en küçüklemede alt sınır kullanılır.
• Düğüm üç nedenle budanır: olursuzluk, yetersiz sınır (sinir ≤ enİyi ya da alt ≥ enİyi) ve tamlık (yaprak ya da tam sayı çıkan LP çözümü). Dal sınırı geri izlemeden ayıran sınır kuralıdır.
• FIFO genişlik öncelikli gezer ve kuyruk kullanır. LIFO derinlik öncelikli gezer, yığın ya da özyineleme kullanır ve az bellek ister. LC (en iyi önce) öncelikli kuyrukla en umut verici düğümü seçer ve çoğunlukla en az düğümü üretir. Üçü de aynı optimumu bulur.
• Sırt çantasında kesirli sırt çantası gevşetmesi üst sınır verir. Örnekte sinir(kök) = 115, optimum 90'dır. En iyi önce 31 düğümün 11'ini, FIFO ve LIFO 13'ünü üretir.
• Gezgin satıcıda en ucuz çıkış kenarı sınırı, yolun maliyetine son şehrin ve gidilmemiş şehirlerin en ucuz çıkışlarını ekler. Dört şehirde 16 düğüm yerine 10 düğüm üretilir. İndirgenmiş matris (14) ve iki en kısa kenar (18) daha sıkıdır ama düğüm başına O(n²) sürer.
• Atamada alt sınır, kalan kişilerin satır en küçüklerinin toplamıdır. Tam sayılı programlamada LP gevşetmesi üst sınır verir ve kesirli bir değişkende iki alt probleme dallanılır. Klikte |K| + |aday| ≤ |enİyi| sınırı kullanılır; boyama daha sıkı bir sınır verir.
• Yöntem en kötü durumda üsteldir. Pratikteki başarısı sınırın kalitesine bağlıdır. Polinom algoritması olan problemlerde kullanılmaz.
• Bağımsız alt problemler böl ve fethete, örtüşen alt problemler dinamik programlamaya, kanıtlı açgözlü seçim açgözlü yaklaşıma götürür. NP-zor bir problemde kesin sonuç için geri izleme ya da dal sınır kullanılır.

10.12Kavram listesi

• dal sınır branch and bound
• dallanma branching
• sınır bound
• budama pruning
• durum uzayı ağacı state-space tree
• olurlu feasible
• gevşetme relaxation
• üst sınır upper bound
• en iyi önce arama best-first search
• en düşük maliyetli (LC) arama least-cost search
• derinlik öncelikli dal sınır depth-first branch and bound
• kabul edilebilir sezgisel admissible heuristic
• A* algoritması A* search
• geri izleme backtracking
• 0/1 sırt çantası 0/1 knapsack
• kesirli sırt çantası fractional knapsack
• gezgin satıcı problemi travelling salesman problem
• indirgenmiş maliyet matrisi reduced cost matrix
• atama problemi assignment problem
• Macar yöntemi Hungarian method
• tam sayılı doğrusal programlama integer linear programming
• LP gevşetmesi LP relaxation
• maksimum klik maximum clique
• çizge boyama graph coloring
• NP-zor NP-hard

10.13Kendini Dene

1. Eşyalar (p, w) = (30, 3), (40, 5), (45, 9), (10, 4) ve W = 12 olsun. Kökün kesirli üst sınırı nedir? En iyi önce dal sınır hangi düğümleri genişletir, kaç düğüm üretir ve optimum nedir?

   Cevap

   Oranlar 10, 8, 5, 2,5'tir; eşyalar sıralıdır. Kökte eşya 1 ve 2 tam sığar (70, ağırlık 8); eşya 3'ün 4/9'u alınır: 4 · 45/9 = 20. sinir(kök) = 90. Kök genişletilir: B (eşya 1 alındı) 30/3, sınır 90, enIyi = 30; C (eşya 1 yok) sınır 40 + 7 · 5 = 75. B genişletilir: D 70/8, sınır 90, enIyi = 70; E 30/3, sınır 75. D genişletilir: “al” çocuğu 115/17 olursuzdur; G (eşya 3 yok) 70/8, sınır 70 + 10 = 80. G genişletilir: H (eşya 4 alındı) 80/12, enIyi = 80; H'nin sınırı 80'dir ve kuyruğa girmez. I (eşya 4 yok) sınır 70, budanır. Kuyruktaki E (75) ve C (75) atılır. 4 genişletme (A, B, D, G), 9 düğüm. Optimum 80'dir: eşya 1, 2 ve 4.

2. Aynı örnek FIFO kuyrukla çözülürse kaç düğüm üretilir, kaç düğüm genişletilir? Fark nereden gelir?

   Cevap

   FIFO 13 düğüm üretir ve 6 düğüm genişletir: A, B, C, D, E ve G'nin karşılığı olan düğüm. Sonuç yine 80'dir. FIFO, C'yi (sınır 75) düzey sırasıyla erkenden genişletir; o anda enIyi yalnız 70'tir ve C atılamaz. E de genişletilir; çocuğu 75/12 olursuz değildir ve enIyi'yi 75'e çıkarır. En iyi önce ise C ve E'yi sona bırakır; o sırada enIyi 80 olmuştur ve ikisi de atılır.

3. Simetrik uzaklıklar d(0,1) = 10, d(0,2) = 15, d(0,3) = 20, d(1,2) = 35, d(1,3) = 25, d(2,3) = 30 olsun. Kökte en ucuz çıkış kenarı, indirgenmiş matris ve iki en kısa kenar sınırları nedir? En kısa tur kaç birimdir?

   Cevap

   En ucuz çıkışlar 10, 10, 15, 20'dir: sınır 55. İndirgemede satır en küçükleri 10 + 10 + 15 + 20 = 55'tir. Satır indirgemesinden sonra sütun 2'de en küçük 5, sütun 3'te 10 kalır: sınır 55 + 5 + 10 = 70. İki en kısa kenar toplamları 25, 35, 45, 45'tir: 150 / 2 = 75. En kısa tur 0 → 1 → 3 → 2 → 0'dır: 10 + 25 + 30 + 15 = 80. Sıra yine en ucuz çıkış ≤ indirgenmiş matris ≤ iki kenar ≤ optimumdur. En ucuz çıkış sınırıyla tsp araması bu örnekte 16 düğümün 15'ini üretir; gevşek sınır neredeyse hiç budamaz.

4. Maliyet matrisi [[4, 7, 3], [2, 6, 1], [3, 9, 4]] olan atama problemi için kalanMin nedir? Optimum atama nedir ve ata(0, 0) kaç çağrı yapar?

   Cevap

   Satır en küçükleri 3, 1, 3'tür: kalanMin = [7, 4, 3, 0]; kökün alt sınırı 7'dir. Arama sırayla 14, 13 ve 11 maliyetli tam atamalar bulur. Optimum k0 → iş 1 (7), k1 → iş 2 (1), k2 → iş 0 (3) olup toplamı 11'dir. Arama 12 çağrı yapar; budamasız arama 16 çağrı yapar. Bu örnekte ilk dal (k0 → iş 0) kötü olduğu için budama geç başlar.

5. En büyük Z = 3x + 5y; x + 2y ≤ 7, 3x + y ≤ 9, x, y ≥ 0 tam sayı. LP gevşetmeleriyle dal sınır uygulanınca (önce y, sonra x kesirliyse onda dallanılarak) ağaç nasıl oluşur?

   Cevap

   Kök: iki doğrunun kesişimi (2,2; 2,4), Z = 18,6; y kesirlidir. Dal y ≤ 2: (2,33; 2), Z = 17; x kesirlidir. Onun altında x ≤ 2: (2; 2), Z = 16, tam sayı, enIyi = 16. x ≥ 3: (3; 0), Z = 9 ≤ 16, budanır. Dal y ≥ 3: (1; 3), Z = 18, tam sayı, enIyi = 18. Optimum x = 1, y = 3, Z = 18'dir. LP çözümünü aşağı yuvarlamak (2; 2) ve 16 verirdi.

6. Kenarları 0–1, 0–2, 0–3, 1–2, 1–3, 2–3, 3–4, 3–5, 4–5 olan çizgede en büyük klik nedir? klik metodu sınırla ve sınırsız kaç çağrı yapar?

   Cevap

   En büyük klik {0, 1, 2, 3}'tür (4 düğüm). Sınırlı arama 13, sınırsız arama 22 çağrı yapar. Sınırsız çağrı sayısı, boş küme dahil kliklerin sayısıdır: {0, 1, 2, 3}'ün 16 alt kümesi ile {4}, {5}, {3, 4}, {3, 5}, {4, 5}, {3, 4, 5}. Sınırlı aramada {0, 1, 2, 3} bulunduktan sonra örneğin K = {3}, aday = {4, 5} dalı 1 + 2 ≤ 4 ile kesilir.

7. Sırt çantası sınırında kesirli parça yerine kalan bütün eşyaların kazancı eklenirse sınır geçerli olur mu? W = 16 örneğinde kökte ne verir?

   Cevap

   Geçerlidir: hiçbir 0/1 çözüm, kalan eşyaların hepsini almaktan fazla kazandıramaz. Ama kapasiteyi hiç hesaba katmadığı için çok gevşektir. Kökte 40 + 30 + 50 + 10 = 130 verir; kesirli sınır 115'tir. Daha gevşek sınır daha az budar; sonuç doğru kalır ama daha çok düğüm üretilir.

8. En iyi önce sırt çantası kodunda karşılaştırıcı yanlışlıkla Double.compare(a.sinir, b.sinir) yazılırsa sonuç doğru kalır mı? Ne değişir?

   Cevap

   Sonuç doğru kalır. Budama kuralı ve sınır geçerli olduğu sürece hangi sırayla gezilirse gezilsin optimum kaybolmaz. Değişen sıradır: kuyruktan her adımda sınırı en küçük düğüm çıkar. Arama en umutsuz dallarla uğraşır ve enIyi geç yükselir. Bu yüzden daha çok düğüm genişletilir; strateji artık “en iyi önce” değil, “en kötü önce” olur.

10.14İleri okuma

• E. Horowitz, S. Sahni, S. Rajasekaran, Computer Algorithms (2. baskı, 2008), Bölüm 8: LC arama ve ĉ = f + ĝ maliyet fonksiyonu burada ayrıntılı işlenir. FIFO ve LC dal sınırın sırt çantası ve gezgin satıcı uygulamaları bu nottakine yakın bir dille verilir.
• A. Levitin, Introduction to the Design and Analysis of Algorithms (3. baskı, 2012), Bölüm 12.2: atama, sırt çantası ve gezgin satıcı için dal sınırı kısa ve görsel örneklerle anlatır; geri izlemeyle birlikte okunmaya uygundur.
• J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel, “An Algorithm for the Traveling Salesman Problem” (1963): “dal sınır” adını ilk kullanan ve indirgenmiş maliyet matrisi yöntemini tanıtan makale.
• R. Carraghan, P. M. Pardalos, “An Exact Algorithm for the Maximum Clique Problem” (1990): |K| + |aday| sınırına dayanan klasik klik algoritması; renk sınırlı sonraki algoritmaların başlangıç noktasıdır.

10.15Kaynaklar

1. R. Carraghan, P. M. Pardalos, “An Exact Algorithm for the Maximum Clique Problem”, Operations Research Letters 9(6), 1990.
2. E. Horowitz, S. Sahni, S. Rajasekaran, Computer Algorithms, 2. baskı, Silicon Press, 2008 (Bölüm 8: Branch-and-Bound).
3. A. H. Land, A. G. Doig, “An Automatic Method of Solving Discrete Programming Problems”, Econometrica 28(3), 1960.
4. A. Levitin, Introduction to the Design and Analysis of Algorithms, 3. baskı, Pearson, 2012 (Bölüm 12.2).
5. J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel, “An Algorithm for the Traveling Salesman Problem”, Operations Research 11(6), 1963.
6. R. Neapolitan, Foundations of Algorithms, 5. baskı, Jones & Bartlett, 2015 (Bölüm 6).

İlgili sayfalar: Bölüm 10 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.