Bölüm 11: Yaklaşım Algoritmaları

11.1Yaklaşım algoritmaları

Şimdiye kadar incelenen algoritmaların çoğu problemin en iyi çözümünü bulur. Sıralama algoritması diziyi tam olarak sıralar, en kısa yol algoritması gerçekten en kısa yolu verir. Bu algoritmaların hepsi polinom sürede çalışır: girdi iki katına çıktığında süre sabit bir katsayıyla büyür. Ne var ki uygulamada karşılaşılan birçok en iyileme probleminde böyle bir algoritma bilinmiyor. Bu problemlerde en iyi çözümü bulmanın bilinen tek yolu, olası çözümlerin çok büyük bir kısmını denemektir. Çözüm sayısı ise girdiyle birlikte üstel ya da faktöriyel hızla artar.

11.1.1Kesin çözüm neden pahalıdır?

Gezgin satıcı problemi (TSP), düğüm kapsama, makine çizelgeleme ve sırt çantası bu türden problemlerdir. Dördü de NP-zor problemler sınıfındadır. Karmaşıklık sınıflarını kısaca anımsamak yararlı olur. P, polinom sürede çözülebilen karar problemlerinin sınıfıdır. NP ise önerilen bir çözümün doğruluğu polinom sürede denetlenebilen karar problemlerinin sınıfıdır. Bir problem, NP'deki her problem ona polinom sürede indirgenebiliyorsa NP-zordur; hem NP-zor hem de NP'nin içindeyse NP-tamdır. P = NP olup olmadığı bilinmiyor, ama yaygın kanı ikisinin farklı olduğu yönündedir. P ≠ NP ise hiçbir NP-zor problem için polinom zamanlı kesin bir algoritma yoktur.

Bu sonucun pratik anlamı açıktır: yüz şehirlik bir rotanın ya da bin işlik bir çizelgenin en iyi çözümünü makul sürede garanti eden bir yöntem beklenmemelidir. Önde üç seçenek vardır. Küçük girdilerle yetinip üstel süre kabullenilebilir; dal sınır ve dinamik programlama bu süreyi azaltır ama ortadan kaldırmaz. Hızlı ama hiçbir şey vaat etmeyen bir sezgisel kullanılabilir. Üçüncü seçenek bu notun konusudur: polinom sürede çalışan ve sonucunun en iyiden ne kadar uzak olabileceğini kanıtla sınırlayan bir algoritma.

Tanımın üç parçası da önemlidir. Algoritma polinom sürede çalışır; aksi hâlde kesin çözüm aramaktan bir farkı kalmaz. Ürettiği çözüm uygundur, yani problemin bütün kısıtlarını sağlar: tur her şehre uğrar, çizelge her işi bir makineye verir, kapsama her kenarı kapsar. Son olarak çözümün kalitesi her girdi için kanıtlanmış bir sınırın içindedir. Birkaç denemede iyi sonuç vermesi yetmez. Algoritma en kötü girdide bile bu sınırı aşmamalıdır.

Bu bir takastır. Optimallikten biraz vazgeçilir; karşılığında hem verimlilik hem de çözüm kalitesi için bir güvence elde edilir. Hesaplama kaynakları, yani zaman ve bellek kısıtlı olduğunda bu takas çoğu zaman en akılcı seçimdir. Üstelik kanıtlanan oran bir en kötü durum sınırıdır. Pratikteki girdilerde yaklaşım algoritmalarının bulduğu çözümler çoğunlukla en iyiye bu sınırdan çok daha yakındır.

11.1.2Terazi benzetmesi

İki kefeli bir terazinin sol kefesinde 37 kilogramlık bir yük olsun. Sağ kefeye konabilecek ağırlıklar 20, 10, 5 ve 1 kilogramdır ve her biri yalnız bir kez kullanılabilir. Bu ağırlıklarla 37 kilogram tam olarak kurulamaz: hepsinin toplamı bile 36 kilogramdır. Elde edilebilecek en yakın denge 36 kilogramdır ve aradaki fark 1 kilogram, yani yükün yaklaşık %2,7'sidir.

Şekil 11.1 bu durumu gösterir. Benzetmenin taşıdığı fikir şudur: kesin dengeyi, yani optimumu aramak yerine hızlıca kurulan ve hatası sınırlı olan bir denge kabul edilir. Yaklaşım algoritması da bunu yapar. Bulduğu çözüm en iyi olmayabilir, ama aradaki farkın en fazla ne kadar olabileceği önceden bellidir. Terazide fark yükün %3'ünü geçmiyorsa “en fazla %3 hata” denebilir. Yaklaşım algoritmalarında bu sınır bir oranla ifade edilir.

11.1.3Yaklaşım oranı

Bir girdi için algoritmanın bulduğu çözümün maliyeti C, en iyi (optimal) çözümün maliyeti C* olsun. Problem bir en küçükleme problemiyse C ≥ C*'dır; en büyükleme problemiyse C ≤ C*'dır. İki durumu tek bir ölçüyle karşılaştırmak için büyük olan değer küçük olana bölünür.

Tanımdaki max iki durumu birleştirir. En küçüklemede C ≥ C* olduğu için büyük oran C / C*'dır ve koşul C ≤ ρ · C* biçimini alır. Algoritmanın bulduğu maliyet, en iyi maliyetin en fazla ρ katıdır. Örneğin 2-yaklaşım bir düğüm kapsama algoritması en fazla en küçük kapsamanın iki katı düğüm seçer. En büyüklemede C ≤ C* olduğu için büyük oran C* / C'dir ve koşul C ≥ C* / ρ olur. Algoritmanın bulduğu değer en iyi değerin en az 1/ρ'sidir. Örneğin 2-yaklaşım bir sırt çantası algoritması en iyi değerin en az yarısını garanti eder.

Şekil 11.2 iki durumu sayı doğrusunda gösterir. En küçüklemede C'nin bulunabileceği aralık [C*, ρ · C*], en büyüklemede [C* / ρ, C*]'dır. Şekildeki örnekte C* = 20 ve ρ = 2 alınmıştır. En küçükleme yapan bir algoritma 30 bulmuşsa oran bu girdi için 30 / 20 = 1,5'tir. En büyükleme yapan bir algoritma 15 bulmuşsa oran 20 / 15 ≈ 1,33'tür. İkisi de 2 sınırının içindedir.

Oranın n'ye bağlı yazılması bilinçlidir. Bazı algoritmaların oranı sabittir: düğüm kapsama için 2, metrik TSP için 1,5. Bazılarınınki girdiyle büyür: en yakın komşu sezgiselinin metrik TSP'deki oranı Θ(log n)'dir. Sabit oran çok daha güçlü bir garantidir. Girdi ne kadar büyürse büyüsün, algoritma en iyiden sabit bir kattan fazla uzaklaşmaz.

11.1.4Yaklaşım algoritması, sezgisel ve yaklaşım şemaları

Zor bir en iyileme problemine uygulanabilecek yöntemler, verdikleri garantiye göre sıralanabilir. Tablo 11.1 bu sıralamayı özetler.

Kesin algoritma en güçlü garantiyi verir, ama NP-zor problemlerde bedeli üstel süredir. Yaklaşım algoritması polinom sürede kalır ve kalitesini bir oranla güvenceye alır. Bazı problemlerde kullanıcı istediği doğruluğu bir ε sayısıyla seçer ve algoritma (1 + ε) oranlı bir çözüm döndürür. Böyle bir algoritma ailesine yaklaşım şeması (approximation scheme) denir.

İki şema arasındaki fark ilk bakışta ince görünür, ama pratikte büyüktür. Süresi O(n^1/ε) olan bir PTAS, her sabit ε için polinomdur. Yine de ε = 0,1 seçildiğinde süre n¹⁰ olur ve bu, yüz elemanlık bir girdide bile kullanılamaz. Süresi O(n³/ε) olan bir FPTAS'ta ise ε = 0,1 süreyi yalnız on katına çıkarır. Sırt çantası FPTAS'ı bulunan bir problemdir. Düzlemdeki noktalar için Öklid TSP'nin PTAS'ı vardır; Arora ve Mitchell bunu birbirinden bağımsız olarak göstermiştir.

Tablonun alt kısmındaki yöntemler hiçbir garanti vermez. Sezgisel (heuristic) yöntem, probleme özgü bir sağduyu kuralıyla hızlıca iyi bir çözüm üretir. En yakın komşu ve 2-opt TSP'nin bilinen sezgiselleridir. Metasezgisel (metaheuristic) yöntem ise belirli bir probleme bağlı olmayan genel bir arama çerçevesidir; benzetimli tavlama, genetik algoritma ve karınca kolonisi bu gruptadır. Bu yöntemler pratikte çoğunlukla çok iyi sonuç verir, ama en kötü durumda en iyiden ne kadar uzaklaşabilecekleri bilinmez.

11.1.5Uygulamalar ve teknikler

Yaklaşım algoritmalarının kullanıldığı problemler günlük hayatın içindedir. Gezgin satıcı problemi kargo dağıtımında ve devre kartlarında delik delme sırasında görülür. Sırt çantası bütçe ve yük planlamada, iş çizelgeleme makine ve işlemci planlamada kullanılır. Düğüm kapsama ise bir ağa en az sayıda izleme noktası yerleştirir. Büyük matrislerin özdeğerlerini yinelemeyle yakınsayan sayısal yöntemler de aynı başlık altında anılır; Google'ın PageRank hesabı bunun en bilinen örneğidir.

Bu problemlere uygulanan yaklaşım teknikleri birkaç ana fikirde toplanır:

• Basitleştirme: problemin daha kolay bir sürümü çözülür ve sonucu asıl probleme uyarlanır. Tam sayı kısıtını kaldıran doğrusal programlama gevşetmesi (LP relaxation) ve TSP için alt sınır veren minimum kapsayan ağaç bu türdendir.
• Açgözlü seçim: her adımda o an en iyi görünen seçenek alınır. En yakın komşu, en uzun iş önce ve oran sıralı sırt çantası örnektir.
• Yerel arama: mevcut çözüm küçük değişikliklerle iyileştirilir; daha iyi komşu çözüm kalmayınca durulur. 2-opt bunun örneğidir.
• Birincil–eşlenik (primal–dual) yöntem: doğrusal programın birincil ve eşlenik (dual) çözümleri birlikte büyütülür. Kapsama problemlerinde sık kullanılır.
• Rastgelelik: rastgele yuvarlama ya da örnekleme ile beklenen değerde oran garantisi elde edilir.
• Metasezgiseller: benzetimli tavlama, genetik algoritma, karınca kolonisi. Garanti vermezler, ama esnek ve güçlüdürler.

Bu tekniklerin ortak bir noktası vardır. Oran kanıtlarının hemen hepsi en iyi çözümün bilinmeyen değeri için bir alt sınır kurar. En iyi tur en az minimum kapsayan ağaç kadar uzundur; en iyi çizelge en az en uzun iş kadar sürer; en küçük kapsama en az bir eşleştirmedeki kenar sayısı kadar düğüm içerir. Algoritmanın sonucu bu alt sınırla karşılaştırılır. En iyi çözüm hiç hesaplanmadan oran böyle kanıtlanır. Bu notun bütün oran kanıtları aynı kalıba uyar.

11.2Gezgin satıcı problemi

Gezgin satıcı problemi, yaklaşım algoritmalarının en çok çalışıldığı problemdir. Tanımı bir cümleye sığar, ama en iyi çözümü bulmak şaşırtıcı ölçüde zordur. Bu kesim önce problemi tanımlar ve kesin çözümün maliyetini hesaplar. Ardından iki yaklaşık yöntemi inceler: en yakın komşu sezgiselini ve minimum kapsayan ağaca dayalı 2-yaklaşımı.

11.2.1Problemin tanımı

TSP bir en iyileme problemidir: amaç toplam uzaklığı en küçük yapmaktır. Aynı zamanda kombinatoryal bir problemdir, çünkü çözüm şehirlerin gezilme sırasıdır, yani bir permütasyondur. Çizge diliyle söylenirse simetrik TSP, kenarları ağırlıklı bir tam çizgede en hafif Hamilton çevrimini arar. Hamilton çevrimi, her düğümden tam bir kez geçip başlangıca dönen çevrimdir.

Problemin adı sık sık en kısa yol problemiyle karıştırılır. İki şehir arasındaki en kısa yol Dijkstra algoritmasıyla polinom sürede bulunur. TSP ise bütün şehirlerden geçen en kısa kapalı turu ister ve NP-zordur. Yüzlerce şehir için en iyi rotayı bulmak pratikte çok zordur.

Bu kesimde sunumdaki beş şehirli örnek kullanılır. Şehirler 0'dan 4'e numaralıdır ve uzaklıklar Tablo 11.2'deki simetrik matriste verilmiştir.

Matris simetriktir: d[1][3] = d[3][1] = 25 gibi. Köşegen sıfırdır, çünkü bir şehrin kendisine uzaklığı yoktur. Bir turun uzunluğu, ardışık şehirler arasındaki uzaklıkların ve son şehirden ilk şehre dönüşün toplamıdır. Örneğin 0 → 1 → 2 → 3 → 4 → 0 turunun uzunluğu 10 + 35 + 30 + 40 + 25 = 140'tır.

11.2.2Kesin çözümün maliyeti

En doğrudan kesin yöntem, kaba kuvvetle bütün turları denemektir. n şehrin n! sıralaması vardır, ama bunların çoğu aynı turu farklı yazar. Tur kapalı olduğu için başlangıç şehri sabitlenebilir: 0 → 1 → 3 → 2 → 4 → 0 ile 1 → 3 → 2 → 4 → 0 → 1 aynı turdur. Geriye (n − 1)! sıra kalır. Simetrik TSP'de bir tur ile onun tersten okunuşu da aynı uzunluktadır. Bu yüzden farklı tur sayısı (n − 1)!/2'dir.

Tablo 11.3 faktöriyelin ne kadar hızlı büyüdüğünü gösterir. Beş şehirde yalnız 12 tur vardır ve hepsi elle bile denenebilir. On şehirde tur sayısı 181 440'a çıkar; bir bilgisayar bunu bir anda bitirir. Yirmi şehirde ise saniyede bir milyar tur deneyen bir bilgisayar bile yaklaşık iki yıl çalışır. Yirmi beş şehirde gereken süre yaklaşık on milyon yıldır. Şehir sayısını beş artırmak, süreyi milyonlarca kat büyütür.

Daha akıllı bir kesin yöntem dinamik programlamadır. Held–Karp algoritması, “başlangıçtan çıkıp S kümesindeki şehirlerin hepsine uğrayan ve j'de biten en kısa yol” değerlerini tablolar ve O(n² · 2ⁿ) sürede çalışır. 25 şehirde bu yaklaşık 2 · 10¹⁰ işlemdir ve faktöriyelden çok daha iyidir. Yine de süre ve O(n · 2ⁿ) bellek üsteldir; altmış şehirde bu yöntem de kullanılamaz.

11.2.3En yakın komşu sezgiseli

En yakın komşu (nearest neighbor) sezgiseli, bir insanın haritaya bakmadan uygulayacağı kuralı izler: her zaman henüz gidilmemiş en yakın şehre gidilir. Adımları şöyledir:

1. Bir başlangıç şehri seçilir ve ziyaret edildi olarak işaretlenir.
2. Bulunulan şehirden ziyaret edilmemiş en yakın şehre gidilir. Bu bir açgözlü seçimdir.
3. Bütün şehirler ziyaret edilene kadar ikinci adım tekrarlanır.
4. Son şehirden başlangıç şehrine dönülür ve tur kapanır.

Sunumdaki Java kodu bu adımları doğrudan uygular:

int[] enYakinKomsu(int[][] d, int bas) {
  int n = d.length, toplam = 0, simdiki = bas;
  boolean[] ziyaret = new boolean[n];
  int[] tur = new int[n + 1];
  tur[0] = bas; ziyaret[bas] = true;
  for (int k = 1; k < n; k++) {
    int enYakin = -1, enAz = Integer.MAX_VALUE;
    for (int j = 0; j < n; j++)
      if (!ziyaret[j] && d[simdiki][j] < enAz) {
        enAz = d[simdiki][j]; enYakin = j; }
    // en yakın şehre git
    tur[k] = enYakin; ziyaret[enYakin] = true;
    toplam += enAz; simdiki = enYakin;
  }
  // başlangıca dön
  tur[n] = bas; toplam += d[simdiki][bas];
  return tur;
}

Kod, uzaklık matrisini d ve başlangıç şehrini bas olarak alır. ziyaret dizisi her şehrin turda olup olmadığını tutar. tur dizisinin n + 1 gözü vardır, çünkü başlangıç şehri hem ilk hem son gözde yer alır. simdiki o an bulunulan şehri, toplam o ana kadarki yol uzunluğunu gösterir.

Dış döngü k = 1'den n − 1'e kadar döner ve her turda bir şehir ekler. İç döngü simdiki şehrin satırını tarar. Ziyaret edilmemiş ve şimdiye kadarki en küçük uzaklıktan daha yakın olan her şehir enYakin adayı olur. Karşılaştırmanın < ile yapılması bir eşitlik kuralı da getirir: aynı uzaklıkta iki şehir varsa indisi küçük olan seçilir. İç döngü bitince en yakın şehir tura yazılır, işaretlenir, uzaklığı toplama eklenir ve yeni simdiki olur. Dış döngüden çıkınca son şehirden başlangıca dönüş kenarı eklenir.

Maliyet hesabı kısadır. Dış döngü n − 1 kez, iç döngü her seferinde n kez döner. İç döngünün gövdesi sabit süredir. Toplam süre O(n²)'dir. Ek bellek ziyaret ve tur dizileri için O(n)'dir. Girdinin kendisi zaten n² boyutlu bir matris olduğu için bu süre girdiyi okuma süresiyle aynı düzeydedir. Daha hızlısı beklenemez.

11.2.4Kod izleme: beş şehir

enYakinKomsu(d, 0) çağrısı Tablo 11.2'deki matrisle çalıştırılsın. Başlangıçta ziyaret[0] = true, tur = [0] ve toplam = 0'dır. Tablo 11.4 her dış döngü adımını gösterir.

İlk adımda 0. satır taranır. Dört aday arasında en küçük uzaklık 10'dur ve 1 şehrine aittir. Tur 0 → 1 olur, toplam 10'dur. İkinci adımda 1. satırda yalnız ziyaret edilmemiş 2, 3 ve 4 sütunlarına bakılır; 0 sütunu işaretli olduğu için atlanır. En küçük değer 25'tir, şehir 3 seçilir ve toplam 35 olur. Üçüncü adımda 3. satırdan 2 (30) ve 4 (40) arasında 2 seçilir; toplam 65'tir. Dördüncü adımda tek aday kalmıştır: 4. Toplam 65 + 35 = 100 olur. Son olarak 4'ten 0'a dönülür ve d[4][0] = 25 eklenir.

Sonuç 0 → 1 → 3 → 2 → 4 → 0 turudur ve uzunluğu 125'tir (Şekil 11.4). Doğrulama betiği aynı kodu beş başlangıç şehrinin hepsiyle çalıştırmıştır. Her başlangıçta bulunan turun uzunluğu yine 125'tir. Örneğin 2'den başlanırsa tur 2 → 0 → 1 → 3 → 4 → 2 olur: 15 + 10 + 25 + 40 + 35 = 125.

11.2.5Kaba kuvvetle karşılaştırma

Beş şehirde (5 − 1)!/2 = 12 farklı tur vardır. Hepsi denenince en yakın komşunun sonucu değerlendirilebilir. Tablo 11.5 on iki turu ve uzunluklarını verir.

Tablo iki ilginç sonuç verir. Birincisi, turların yarısı 125, öbür yarısı 140 uzunluğundadır. En iyi uzunluk 125'tir ve altı farklı tur bu değere ulaşır. En yakın komşunun bulduğu tur bunlardan biridir; yani bu örnekte sezgisel en iyi sonucu bulmuştur. Bu bir şans eseridir ve genel bir durum değildir. İkincisi, matris üçgen eşitsizliğini sağlamaz: d[1][2] = 35'tir, ama 1'den 0 üzerinden 2'ye gitmek yalnız d[1][0] + d[0][2] = 10 + 15 = 25 tutar. Doğrudan yol dolambaçlı yoldan uzundur. Böyle bir matrise metrik değil denir. Bu özellik, oran garantileri için belirleyicidir.

En yakın komşunun güçlü ve zayıf yanları şöyle özetlenebilir. Çok basittir ve O(n²) sürede çalışır. Rastgele düzlem örneklerinde bulduğu turlar ortalama olarak en iyinin yaklaşık %25 üzerindedir. Yerel arama için iyi bir başlangıç turu sağlar. Buna karşılık sabit bir yaklaşım oranı yoktur. Rosenkrantz, Stearns ve Lewis, üçgen eşitsizliği sağlansa bile oranın Θ(log n) düzeyine çıkabildiğini göstermiştir: üst sınır O(log n)'dir ve bu sınıra yaklaşan girdiler kurulabilir.

11.2.6Genel TSP'de sabit oran yoktur

En yakın komşunun sabit bir oranı yoktur; ama belki daha akıllı bir algoritmanın vardır. Genel TSP için, yani uzaklıklar üzerinde hiçbir koşul yokken, bu umut boşunadır. P ≠ NP ise genel TSP için polinom zamanlı hiçbir sabit oranlı yaklaşım algoritması yoktur. Kanıt, Hamilton çevrimi problemine dayanır. Bir çizgede Hamilton çevrimi olup olmadığını belirleme problemi NP-tamdır.

Kurgunun gücü ağır kenarlardan gelir: tek bir ağır kenar bile oranı bozar. Ancak bu kurgu üçgen eşitsizliğini ağır biçimde ihlal eder; ağır u–v kenarı ρn + 1 iken ortak bir komşu üzerinden yol yalnız 2'dir. Uzaklıkların üçgen eşitsizliğini sağladığı TSP'de kurgu geçersizdir ve sabit oranlı algoritmalar vardır.

11.2.7Metrik TSP için MST tabanlı 2-yaklaşım

Gerçek hayattaki uzaklıkların çoğu metriktir. Düzlemdeki noktalar arasındaki Öklid uzaklığı, bir yol ağındaki en kısa yol uzaklıkları ve uçuş süreleri bu türdendir. Metrik TSP hâlâ NP-zordur, ama artık sabit oranlı bir algoritma mümkündür. En basiti minimum kapsayan ağaca (minimum spanning tree, MST) dayanır. Minimum kapsayan ağaç, bir çizgenin bütün düğümlerini bağlayan ağaçların toplam ağırlığı en küçük olanıdır. Prim ya da Kruskal algoritmasıyla O(n²) ya da O(E log V) sürede bulunur.

Algoritmanın üç adımı vardır:

1. Şehirlerin tam çizgesinde bir minimum kapsayan ağaç T kurulur.
2. T, bir kök şehirden başlayarak derinlik öncelikli gezilir. Her kenar bir kez gidişte, bir kez dönüşte kullanılır. Bu kapalı yürüyüşün uzunluğu 2 · w(T)'dir.
3. Yürüyüşte daha önce görülmüş şehirler atlanır (kısayol). Geriye şehirlerin önce-kök (preorder) sırası kalır; sona başlangıç şehri eklenince tur kapanır.

Sunumdaki örnekte düzlemde yedi şehir vardır ve uzaklıklar Öklid uzaklığıdır. Doğrulama betiği şehirlerin koordinatlarını şekildeki çizimden geri hesaplamıştır: A (10, 20), B (18, 68), C (42, 86), D (50, 46), E (76, 78), F (92, 42), G (62, 10). Bütün uzaklıklar bu koordinatlardan bulunur.

Prim algoritması A'dan başlatılırsa kenarlar şu sırayla eklenir: A–D (47,7), D–G (37,9), D–B (38,8), B–C (30,0), C–E (34,9), E–F (39,4). Toplam ağırlık w(T) = 228,8'dir (Şekil 11.5). Ağacın neden en iyi tur için bir alt sınır olduğu kolayca görülür. En iyi turdan herhangi bir kenar silinirse bütün şehirleri bağlayan bir yol kalır. Yol da bir kapsayan ağaçtır. Minimum kapsayan ağaç, bütün kapsayan ağaçların en hafifi olduğu için bu yoldan kısadır. Kenar ağırlıkları negatif olmadığından w(T) ≤ OPT çıkar.

İkinci adımda ağaç A'dan derinlik öncelikli gezilir. Sunumdaki gezinme D'nin çocuklarından önce B'yi, sonra G'yi ziyaret eder: A → D → B → C → E → F → E → C → B → D → G → D → A. Her ağaç kenarı iki kez kullanılır ve yürüyüşün uzunluğu 2 · 228,8 = 457,6'dır. Bu yürüyüş geçerli bir tur değildir, çünkü D, B, C ve E birden çok kez geçilir.

Üçüncü adımda tekrar eden şehirler atlanır. Yürüyüş soldan okunur ve ilk kez görülen her şehir tura yazılır: A, D, B, C, E, F; sonra E, C, B, D atlanır; G yazılır; D ve A atlanır. Sona A eklenince tur A → D → B → C → E → F → G → A olur. Uzunluğu Tablo 11.6'da adım adım hesaplanmıştır.

Kısayolların yürüyüşü hiç uzatmadığı tablodan görülür. F'den G'ye yürüyüş beş ağaç kenarından geçer ve 181,0 tutar; doğrudan F–G kenarı ise 43,9'dur. Bunu garanti eden üçgen eşitsizliğidir: bir ara şehri atlamak, yani d_ik + d_kj yerine d_ij kullanmak, uzunluğu artırmaz. Atlama tekrar tekrar uygulanınca birden çok ara şehir de atlanabilir.

Örnekte kaba kuvvet 6!/2 = 360 turun hepsini dener. En iyi tur A → B → C → E → F → G → D → A'dır ve uzunluğu 282,5'tir. Algoritmanın bulduğu 287,7, en iyinin yalnız yaklaşık 1,02 katıdır. Garanti 2'dir, ama pratik sonuç çok daha iyidir. Kanıttaki sınırlar da kontrol edilebilir: w(T) = 228,8 ≤ 282,5 = OPT ve 287,7 ≤ 457,6 = 2 · w(T).

Algoritmanın süresini ağaç kurma belirler. Tam çizgede Prim algoritması dizi tabanlı uygulamayla O(n²) sürer. Derinlik öncelikli gezinme ve kısayol adımı O(n)'dir. Toplam süre O(n²)'dir; en yakın komşuyla aynı düzeydedir, ama artık kanıtlanmış bir oran vardır.

11.2.8Christofides ve diğer sınırlar

MST tabanlı algoritmanın kaybı tek bir yerden gelir: her ağaç kenarı iki kez yürünür. Christofides 1976'da bu çift yürüyüşü daha ucuz bir yapıyla değiştirdi. Ağaçta derecesi tek olan düğümler bulunur; bunların sayısı her zaman çifttir. Bu düğümler arasında en küçük ağırlıklı mükemmel eşleştirme kurulur. Ağaç ile eşleştirmenin birleşiminde her düğümün derecesi çifttir ve bu yüzden bir Euler turu vardır. Euler turu her kenardan tam bir kez geçen kapalı yürüyüştür. Bu yürüyüşe kısayol uygulanır. Eşleştirmenin ağırlığı en fazla OPT / 2'dir; toplam w(T) + OPT/2 ≤ 1,5 · OPT olur. Algoritmanın süresi, eşleştirme adımı yüzünden O(n³)'tür.

Christofides'in 1,5 sınırı kırk yılı aşkın süre geliştirilemedi. 2020'de Karlin, Klein ve Oveis Gharan oranı rastgele bir algoritmayla 3/2 − ε'a indirdi; buradaki ε 10⁻³⁶'dan büyük çok küçük bir sabittir. Pratik bir fark yaratmaz, ama 1,5'in aşılabildiğini gösterir. Tablo 11.7 TSP için bilinen başlıca sonuçları toplar.

11.3Yerel arama: 2-opt

En yakın komşu ve MST tabanlı algoritma bir turu sıfırdan kurar. Yerel arama ise elde zaten bir tur olduğunu varsayar ve onu adım adım iyileştirir. Başlangıç turu rastgele olabilir ya da başka bir sezgiselden gelebilir.

11.3.1Yerel arama fikri

Yerel arama bir dağcının sisli havada tırmanmasına benzer. Dağcı yalnız bulunduğu noktanın çevresini görür. Hangi adım daha yükseğe çıkarıyorsa o adımı atar; hiçbir yönde yükselme kalmayınca durur. Durduğu yer bir tepedir, ama dağın en yüksek tepesi olmayabilir. Yerel arama da yerel bir optimumda durur. Bu nokta genel optimum (global optimum), yani bütün çözümlerin en iyisi olmayabilir.

11.3.22-opt hamlesi ve kazancı

Bir turdan iki kenar çıkarılsın: (a, b) ve (c, d). Tur iki parçaya ayrılır. Parçaları yeniden bir tur hâline getirmenin, eski bağlantılardan farklı tek bir yolu vardır: a'yı c'ye, b'yi d'ye bağlamak. Bu bağlantı yapılınca b … c arasındaki alt yol ters yönde gezilir. Bu değişikliğe 2-opt hamlesi denir.

Hamlenin turu kısaltıp kısaltmadığı yalnız dört kenara bakılarak anlaşılır. Tersine çevrilen alt yolun iç kenarları aynı kalır, çünkü simetrik TSP'de bir kenarın uzunluğu yönüne bağlı değildir. Değişen yalnız çıkan iki kenar ile giren iki kenardır. Hamlenin kazancı şöyle yazılır:

Δ = d(a, c) + d(b, d) − d(a, b) − d(c, d)

Δ < 0 ise yeni tur eskisinden |Δ| kadar kısadır ve hamle yapılır. Δ ≥ 0 ise hamle turu kısaltmaz. Kazanç O(1) sürede hesaplanır. Tur uzunluğu yeniden toplanmaz.

Öklid düzleminde 2-opt'un geometrik bir yorumu vardır: kesişen iki kenar her zaman kaldırılabilir. (a, b) ve (c, d) doğru parçaları bir X noktasında kesişsin. Üçgen eşitsizliğine göre d(a, c) ≤ d(a, X) + d(X, c) ve d(b, d) ≤ d(b, X) + d(X, d)'dir. Sağ tarafların toplamı tam olarak d(a, b) + d(c, d)'dir. Demek ki Δ ≤ 0'dır ve noktalar aynı doğru üzerinde değilse eşitsizlik kesindir. Sonuç olarak 2-opt yerel optimumu olan bir Öklid turunun hiçbir kenarı bir başkasını kesmez.

2-opt hamlesi yapacak hiçbir kenar çifti kalmayınca tur bir 2-opt yerel optimumudur. Bu tur çoğunlukla iyi bir turdur, ama genel optimum olması gerekmez. Daha iyi bir tura ulaşmak için iki kenardan fazlasını aynı anda değiştirmek gerekebilir.

11.3.3Kod ve maliyet

Sunumdaki Java kodu “ilk iyileştiren hamle” stratejisini izler. Turu tarar ve kazancı negatif olan ilk hamleyi hemen uygular:

void ikiOpt(int[] tur, double[][] d) {
  int n = tur.length;
  boolean iyilesti = true;
  while (iyilesti) {
    iyilesti = false;
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 2; j < n; j++) {
        int a = tur[i], b = tur[i + 1];
        int c = tur[j], e = tur[(j + 1) % n];
        double fark = d[a][c] + d[b][e]
                    - d[a][b] - d[c][e];
        if (fark < -1e-9) {   // kısalıyor
          tersCevir(tur, i + 1, j);
          iyilesti = true;
        }
      }
  }
}

Tur, şehir numaralarından oluşan tur dizisinde tutulur ve kapalıdır: son şehirden ilk şehre bir kenar vardır. iyilesti bayrağı bir taramada en az bir hamle yapılıp yapılmadığını izler. Dış while döngüsü, bir tarama hiç hamle yapmadan bitene kadar sürer.

İç döngüler kenar çiftlerini dolaşır. i. kenar tur[i] ile tur[i + 1] arasındaki kenardır; j. kenar tur[j] ile tur[(j + 1) % n] arasındadır. Mod işlemi son kenarın, yani son şehirden ilk şehre dönen kenarın da hesaba katılmasını sağlar. j'nin i + 2'den başlaması, komşu iki kenarın seçilmesini önler. Komşu kenarların ortak bir ucu vardır ve onlarla yapılan bir 2-opt hamlesi turu değiştirmez. Yine de i = 0 ve j = n − 1 durumunda iki kenar turun başında birleşir: e = tur[0] = a olur ve kazanç her zaman sıfır çıkar. Kod bu durumu ayrıca dışlamaz; kazanç sıfır olduğu için hamle yapılmaz.

Kazanç fark değişkeninde hesaplanır. Karşılaştırma fark < 0 yerine fark < -1e-9 ile yapılır. Uzaklıklar double olduğu için yuvarlama hataları sıfır olması gereken bir farkı −10⁻¹⁶ gibi çok küçük bir negatif sayı yapabilir. Böyle bir “hayalet kazanç”, algoritmanın aynı iki tur arasında sonsuza kadar gidip gelmesine yol açabilir. Küçük eşik bunu önler.

Hamle yapılınca tersCevir(tur, i + 1, j) çağrılır. Bu yardımcı metot sunumda verilmez; tur[i + 1] ile tur[j] arasındaki öğeleri, iki sınır dahil, yerinde ters çevirir. İki uçtan ortaya doğru yer değiştiren bir döngüyle yazılabilir:

void tersCevir(int[] t, int i, int j) {
  while (i < j) {
    int x = t[i]; t[i] = t[j]; t[j] = x;
    i++; j--;
  }
}

Maliyet üç düzeyde incelenir. Bir tarama n(n − 3)/2 civarında, yani O(n²) kenar çiftine bakar. Her çiftin kazancı O(1)'de hesaplanır. Hamle yapılan çiftte ters çevirme O(n) sürer. Kaç tarama yapılacağı ise önceden bilinmez. En kötü durumda tarama sayısı üstel olabilir; kuramsal olarak kötü girdiler kurulabilir. Pratikte ise birkaç düzine tarama çoğunlukla yeter.

11.3.4Kod izleme: dört nokta

Sunumdaki izleme dört noktayla çalışır: 0 (0, 0), 1 (3, 4), 2 (3, 0) ve 3 (0, 4). Noktalar 3 × 4 boyutunda bir dikdörtgenin köşeleridir. Uzaklıklar Öklid uzaklığıdır: yatay kenarlar 3, dikey kenarlar 4, köşegenler 5 birimdir. Başlangıç turu 0 → 1 → 2 → 3 → 0'dır. Bu tur iki köşegeni kullanır: d(0, 1) + d(1, 2) + d(2, 3) + d(3, 0) = 5 + 4 + 5 + 4 = 18.

Tablo 11.8 izlemeyi verir. n = 4 olduğu için i 0 ile 2 arasında, j de i + 2 ile 3 arasında değişir. Geçerli çiftler (0, 2), (0, 3) ve (1, 3)'tür. İlk taramada (0, 2) çifti (0, 1) ve (2, 3) köşegenlerini çıkarıp (0, 2) ve (1, 3) kenarlarını önerir. Bu kenarlar 3 birimlik kısa kenarlardır: fark = 3 + 3 − 5 − 5 = −4. Hamle yapılır, tersCevir(tur, 1, 2) ile 1 ve 2 yer değiştirir ve tur [0, 2, 1, 3] olur. Yeni uzunluk 3 + 4 + 3 + 4 = 14'tür.

Tarama aynı tur üzerinde sürer. (0, 3) çiftinde iki kenar ortak uçludur (e = a) ve fark sıfırdır. (1, 3) çifti köşegenleri geri getirir ve +2 verir. İlk taramada hamle yapıldığı için tarama yinelenir; ikinci taramada hiçbir çift negatif kazanç vermez ve döngü biter.

Sonuç [0, 2, 1, 3] turu ve 14 uzunluğudur. Bu tur dikdörtgenin çevresidir. Dört noktada yalnız üç farklı tur vardır (3!/2 = 3): çevre (14) ve köşegen kullanan iki tur (18 ve 18). Bu örnekte 2-opt yerel optimumu aynı zamanda genel optimumdur.

11.3.5Yirmi sekiz şehirde 2-opt

Daha büyük bir örnek, 2-opt'un gücünü daha açık gösterir. Sunumda 28 şehir 0–100 aralığında rastgele yerleştirilmiş ve rastgele bir başlangıç turu seçilmiştir. Tur kenarları sürekli birbirini keser ve uzunluk 1269,8'dir. Doğrulama betiği şehir koordinatlarını sunumdaki çizimden okumuş ve aynı ikiOpt kodunu çalıştırmıştır. Sunumdaki bütün değerler bu çalıştırmayla birebir tutar.

Tablo 11.9'daki değerler iki şey gösterir. Birincisi, tek tek hamlelerin kazancı küçüktür. Tablodaki kazançlar 9 ile 37 birim arasındadır; 48 hamlenin en büyüğü bile (70,4) o anki tur uzunluğunun %10'unu geçmez. İlk iyileştiren hamle stratejisi büyük kazancı aramaz, bulduğu ilk kazancı alır. İkincisi, bu küçük kazançlar birikir. 48 hamleden sonra tur 430,8'e iner. Bu, başlangıç uzunluğunun yaklaşık %34'üdür.

Son turda kesişen kenar yoktur (Şekil 11.11). Bu, 2-opt hamlesinin geometrik yorumundan beklenen sonuçtur: 2-opt yerel optimumu olan bir Öklid turunun kenarları birbirini kesmez. Ancak kesişme olmaması turun en iyi olduğu anlamına gelmez. Kesişmesiz birçok tur vardır ve bunların uzunlukları birbirinden farklıdır.

Strateji ve başlangıç turu sonucu etkiler. Doğrulama betiği iki farklı deneme daha yapmıştır. “En iyi iyileştiren hamle” stratejisi her taramada bütün çiftlere bakıp kazancı en büyük olanı uygular. Aynı rastgele turdan başladığında 23 hamlede durur ve 441,9 uzunluğunda bir yerel optimum bulur. En yakın komşu turundan (518,6) başlayan ilk iyileştiren hamle stratejisi ise yalnız 10 hamlede durur ve 449,7'ye ulaşır. Bu örnekte rastgele başlangıç daha uzun sürmüş ama daha iyi bir yerel optimuma varmıştır. Genel bir kural çıkarılamaz. Yerel aramanın sonucu başlangıca ve stratejiye bağlıdır; pratikte farklı başlangıçlarla birkaç kez çalıştırılıp en iyisi alınır.

11.3.6Yerel optimumdan kaçış: metasezgiseller

Yerel aramanın temel sorunu, ilk yerel optimumda takılmasıdır. Yalnız iyileştiren hamleleri kabul eden bir algoritma, bir çukura düştüğünde oradan çıkamaz. Metasezgiseller bu sorunu farklı yollardan aşar: bazen kötüleştiren hamleleri de kabul eder, aynı anda birçok çözümü birlikte geliştirir ya da geçmişten öğrenir.

Benzetimli tavlama (simulated annealing) adını metallerin tavlanmasından alır. Sıcak metal yavaşça soğutulursa atomları düzenli, enerjisi düşük bir yapıya yerleşir. Algoritma her adımda rastgele bir komşu seçer. Komşu daha iyiyse hamle yapılır. Daha kötüyse, yani maliyeti Δ > 0 kadar artırıyorsa, hamle e^−Δ/T olasılıkla yine de kabul edilir. Buradaki T, “sıcaklık” denen bir parametredir ve yavaşça düşürülür. Tipik bir ayar T₀ = 100 ile başlar ve her adımda T ← 0,997 · T yapar.

Tablo 11.10 sıcaklığın etkisini gösterir. Yüksek sıcaklıkta kötüleştiren hamleler de neredeyse her zaman kabul edilir ve arama manzarada serbestçe dolaşır. Sıcaklık düştükçe hamleler seçicileşir. T = 1'de 5 birim kötüleştiren bir hamle yaklaşık 150 denemede bir kabul edilir. Sonunda algoritma neredeyse yalnız iyileştiren hamleleri kabul eden bir yerel aramaya dönüşür. Soğuma hızı da hesaplanabilir. 100 · 0,997^k < 1 eşitsizliği k > ln 100 / (−ln 0,997) ≈ 1532,8 verir; sıcaklık 1533 adımda 1'in altına iner.

Genetik algoritma (genetic algorithm) bir tur popülasyonuyla çalışır. Kısa turlar daha sık seçilir, seçilen turlar çaprazlama (crossover) ile birleştirilir ve mutasyon çeşitliliği korur. Tipik bir ayar 100 bireylik popülasyon, rastgele kesim noktalı çaprazlama ve 0,05 mutasyon olasılığıdır.

Karınca kolonisi optimizasyonu (ant colony optimization) gerçek karıncalardan esinlenir. Kısa tur kuran yapay karıncalar kenarlara daha çok feromon bırakır; sonraki karıncalar feromonu yoğun kenarları tercih eder ve feromon zamanla buharlaşır.

Üç yöntem de TSP, araç rotalama, iş çizelgeleme ve atama problemlerinde yaygın olarak kullanılır. Hiçbiri yaklaşım oranı garanti etmez. Sonuç başlangıç çözümüne, parametrelere ve rastgele sayı üretecinin tohumuna duyarlıdır.

11.4İş çizelgeleme

İş çizelgeleme (job scheduling), belirli kaynaklarla (işçiler, makineler, işlemciler) işlerin en verimli biçimde planlanmasıdır. Amaç, işlerin tamamlanma süresini en aza indirmek ya da kâr, gecikme ve son tarih gibi ölçütlere göre en iyi planı bulmaktır. Bu kesim iki problemi ayırır ve yaklaşım algoritmalarına konu olanını ayrıntılı inceler.

11.4.1İki çizelgeleme problemi

Makine çizelgeleme probleminde n iş ve m özdeş makine vardır. j. işin süresi p_j'dir. Her iş tek bir makinede, kesintisiz çalışır. Bir makinenin yükü, ona verilen işlerin sürelerinin toplamıdır. Son işin bittiği an, yani en yüklü makinenin yükü C_max ile gösterilir. Bu değere en büyük yük (makespan) denir. Amaç C_max'ı en küçük yapmaktır. Problem m ≥ 2 için NP-zordur; m = 2 durumu bile, işleri toplamları eşit iki kümeye bölme probleminin bir sürümüdür.

Son tarihli iş sıralama probleminde her iş bir birim sürer ve bir kârı ile bir son tarihi vardır. Son tarihinden önce biten işlerin toplam kârı en büyük olmalıdır. Bu problem, işleri kâra göre azalan sırayla son tarihinden önceki en geç boş dilime koyan açgözlü bir algoritmayla en iyi biçimde çözülür.

11.4.2Liste çizelgeleme

Liste çizelgeleme çevrimiçi bir algoritmadır: bir işi atarken sonra gelecek işleri bilmesi gerekmez. Bu yüzden işlerin zaman içinde geldiği ortamlarda doğrudan kullanılabilir. Sunumdaki örnek bu durumu gösterir. Üç özdeş makine M1, M2 ve M3 vardır. J1 (süre 2), J2 (süre 8) ve J3 (süre 6) t = 0'da hazırdır; J4 (süre 3) t = 3'te gelir.

Bütün işler atandıktan sonra en büyük yük 8'dir ve M2'ye aittir (Şekil 11.14). Bu çizelge en iyidir, çünkü hiçbir çizelge en uzun işten önce bitemez. J2 tek başına 8 birim sürer; en iyi en büyük yük de en az 8'dir. Genelde ise liste çizelgeleme en iyiyi bulmaz; yalnız 2 − 1/m oranını garanti eder.

En az yüklü makine bir dizi taranarak bulunursa süre O(nm), makineler bir en küçük öbekte (min-heap) tutulursa O(n log m) olur.

11.4.3Liste çizelgelemenin oranı

Oran kanıtı, en iyi çözüm için iki alt sınıra dayanır. Bunlardan biri iş yüküyle ilgilidir. Toplam iş Σ p_j'dir ve m makineye dağıtılmalıdır. En iyi çizelgede bile bir makinenin yükü en az ortalama yük kadardır: OPT ≥ Σ p_j / m. Öbürü en uzun işle ilgilidir. Her iş bir makinede kesintisiz çalışır; en uzun iş tek başına max p_j sürer: OPT ≥ max p_j.

Oranın sıkı olduğu, yani daha iyi bir sınırın kanıtlanamayacağı bir örnekle gösterilir. m = 2 makine ve sırasıyla 1, 1, 2 süreli üç iş olsun. Liste çizelgeleme ilk işi M1'e, ikinciyi M2'ye verir; üçüncü iş için iki makinenin yükü de 1'dir ve iş M1'e gider. Yükler 3 ve 1 olur; C_max = 3'tür. En iyi çizelge iki kısa işi bir makineye, uzun işi öbürüne verir ve 2'de biter. Oran 3/2 = 2 − 1/2'dir; teoremdeki sınıra tam olarak ulaşılmıştır.

Örnek her m için genelleştirilebilir: önce m(m − 1) adet 1 birimlik iş, sonra tek bir m birimlik iş gelsin. Kısa işler makinelere eşit dağılır ve her makinenin yükü m − 1 olur. Uzun iş bunlardan birine eklenir: C_max = 2m − 1. En iyi çizelge uzun işi tek başına bir makineye verir ve kısa işleri kalan m − 1 makineye m'şer dağıtır: OPT = m. Oran (2m − 1)/m = 2 − 1/m'dir. m = 3 için altı adet 1 birimlik iş ve bir 3 birimlik iş, 5/3 oranını verir.

11.4.4En uzun iş önce (LPT)

Sıkı örnekler aynı zayıflığı gösterir: uzun bir iş sona kalınca, öbür makineler çoktan bitmişken tek bir makine çalışmaya devam eder. Çözüm basittir: uzun işler başa alınır. En uzun iş önce (longest processing time first, LPT) kuralı, işleri süreye göre azalan sıraya koyar ve sonra liste çizelgeleme uygular. Sona kalan işler kısadır; dengesizliği düzeltirler.

Sunumdaki örnekte işler 2, 3, 4, 6, 2, 2 ve m = 3'tür. Toplam iş 19'dur; en iyi en büyük yük en az ⌈19/3⌉ = 7'dir. Verilen sırayla liste çizelgeleme önce 2, 3 ve 4'ü üç makineye dağıtır. 6 birimlik iş en az yüklü makineye, yani 2 birim yüklü M1'e gider ve onun yükü 8 olur. Kalan iki kısa iş M2 ve M3'e eklenir. C_max = 8'dir. LPT sırası 6, 4, 3, 2, 2, 2'dir. Uzun işler önce üç makineye dağılır; kısa işler sonra en az yüklü makinelere eklenir ve yükler 6, 6, 7 olur. C_max = 7'dir ve alt sınıra eşit olduğu için en iyidir.

LPT sınırı da sıkıdır. m = 3 ve işler 5, 5, 4, 4, 3, 3, 3 olsun. LPT yükleri önce 5, 5, 4 yapar. Sonraki 4 ve iki 3 yükleri 8, 8, 8'e getirir; son 3 bir makineyi 11'e çıkarır. En iyi çizelge {5, 4}, {5, 4}, {3, 3, 3} ile 9'da biter: oran 11/9 = 4/3 − 1/9. Aynı kalıp her m için kurulur: 2m − 1, 2m − 1, …, m + 1, m + 1 ve üç tane m. Doğrulama betiği m = 2, 3, 4 için LPT'nin 4m − 1, en iyinin 3m bulduğunu denetlemiştir.

LPT çevrimiçi değildir: işleri sıralamak için hepsini önceden bilmelidir. Bunun karşılığında garantisi çok daha güçlüdür. Liste çizelgelemenin sınırı m arttıkça 2'ye, LPT'ninki 4/3'e yaklaşır; m = 2'de değerler 1,5 ve 7/6 ≈ 1,17, m = 4'te 1,75 ve 1,25'tir. Makine çizelgelemenin bir PTAS'ı da vardır (Hochbaum ve Shmoys, 1987): her 1 + ε oranına polinom sürede ulaşılabilir, ama süre 1/ε'da üsteldir.

11.4.5LPT kodu ve izleme

Sunumdaki Java kodu LPT'yi en basit biçimde yazar:

int lpt(Integer[] isler, int m) {
  Arrays.sort(isler, Comparator.reverseOrder());
  int[] yuk = new int[m];
  for (int p : isler) {
    int k = 0;              // en az yüklü
    for (int i = 1; i < m; i++)
      if (yuk[i] < yuk[k]) k = i;
    yuk[k] += p;
  }
  return Arrays.stream(yuk).max().getAsInt();
}

İlk satır işleri Comparator.reverseOrder() ile büyükten küçüğe sıralar. Bu karşılaştırıcı nesnelerle çalıştığı için dizi int[] değil Integer[] türündedir. yuk dizisi her makinenin o anki yükünü tutar ve başta sıfırdır. Döngü her işi ele alır. İç döngü en az yüklü makinenin indisini k'de bulur. Karşılaştırma kesin küçüktür (<); bu yüzden yükler eşitse indisi küçük olan makine seçilir. İş o makinenin yüküne eklenir. Sonunda yüklerin en büyüğü döndürülür.

Kodun ilk satırı silinirse geriye liste çizelgeleme kalır: işler verildiği sırayla en az yüklü makineye gider. İki algoritma arasındaki tek fark bu sıralamadır. Kodda en az yüklü makine dizi taranarak bulunur ve her iş için O(m) sürer. Toplam süre O(n log n + nm)'dir. Makineler bir öbekte tutulursa süre O(n log n + n log m) = O(n log n)'ye iner.

Tablo 11.12 kodun her adımını gösterir. İlk adımda bütün yükler sıfırdır. İç döngü k = 0 ile başlar ve hiçbir yük 0'dan küçük olmadığı için değişmez; 6 birinci makineye gider. İkinci ve üçüncü adımlarda boş makineler sırayla doldurulur. Dördüncü adımda en az yüklü makine 3 yüklü M2'dir (k = 2). Beşinci adımda yükler 6, 4, 5'tir ve 2 birimlik iş 4 yüklü makineye gider. Son adımda yükler 6, 6, 5'tir ve son iş 5 yüklü makineye eklenir. En büyük yük 7'dir. Alt sınır ⌈19/3⌉ = 7 olduğu için bu çizelge en iyidir.

11.5Düğüm kapsama

Bir kampüs ağında her bağlantının izlenmesi istensin. İzleme yazılımı bir yönlendiriciye kurulunca o yönlendiriciye bağlı bütün hatları görür. En az kaç yönlendiriciye yazılım kurulmalıdır? Bu soru, çizge kuramının klasik düğüm kapsama problemidir.

11.5.1Problemin tanımı

Kapsama kümesi bir gözcü düzeni gibi düşünülebilir: her düğümdeki gözcü o düğüme değen kenarları görür ve her kenarı en az bir gözcü görmelidir. Problemin karar sürümü, yani “k düğümlük bir kapsama var mı?” sorusu, NP-tamdır.

Şekil 11.18'deki çizgede soldaki altı düğümlük küme geçerlidir, ama sağdaki üç düğüm aynı işi görür. En soldaki düğüm dörtgenin iki kenarını, ortadaki merkez düğüm dörtgenin öbür iki kenarını ve sağa açılan dört kenarı, sağdaki iç düğüm de üç yaprağa giden kenarları kapsar. Üçten azının yetmediği de gösterilebilir: dörtgenin bir kenarı, merkezden sağa giden bir kenar ve bir yaprak kenarı ortak ucu olmayan üç kenardır. Her biri ayrı bir gözcü ister.

Sunumdaki ikinci örnek dört düğümlüdür. Düğümler A, B, C, D, kenarlar (A, B), (A, C), (B, C), (B, D), (C, D)'dir. {A, B, C} geçerli bir kapsamadır: her kenarın en az bir ucu kümededir. Ama en küçük değildir, çünkü {B, C} de beş kenarın hepsini kapsar. Tek düğüm yetmez; örneğin B, (A, C) kenarını kapsamaz. En iyi değer 2'dir.

11.5.2Çözüm yaklaşımları

Kesin çözüm, 2ⁿ alt kümenin her birini O(m) sürede denetler: toplam O(2ⁿ · m). Dal sınır ve doğrusal programlama bu aramayı hızlandırır, ama üstel süreyi ortadan kaldırmaz.

Yaklaşık çözümlerde iki açgözlü fikir öne çıkar: en yüksek dereceli düğümü seçmek ve kapsanmamış bir kenarın iki ucunu birden almak. İlki doğal görünür ama garantisi zayıftır; ikincisi savurgan görünür, ama 2 oranını garanti eder.

Şekil 11.20'deki çizge izlemede kullanılır. Kenarları (A, B), (A, C), (A, D), (A, E), (A, F), (B, C), (G, H), (G, I), (H, I), (H, K), (I, J), (J, K), (J, L)'dir. Doğrulama betiği bütün alt kümeleri denemiştir. En küçük kapsama 5 düğümlüdür ve dört farklı en iyi çözüm vardır: {A, B, H, I, J}, {A, B, G, H, J}, {A, C, H, I, J} ve {A, C, G, H, J}. Dörtten azının yetmediği şöyle görülür: A, B, C üçgeni en az iki düğüm ister; G, H, I üçgeni de öyle. (J, L) kenarı da bu iki üçgenden ayrı bir düğüm ister.

11.5.3Tek uç eklemek neden yetmez?

Akla gelen ilk algoritma şudur. Başlangıçta kapsama kümesi boştur. Kapsanmamış bir kenar seçilir ve uçlarından biri kümeye eklenir. Bütün kenarlar kapsanana kadar bu adım tekrarlanır. Algoritma her zaman geçerli bir kapsama üretir, ama hangi ucun ekleneceğine dair bir kural koymadıkça kalitesi hakkında hiçbir şey söylenemez.

Şekil 11.21 kötü durumu gösterir. Merkez m beş yaprağa bağlıdır. Algoritma her kenarda yaprak ucunu seçerse kenarlar birer birer kapsanır ve sonunda beş yaprağın hepsi seçilir. Oysa yalnız merkezi seçmek bütün kenarları kapsar. n yapraklı bir yıldızda bu algoritmanın oranı n'dir ve girdiyle sınırsız büyür.

Doğru 2-yaklaşım küçük ama belirleyici bir değişiklik yapar. Kapsanmamış bir (u, v) kenarı seçilir ve u ile v'nin ikisi de kümeye eklenir. u ya da v'ye değen bütün kenarlar kapsanmış sayılır. Kenar kalmayana kadar bu adımlar tekrarlanır. Yıldızda bu algoritma ilk kenarın iki ucunu, yani merkezi ve bir yaprağı seçer. Bütün kenarlar kapsanır; sonuç 2 düğümdür ve en iyinin iki katıdır.

11.5.4Kenar seçen 2-yaklaşım: kod ve izleme

Sunumdaki Java kodu kenarları bir dizide alır ve onları sırayla işler:

Set<Character> dugumKapsama(char[][] kenarlar) {
  Set<Character> kapsama = new HashSet<>();
  for (char[] k : kenarlar) {
    char u = k[0], v = k[1];
    if (!kapsama.contains(u) && !kapsama.contains(v)) {
      kapsama.add(u); kapsama.add(v); }  // iki uç
  }
  return kapsama;
}

Her kenar iki karakterlik bir dizidir: k[0] ve k[1] uçlardır. Kapsama bir HashSet'te tutulur; contains ve add işlemleri ortalama O(1) sürer. Döngü her kenarda iki ucun da kapsamada olmadığını denetler. Öyleyse kenar henüz kapsanmamıştır ve iki ucu birden eklenir. Uçlardan biri zaten kapsamadaysa kenar kapsanmıştır ve atlanır. Kodda “kapsanmış sayma” işlemi ayrıca yazılmaz; bir kenar, uçlarından biri kümeye girdiği anda kendiliğinden kapsanmış olur ve sırası geldiğinde atlanır.

Maliyet açıktır. Her kenar bir kez incelenir ve her inceleme ortalama sabit sürer. Toplam süre O(V + E)'dir. Bellek kapsama kümesi için O(V)'dir.

Tablo 11.13, kodu Şekil 11.20'deki çizgede çalıştırır. Kenarlar yukarıdaki sırayla verilmiştir. İlk kenar (A, B)'nin iki ucu da dışarıdadır; A ve B eklenir. A'ya ya da B'ye değen sonraki beş kenar atlanır. (G, H) ikinci bağımsız kenardır; G ve H eklenir. (G, I), (H, I) ve (H, K) atlanır. (I, J)'nin iki ucu da dışarıdadır; I ve J eklenir. Kalan iki kenarı J kapsar.

Sonuç {A, B, G, H, I, J} kümesidir ve 6 düğüm içerir. En iyi değer 5 olduğu için oran 6/5 = 1,2'dir; garanti edilen 2'nin çok altındadır. Algoritmanın seçtiği üç kenar, (A, B), (G, H) ve (I, J), ortak ucu olmayan kenarlardır. Ortak ucu olmayan kenarlardan oluşan kümeye eşleştirme (matching) denir. Oran kanıtının anahtarı bu eşleştirmedir.

11.5.5Oran neden en fazla 2'dir?

Başka yaklaşımlar da vardır. En yüksek dereceli düğümü seçen açgözlü algoritma doğal görünür. Her adımda en çok kapsanmamış kenara değen düğümü alır. Şekil 11.20'deki çizgede, eşit derecelerde alfabetik sıra izlenirse, bu algoritma sırasıyla A, H, J, B, G'yi seçer ve 5 düğümle en iyiyi bulur. Ancak bu algoritmanın oranı yalnız O(log n) ile sınırlanabilir ve oranın gerçekten logaritmik büyüdüğü çizgeler kurulabilir. İyi bir sezgiseldir, ama sabit oranlı bir yaklaşım algoritması değildir.

Doğrusal programlama ile yuvarlama ikinci bir 2-yaklaşım verir. Her düğüme x_v ∈ {0, 1} değişkeni atanır ve her kenar için x_u + x_v ≥ 1 kısıtı yazılır; Σ x_v en küçüklenir. Tam sayı koşulu kaldırılıp 0 ≤ x_v ≤ 1 yazılırsa problem bir doğrusal programa, yani LP gevşetmesine dönüşür ve polinom sürede çözülür. Gevşetmenin değeri OPT'tan küçük ya da ona eşittir. Ardından x_v ≥ 1/2 olan düğümler seçilir. Her kenar kısıtında iki değişkenden en az biri 1/2'ye ulaştığı için sonuç geçerli bir kapsamadır. Seçilen her düğümün değeri en az 1/2 olduğu için eleman sayısı gevşetme değerinin en fazla iki katıdır.

2'den belirgin biçimde iyi sabit bir oran bilinmiyor. Benzersiz Oyunlar Varsayımı (Unique Games Conjecture) doğruysa her ε > 0 için 2 − ε oranlı polinom zamanlı bir algoritmanın olmadığı gösterilmiştir (Khot ve Regev, 2008). Basit görünen kenar seçen algoritma, bu varsayım altında en iyi olası sabit orana ulaşır.

11.5.6NP-tamlık: 3-SAT'tan indirgeme

Düğüm kapsamanın karar sürümünün NP-tam olduğu bir indirgemeyle gösterilir. İndirgeme, bilinen bir NP-tam problemin her örneğini polinom sürede düğüm kapsamanın bir örneğine dönüştürür ve iki örneğin yanıtı aynı olur. Kaynak problem olarak 3-SAT kullanılır. 3-SAT'ta bir mantık formülü, her biri üç değişmezden (literal) oluşan tümcelerin “ve” ile bağlanmasıdır; her tümce değişmezlerin “veya” ile bağlanmasıdır. Değişmez bir değişken ya da onun değilidir. Soru, formülü doğru yapan bir değer ataması olup olmadığıdır.

İndirgeme, l değişkenli ve m tümceli bir formülden şu çizgeyi kurar:

• Her x_i değişkeni için iki düğüm, x_i ve ¬x_i, ve aralarında bir kenar. Bu kenarı kapsamak için iki düğümden biri seçilmelidir; seçim değişkenin değerini belirler.
• Her tümce için üç düğümlü bir üçgen; düğümler tümcenin değişmezleriyle etiketlenir. Bir üçgeni kapsamak için üç düğümünden en az ikisi seçilmelidir.
• Her üçgen düğümü, aynı etiketli değişken düğümüne bir kenarla bağlanır.

Aranan kapsama boyutu k = l + 2m'dir: her değişken kenarından bir düğüm, her üçgenden iki düğüm. Çizgede 2l + 3m düğüm ve l + 6m kenar vardır; kurulum polinom süredir.

Sunumdaki örnek formül φ = (x₁ ∨ x₁ ∨ x₂) ∧ (¬x₁ ∨ ¬x₂ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₂)'dir. İki değişken ve üç tümce vardır; çizgede 4 + 9 = 13 düğüm ve 2 + 9 + 9 = 20 kenar bulunur. Aranan boyut k = 2 + 2 · 3 = 8'dir.

Formülü sağlayan atama x₁ = yanlış, x₂ = doğru'dur. Kapsama bu atamadan şöyle kurulur. x₁ yanlış olduğu için değişken kenarından ¬x₁ seçilir; x₂ doğru olduğu için x₂ seçilir. Her tümcede doğru bir değişmez vardır. O değişmezin üçgen düğümü dışarıda bırakılır ve öbür iki düğüm seçilir. Dışarıda kalan düğümün bağlantı kenarını ise değişken tarafında seçilmiş düğüm kapsar. C₁'de doğru değişmez x₂'dir; iki x₁ düğümü seçilir. C₂'de doğru değişmez ¬x₁'dir; iki ¬x₂ düğümü seçilir. C₃'te doğru değişmez ¬x₁'dir; iki x₂ düğümü seçilir.

Sonuçta 8 düğüm seçilmiştir ve 20 kenarın hepsi kapsanır (Şekil 11.24). Doğrulama betiği bu çizgede en küçük kapsamanın gerçekten 8 olduğunu ve formülü sağlayan tek atamanın x₁ = yanlış, x₂ = doğru olduğunu bütün olasılıkları deneyerek doğrulamıştır.

Ters yön de geçerlidir. k = l + 2m boyutlu bir kapsama, her değişken kenarından tam bir, her üçgenden tam iki düğüm içerir. Bu yapılar en az bir ve en az iki düğüm ister ve toplam tam olarak k'dir. Değişken tarafında seçilen düğümler bir atama tanımlar. Her üçgende dışarıda kalan düğümün bağlantı kenarı kapsanmış olmalıdır; bu yalnız değişken tarafındaki eşi seçilmişse mümkündür. Demek ki o değişmez atamada doğrudur ve tümce sağlanır. Sonuç: φ sağlanabilir ancak ve ancak çizgede l + 2m boyutlu bir düğüm kapsama vardır.

11.6Sırt çantası

0/1 sırt çantası probleminde n eşya vardır. i. eşyanın değeri v_i, ağırlığı w_i'dir. Çantanın kapasitesi W'dir. Toplam ağırlığı W'yi aşmayan ve toplam değeri en büyük olan eşya kümesi aranır. Her eşya ya bütünüyle alınır ya da hiç alınmaz. Problem NP-zordur. Dinamik programlamayla O(nW) sürede çözülür, ama bu süre W'nin sayısal değerine bağlıdır. W girdide log W bitle yazıldığı için süre girdinin boyutunda üsteldir.

11.6.1Oran sıralı açgözlü kural

En doğal açgözlü kural, eşyaları birim ağırlık başına değerlerine göre sıralamaktır. Eşyalar v_i / w_i oranına göre azalan sıraya konur ve sırayla incelenir. Çantaya sığan eşya alınır, sığmayan atlanır. Sıralama baskın maliyettir; süre O(n log n)'dir.

Tablo 11.14 sunumdaki yedi eşyalı örneği verir. En yüksek oranlı eşya 6'dır (20/7 ≈ 2,86) ve alınır; çantada 7 kilogram vardır. Sıradaki eşya 3, 4 kilogramdır ve sığmaz. Eşya 7 de sığmaz. Eşya 2, 3 kilogramdır ve çantayı tam 10 kilograma tamamlar. Bundan sonra hiçbir eşya sığmaz. Açgözlü toplam değer 20 + 5 = 25'tir. Doğrulama betiği 2⁷ = 128 alt kümenin hepsini denemiştir; en iyi değer de 25'tir ve yine eşya 2 ile 6'dan oluşur. Bu örnekte açgözlü kural en iyiyi bulur. Eşya 2 ile eşya 5'in oranı eşittir (5/3 = 10/6); tabloda eşya 2 önce gelir.

Eşyalar bölünebilseydi, yani problem kesirli sırt çantası olsaydı, bu kural her zaman en iyi sonucu verirdi: sığmayan ilk eşyanın bir parçası alınır ve çanta tam dolar. 0/1 sürümünde ise kuralın hiçbir garantisi yoktur.

11.6.2İyileştirilmiş kural: 2-yaklaşım

Kötü örneğin kaynağı tek bir değerli eşyadır. Oran sıralaması onu geride bırakır ve küçük eşyalar çantada yer kaplayınca o eşya artık sığmaz. Düzeltme basittir. Açgözlü değer, tek başına çantaya sığan en değerli eşyanın değeriyle karşılaştırılır ve büyük olan alınır:

sonuç = max( açgözlü değer, sığan en değerli tek eşya )

Kötü örnekte bu kural max(2, 10) = 10 bulur ve en iyiye ulaşır. Genel garanti de 2'dir.

11.6.3Tam polinom zamanlı yaklaşım şeması

Sırt çantası, 2'den çok daha iyi bir oranı kabul eden problemlerdendir. Her ε > 0 için en iyi değerin en az (1 − ε)'unu bulan ve süresi O(n³/ε) olan bir algoritma vardır. Bu, bir tam polinom zamanlı yaklaşım şemasıdır (FPTAS).

Fikir değerleri ölçeklemektir. Sırt çantasının değerlere göre kurulan bir dinamik programı vardır: her x değeri için “toplam değeri tam x olan en hafif eşya kümesinin ağırlığı” tablolanır. Tablonun boyu değerlerin toplamı kadardır ve süre O(n · Σ v_i) olur. Değerler büyükse bu süre büyüktür. FPTAS değerleri bir K = ε · v_max / n sayısına böler ve aşağı yuvarlar: v'_i = ⌊v_i / K⌋. Ölçeklenmiş değerlerin her biri en fazla n/ε'dur ve toplamları en fazla n²/ε'dur. Dinamik program bu küçük değerlerle O(n · n²/ε) = O(n³/ε) sürede çalışır ve ölçeklenmiş problemin en iyi çözümünü bulur.

Yuvarlamanın verdiği kayıp sınırlıdır. Her eşyanın değeri en fazla K kadar kaybedilir; en iyi küme en fazla n eşya içerdiği için toplam kayıp en fazla nK = ε · v_max ≤ ε · OPT'tur. Bu yüzden bulunan kümenin gerçek değeri en az (1 − ε) · OPT'tur. Sunumdaki özet tablosu bu oranı en küçükleme biçimine benzeterek 1 + ε diye yazar; iki yazım küçük ε için aynı garantiyi anlatır.

11.7Kuvvet yinelemesi

Şimdiye kadarki algoritmalar kombinatoryal problemlere yaklaşık çözümler üretti. Sayısal hesaplamada ise “yaklaşım” başka bir biçimde görülür: kesin değeri sonlu adımda bulmak yerine, her adımda ona biraz daha yaklaşan bir dizi üretilir. Bu davranışa yakınsama (convergence) denir. Yakınsamanın tipik örneği, bir matrisin en büyük özdeğerini bulan kuvvet yinelemesidir.

11.7.1Baskın özdeğer ve özvektör

Kare bir A matrisi için A · v = λ · v eşitliğini sağlayan sıfırdan farklı v vektörüne özvektör, λ sayısına da ona ait özdeğer denir. Özvektör, matrisle çarpılınca yönü değişmeyen, yalnız λ katına uzayan ya da kısalan vektördür. n × n bir matrisin en fazla n özdeğeri vardır. Mutlak değeri en büyük olana baskın özdeğer denir ve λ₁ ile gösterilir; ona ait özvektör v₁'dir.

Bütün özdeğerleri kesin olarak hesaplayan yöntemler O(n³) sürer. Matris binlerce satırlıysa bu kabul edilebilir; milyarlarca satırlıysa değildir. Kuvvet yinelemesi yalnız baskın özdeğeri ve özvektörü yaklaşık olarak verir, ama her adımı yalnız bir matris–vektör çarpımıdır. Bu çarpım yoğun bir matriste O(n²), seyrek bir matriste sıfır olmayan öğe sayısı kadar sürer. Dev boyutlu seyrek matrislerde kullanılabilen tek yöntem çoğunlukla budur.

En basit örnek köşegen bir matristir. A = [[2, 0], [0, 1]] matrisinin özdeğerleri 2 ve 1, özvektörleri (1, 0) ve (0, 1)'dir. x₀ = (1, 1) alınsın. Her çarpımda birinci bileşen 2 katına çıkar, ikinci bileşen aynı kalır: A^k x₀ = (2^k, 1). Normalleştirilmiş vektörün yönü giderek (1, 0)'a döner (Şekil 11.25). İkinci bileşenin birinciye oranı 2^−k'dır. Hata her adımda yarıya iner. Bu oranın 10⁻³'ün altına inmesi için 2^k > 1000 gerekir; 2⁹ = 512, 2¹⁰ = 1024 olduğundan k = 10 adım yeter.

11.7.2Adımlar ve yakınsamanın nedeni

Algoritmanın adımları şöyledir:

1. Bir A matrisi belirlenir ve sıfırdan farklı bir başlangıç vektörü x₀ seçilir. Rastgele seçmek yaygındır.
2. Vektör matrisle çarpılır: y = A · x_k.
3. Yeni vektörün normu, yani uzunluğu 1'e getirilir: x_k+1 = y / ‖y‖.
4. İkinci ve üçüncü adımlar, istenen sayıda ya da vektördeki değişim yeterince küçülene kadar tekrarlanır.

Sonuçta x_k, v₁'e yakınsar. Özdeğer tahmini için iki yol vardır. Normalleştirmeden önceki uzunluk ‖A · x_k‖, |λ₁|'e yakınsar. Simetrik matrislerde daha hızlı yakınsayan tahmin Rayleigh bölümüdür: ‖x_k‖ = 1 iken λ ≈ x_k^T A x_k.

Yöntemin neden çalıştığı, başlangıç vektörünün özvektörler cinsinden yazılmasıyla görülür. A'nın özvektörleri bir taban oluştursun ve x₀ = c₁ v₁ + c₂ v₂ + … + c_n v_n olsun. A ile her çarpım her bileşeni kendi özdeğeriyle çarpar:

A^k x₀ = λ₁^k [ c₁ v₁ + c₂ (λ₂/λ₁)^k v₂ + … + c_n (λ_n/λ₁)^k v_n ]

|λ₁| > |λ₂| ≥ … ≥ |λ_n| ise köşeli parantezin içindeki (λ_i/λ₁)^k çarpanlarının hepsi geometrik olarak sıfıra iner. Geriye c₁ v₁ kalır. Normalleştirme baştaki λ₁^k çarpanını siler ve vektör v₁ yönünde birim vektöre yaklaşır. Sönmesi en yavaş olan bileşen v₂'ninkidir. Bu yüzden hata her adımda yaklaşık |λ₂/λ₁| katına iner. Oran 0,1 ise her adımda bir doğru basamak kazanılır; oran 0,99 ise bir basamak için yaklaşık 230 adım gerekir.

Formül iki koşulu da açıkça gösterir. Birincisi c₁ ≠ 0 olmalıdır; başlangıç vektörü v₁'e dik seçilirse v₁ bileşeni hiç yoktur ve kuramsal olarak ortaya çıkmaz. Pratikte yuvarlama hataları küçük bir v₁ bileşeni yaratır, ama yakınsama gecikir. Rastgele seçilen bir vektörün tam dik olma olasılığı sıfırdır. İkincisi |λ₁| > |λ₂| olmalıdır. Mutlak değerce eşit iki özdeğer varsa, örneğin λ₁ = 3 ve λ₂ = −3, ikinci bileşen sönmez ve vektör iki yön arasında gidip gelebilir.

11.7.3Adım adım yakınsama

Sunumdaki örnek simetrik bir matristir: A = [[2, 1], [1, 3]]. Karakteristik denklem (2 − λ)(3 − λ) − 1 = λ² − 5λ + 5 = 0'dır ve kökleri λ₁ = (5 + √5)/2 ≈ 3,618 ile λ₂ = (5 − √5)/2 ≈ 1,382'dir. Baskın özvektör, uzunluğu 1 olacak biçimde v₁ ≈ (0,5257; 0,8507)'dir. Oran λ₂/λ₁ ≈ 0,382'dir. Başlangıç vektörü x₀ = (1, 0)'dır ve hatası ‖x₀ − v₁‖ ≈ 0,974'tür.

Tablo 11.15 ilk dokuz adımı verir. İlk adımda A · (1, 0) = (2, 1)'dir. Uzunluğu √5 ≈ 2,236'dır ve bölününce x₁ = (0,894; 0,447) çıkar. Rayleigh bölümü x₁^T A x₁ = 3,0'dır. İkinci adımda A · x₁ = (2,236; 2,236) olur; vektör tam köşegen yöne döner ve λ ≈ 3,5'tir. Üçüncü adımda x₃ = (0,6; 0,8) ve λ ≈ 3,6 bulunur. Sonraki adımlarda λ tahmini hızla 3,618'e oturur.

Hata sütunu yakınsama hızını açıkça gösterir. Ardışık iki hatanın oranı ilk adımlarda 0,42 ve 0,39'dur; dördüncü adımdan sonra 0,382 ≈ λ₂/λ₁'e oturur. Hata her adımda yaklaşık 0,38 katına iner. Log ölçekli grafikte bu davranış eğimi log₁₀ 0,382 ≈ −0,42 olan bir doğrudur (Şekil 11.26). Sayısal analizde böyle bir yakınsamaya doğrusal ya da geometrik yakınsama denir. Her adım yaklaşık 0,42 ondalık basamak kazandırır; bir basamak için iki buçuk adım gerekir. Özdeğer tahmini özvektörden daha hızlı yakınsar: simetrik matriste Rayleigh bölümünün hatası, vektör hatasının karesiyle orantılıdır. Dokuzuncu adımda vektör hatası 2,8 · 10⁻⁴ iken λ altı basamağa kadar doğrudur.

11.7.4Java kodu ve 3 × 3 örnek

Sunumdaki Java kodu algoritmayı sabit sayıda adımla çalıştırır:

double[] kuvvet(double[][] a, int adim) {
  int n = a.length;
  double[] x = new double[n];
  Arrays.fill(x, 1.0);     // x₀ ≠ 0
  for (int k = 0; k < adim; k++) {
    double[] y = new double[n];
    for (int i = 0; i < n; i++)  // y = A·x
      for (int j = 0; j < n; j++)
        y[i] += a[i][j] * x[j];
    double norm = 0;
    for (double yi : y) norm += yi * yi;
    norm = Math.sqrt(norm);
    for (int i = 0; i < n; i++)  // ‖x‖ = 1
      x[i] = y[i] / norm;
  }
  return x;
}

Metot matrisi a ve adım sayısını adim olarak alır. Başlangıç vektörü bütün bileşenleri 1 olan vektördür. Bu seçim basittir ve çoğu matriste c₁ ≠ 0 koşulunu sağlar. Dış döngünün her turunda önce y = A · x çarpımı iki iç içe döngüyle hesaplanır; y[i], A'nın i. satırı ile x'in iç çarpımıdır. Sonra y'nin Öklid normu, bileşenlerin karelerinin toplamının karekökü olarak bulunur. Son olarak x, y / norm yapılır. Metot son x'i döndürür; norm değeri döndürülmez, ama λ₁ tahmini olarak kullanılabilir.

Her adımda çarpım n² çarpma ve toplama yapar; normalleştirme O(n) sürer. adim adımlık toplam süre O(adim · n²)'dir. Bellek x ve y için O(n)'dir; matrisin kendisi değiştirilmez. Kod bir durma ölçütü kullanmaz. Pratik uygulamalarda döngü, ardışık iki x arasındaki fark bir eşiğin altına inince durdurulur.

Sunumdaki örnek matris şudur:

A = [[0,511; 0,32; 0,12], [0,211; 0,62; 0,12], [0,311; 0,12; 0,16]], x₀ = (1, 1, 1)

Bu matrisin özdeğerleri yaklaşık 0,9008; 0,3 ve 0,0902'dir. Oran λ₂/λ₁ = 0,3 / 0,9008 ≈ 0,33'tür; yakınsama hızlıdır. Matrisin bir özelliği de dikkat çeker. Birinci ve ikinci satırın ilk iki öğesinin toplamı aynıdır (0,511 + 0,32 = 0,211 + 0,62 = 0,831) ve üçüncü öğeleri eşittir. Bu yüzden x'in ilk iki bileşeni eşitse A · x'inkiler de eşit kalır. x₀ = (1, 1, 1) bu özelliği taşıdığı için yinelemenin her adımında x₁ = x₂'dir.

İlk adımda y[0], birinci satırın x ile çarpımıdır: 0,511 · 1 + 0,32 · 1 + 0,12 · 1 = 0,951. y[1] de aynı nedenle 0,951'dir, y[2] ise 0,311 + 0,12 + 0,16 = 0,591'dir. Norm √(0,951² + 0,951² + 0,591²) ≈ 1,4690'dır. Bölününce x = (0,6474; 0,6474; 0,4023) elde edilir. Bu vektörün uzunluğu 1'dir; sayılar artık ne büyür ne söner.

İkinci adımda y = (0,5862; 0,5862; 0,3434)'tür. Bileşenlerin oranı ilk adımdakine çok yakındır; yön az değişmiştir. Norm 0,8974'tür. Üçüncü adımda norm 0,9005'e, dördüncüde 0,9008'e çıkar ve orada kalır. Normun λ₁ = 0,9008'e yakınsadığı görülür. Vektör dördüncü adımdan sonra dört basamakta değişmez: v₁ ∝ (0,6539; 0,6539; 0,3805).

Sunumdaki izleme adim = 3 ile durur ve x ≈ (0,6539; 0,6539; 0,3807) döndürür; üçüncü bileşen bir adım sonra 0,3805'e oturur. Adım sayısı istenen doğruluğa göre seçilmelidir: hatanın 10^−d katına inmesi için yaklaşık d / log₁₀(λ₁/|λ₂|) adım gerekir. Burada oran yaklaşık 3'tür ve her adım yarım basamaktan biraz az (log₁₀ 3 ≈ 0,48) kazandırır.

11.7.5Sınırlar ve uygulamalar

Kuvvet yinelemesinin güçlü yanları sadeliğinden gelir. Yalnız matris–vektör çarpımı kullanır. Matrisin kendisini değiştirmez ve ek bellek olarak yalnız birkaç vektör, yani O(n) yer ister. Bu yüzden milyarlarca satırı olan seyrek matrislere de uygulanabilir.

Sınırları da açıktır. Yalnız baskın özdeğeri bulur. |λ₂|, |λ₁|'e yakınsa çok yavaş yakınsar; eşitse yakınsamayabilir. Başlangıç vektörü v₁'e dik seçilirse (c₁ = 0) kuramsal olarak başarısız olur.

Yöntemin en ünlü uygulaması Google'ın PageRank hesabıdır. Bir sayfanın önemi, ona bağlantı veren sayfaların önemine göre belirlenir; bu tanım bir özvektör denklemidir. Sayfaların önem değerleri, web bağlantı matrisinin baskın özvektörüdür. Matrisin milyarlarca satırı vardır ama çok seyrektir ve kuvvet yinelemesi birkaç düzine adımda yeterli doğruluğa ulaşır. Türevleri de yaygındır: ters yineleme en küçük özdeğeri, kaydırmalı yineleme belirli bir değere en yakın özdeğeri bulur; Lanczos ve Arnoldi yöntemleri birkaç özdeğeri birlikte hesaplar. Temel bileşenler çözümlemesinde (PCA) ilk temel bileşen de bu yolla bulunabilir.

11.8Karşılaştırma ve sık yapılan hatalar

Tablo 11.17 notta incelenen algoritmaları problem, oran ve süre bakımından yan yana koyar.

Notun çeşitli yerlerinde ele alınan sık hatalar şunlardır:

• Sezgiseli yaklaşım algoritması sanmak. En yakın komşu ve 2-opt iyi sonuç verir, ama oran garantisi yoktur. Yaklaşım algoritması kanıtlanmış bir ρ ister.
• Oranı ters yazmak. En küçüklemede C ≤ ρ · C*, en büyüklemede C ≥ C* / ρ. ρ her zaman en az 1'dir.
• Kapsamada tek uç eklemek. Kenarın yalnız bir ucunu eklemek yıldız çizgede n kat kötü sonuç verebilir; 2-yaklaşım iki ucu da ekler.
• Üçgen eşitsizliğini unutmak. MST tabanlı 2-yaklaşımın kısayol adımı yalnız metrik TSP'de yolu uzatmaz.
• Metasezgiseli kesin sanmak. Benzetimli tavlama ve genetik algoritma en iyiye ulaşmayı garanti etmez; farklı tohum ve parametrelerle birkaç kez çalıştırılıp en iyi sonuç alınır.
• Normalleştirmeyi atlamak. Kuvvet yinelemesinde x her adımda normalleştirilmezse sayılar taşar (|λ₁| > 1) ya da sıfıra iner.

11.9Özet

• Yaklaşım algoritması: NP-zor bir en iyileme problemi için polinom sürede çalışır ve her girdide max(C/C*, C*/C) ≤ ρ koşulunu sağlar; en küçüklemede C ≤ ρ · C*, en büyüklemede C ≥ C*/ρ.
• Yöntem türleri: kesin algoritma, yaklaşım algoritması, PTAS, FPTAS (süre 1/ε'da da polinom), sezgisel ve metasezgisel (garanti yok).
• TSP: kaba kuvvet (n − 1)!/2 tur, Held–Karp O(n² 2ⁿ). Genel TSP'de P ≠ NP ise sabit oranlı yaklaşım yoktur. En yakın komşu O(n²)'dir ama oranı Θ(log n) olabilir.
• Metrik TSP: w(T) ≤ OPT ve kısayollu tur ≤ 2 · w(T); yedi şehirde 287,7 / 282,5. Christofides 1,5 oranını verir.
• 2-opt: kazanç Δ = d(a,c) + d(b,d) − d(a,b) − d(c,d); yerel optimumda kesişen kenar kalmaz; 28 şehirde 48 hamleyle 1269,8'den 430,8'e. Metasezgiseller yerel optimumdan kaçabilir ama garanti vermez.
• Makine çizelgeleme: liste çizelgeleme 2 − 1/m, LPT 4/3 − 1/(3m); alt sınırlar Σp/m ve max p; iki sınır da sıkıdır.
• Düğüm kapsama: kapsanmamış bir kenarın iki ucu eklenir; seçilen kenarlar eşleştirmedir, |C| = 2|M| ≤ 2 · OPT, süre O(V + E). 3-SAT indirgemesinde k = l + 2m.
• Sırt çantası: max(oran sıralı açgözlü, en değerli tek eşya) 2-yaklaşımdır; değer ölçekleme FPTAS verir.
• Kuvvet yinelemesi: x_k+1 = A x_k / ‖A x_k‖ → v₁; hata her adımda yaklaşık |λ₂/λ₁| katına iner; koşullar c₁ ≠ 0 ve |λ₁| > |λ₂|.

11.10Kavram listesi

• yaklaşım algoritması approximation algorithm
• yaklaşım oranı approximation ratio
• yaklaşım şeması approximation scheme (PTAS / FPTAS)
• sezgisel heuristic
• metasezgisel metaheuristic
• gezgin satıcı problemi travelling salesman problem (TSP)
• Hamilton çevrimi Hamiltonian cycle
• üçgen eşitsizliği triangle inequality
• minimum kapsayan ağaç minimum spanning tree (MST)
• en yakın komşu nearest neighbor
• yerel arama local search
• yerel optimum local optimum
• benzetimli tavlama simulated annealing
• liste çizelgeleme list scheduling
• en büyük yük makespan
• en uzun iş önce longest processing time first (LPT)
• düğüm kapsama vertex cover
• eşleştirme matching
• indirgeme reduction
• LP gevşetmesi LP relaxation
• 0/1 sırt çantası 0/1 knapsack
• kuvvet yinelemesi power iteration
• yakınsama convergence

11.11Kendini Dene

1. Bir 2-yaklaşım algoritması bir en küçükleme probleminde 50 maliyetli bir çözüm buluyor. En iyi maliyet hangi aralıktadır? Aynı sonuç bir en büyükleme probleminde bulunsaydı aralık ne olurdu?

   Cevap

   En küçüklemede 50 ≤ 2 · OPT olduğundan OPT ≥ 25'tir; en iyi çözüm bulunan çözümden kötü olamayacağı için OPT ≤ 50'dir. Aralık [25, 50]'dir. En büyüklemede 50 ≥ OPT / 2 olduğundan OPT ≤ 100'dür ve OPT ≥ 50'dir. Aralık [50, 100]'dür.

2. Dört şehrin uzaklık matrisi satır satır 0: (0 1 15 6), 1: (1 0 7 3), 2: (15 7 0 2), 3: (6 3 2 0) olsun. En yakın komşu 0'dan başlayınca hangi turu bulur? En iyi tur nedir? Matris metrik midir?

   Cevap

   0'dan en yakın şehir 1'dir (1). 1'den ziyaret edilmemişler 2 (7) ve 3 (3); 3 seçilir. 3'ten tek aday 2'dir (2). 2'den 0'a dönülür (15). Tur 0 → 1 → 3 → 2 → 0, uzunluk 1 + 3 + 2 + 15 = 21'dir. Dört şehirde üç farklı tur vardır: 0 → 1 → 2 → 3 → 0 (16), 0 → 1 → 3 → 2 → 0 (21) ve 0 → 2 → 1 → 3 → 0 (31). En iyisi 16'dır. Matris metrik değildir: d[0][2] = 15 > d[0][1] + d[1][2] = 8. Ucuz seçimler pahalı dönüş kenarını sona bırakmıştır.

3. Noktalar a (0, 0), b (3, 4), c (6, 0), d (3, −4) ve turda (a, b) ile (c, d) kenarları var. 2-opt kazancı nedir; hamle yapılır mı? Kenarlar birbirini kesiyor mu?

   Cevap

   d(a, b) = d(c, d) = 5, d(a, c) = 6, d(b, d) = 8'dir. Δ = 6 + 8 − 5 − 5 = 4 > 0; hamle turu uzatır ve yapılmaz. İki kenar kesişmez: (a, b) eksenin üstünde, (c, d) altındadır. Kesişmeyen kenar çiftlerinde 2-opt kazancı pozitif olabilir; geometrik sonuç yalnız kesişen kenarlar için bir iyileşme garanti eder.

4. Süreleri 1, 2, 3, 4, 5, 6 olan işler m = 3 makineye bu sırayla liste çizelgelemeyle veriliyor. Makine yükleri ve C_max nedir? LPT ne bulur? En iyi değer kaçtır?

   Cevap

   Liste: 1, 2, 3 üç makineye gider (yükler 1, 2, 3). 4 en az yüklü birinci makineye (5), 5 ikinciye (7), 6 üçüncüye (9) gider. Yükler 5, 7, 9; C_max = 9. LPT sırası 6, 5, 4, 3, 2, 1'dir: 6, 5, 4 üç makineye; 3 en az yüklü üçüncüye (7), 2 ikinciye (7), 1 birinciye (7). Yükler 7, 7, 7. Toplam iş 21 olduğundan alt sınır 7'dir; LPT en iyiyi bulur. Liste çizelgelemenin oranı 9/7 ≈ 1,29'dur ve 2 − 1/3 ≈ 1,67 sınırının altındadır.

5. Altı düğümlü 1–2–3–4–5–6–1 çevriminin kenarları (1,2), (2,3), (3,4), (4,5), (5,6), (6,1) sırasıyla kenar seçen 2-yaklaşıma veriliyor. Kaç düğüm seçilir? Kenarlar (2,3), (5,6), (1,2), (3,4), (4,5), (6,1) sırasıyla verilseydi sonuç ne olurdu? En iyi değer nedir?

   Cevap

   İlk sırada (1,2), (3,4) ve (5,6) seçilir; sonuç 6 düğümdür. İkinci sırada (2,3) ve (5,6) seçilir; kalan dört kenarın birer ucu kapsamadadır ve sonuç {2, 3, 5, 6}, 4 düğümdür. En iyi kapsama 3 düğümdür, örneğin {1, 3, 5}. Oranlar 2 ve 4/3'tür. Kenar sırası sonucu değiştirir, ama garanti her sırada geçerlidir.

6. W = 50 ve eşyalar (değer, ağırlık) olarak (60, 10), (100, 20), (120, 30) olsun. Oran sıralı açgözlü kural, iyileştirilmiş kural ve en iyi 0/1 çözüm ne bulur? Kesirli sürümün değeri nedir?

   Cevap

   Oranlar 6, 5 ve 4'tür. Açgözlü kural (60, 10) ve (100, 20)'yi alır (30 kg); (120, 30) sığmaz (60 kg). Açgözlü değer 160'tır. Sığan en değerli tek eşya 120'dir; iyileştirilmiş kural max(160, 120) = 160 bulur. En iyi 0/1 çözüm (100, 20) ve (120, 30)'u alır: tam 50 kg, 220 değer. Oran 220/160 = 1,375 ≤ 2'dir. Kesirli sürümde ilk iki eşya ve üçüncünün 2/3'ü alınır: 60 + 100 + 80 = 240.

7. A = [[2, 1], [1, 2]] ve x₀ = (1, 0) için kuvvet yinelemesinin ilk adımını yapınız. Özdeğerler 3 ve 1 olduğuna göre hatanın 10⁻⁶ katına inmesi için yaklaşık kaç adım gerekir?

   Cevap

   y = A · x₀ = (2, 1), ‖y‖ = √5 ≈ 2,2361, x₁ = (0,8944; 0,4472). Rayleigh bölümü x₁^T A x₁ = 2,8'dir; gerçek değer 3'tür. Hata her adımda yaklaşık 1/3 katına iner. (1/3)^k < 10⁻⁶ için k > 6 / log₁₀ 3 ≈ 12,6, yani 13 adım gerekir.

8. Bütün uzaklıkları 1 ya da 2 olan bir TSP örneği metrik midir? Bu örneğe MST tabanlı 2-yaklaşım uygulanabilir mi?

   Cevap

   Evet, metriktir. Her i, j, k için d_ij ≤ 2'dir; ayrıca d_ik + d_kj ≥ 1 + 1 = 2'dir. Üçgen eşitsizliği her zaman sağlanır. Bu yüzden MST tabanlı algoritma uygulanabilir ve 2 · OPT garantisi geçerlidir. Hamilton çevrimi kanıtındaki kurgu ise ağır kenarı ρn + 1 yaptığı için metrik değildir; ağırlıklar 1 ve 2 ile sınırlanınca o kanıt çalışmaz.

11.12İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 35: düğüm kapsama, metrik TSP ve küme kapsama için yaklaşım algoritmaları, Hamilton çevrimi indirgemesinin tam kanıtıyla birlikte.
• D. P. Williamson ve D. B. Shmoys, The Design of Approximation Algorithms (2011): açgözlü, yerel arama, doğrusal programlama ve yaklaşım şemaları tekniklerini düzenli bir sırayla anlatır; kitabın elektronik sürümü yazarların sitesinde ücretsizdir.
• V. V. Vazirani, Approximation Algorithms (2001): kapsama, sırt çantası FPTAS'ı ve birincil–eşlenik yöntemleri kısa ve kesin kanıtlarla verir.
• G. H. Golub ve C. F. Van Loan, Matrix Computations (4. baskı, 2013): kuvvet yinelemesinin yakınsama analizi, ters ve kaydırmalı yineleme, Lanczos yöntemi.

11.13Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 35: Approximation Algorithms).
2. N. Christofides, “Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem”, Rapor 388, Carnegie Mellon Üniversitesi, 1976.
3. G. H. Golub, C. F. Van Loan, Matrix Computations, 4. baskı, Johns Hopkins University Press, 2013.
4. R. L. Graham, “Bounds on Multiprocessing Timing Anomalies”, SIAM Journal on Applied Mathematics 17(2), 1969.
5. A. R. Karlin, N. Klein, S. Oveis Gharan, “A (Slightly) Improved Approximation Algorithm for Metric TSP”, Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 2021.
6. M. Sipser, Introduction to the Theory of Computation, 3. baskı, Cengage, 2012 (3-SAT → düğüm kapsama indirgemesi).
7. V. V. Vazirani, Approximation Algorithms, Springer, 2001.
8. D. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

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