Bölüm 7: Açgözlü Algoritmalar

7.1Açgözlü yaklaşım

Birçok algoritma problemi bir dizi karardan oluşur. Hangi para verilecek, hangi etkinlik seçilecek, hangi iş hangi saate konacak, hangi kenar ağaca eklenecek? Bu kararların sırasıyla verilmesi gerekir ve her karar sonrakileri etkiler. Bütün karar dizilerini tek tek denemek doğru sonucu verir, ama dizilerin sayısı girdiyle birlikte üstel olarak büyür. Açgözlü yaklaşım bu ağacın yalnız tek bir dalını izler: her adımda o an en iyi görünen seçeneği alır ve yoluna devam eder.

7.1.1Adım adım karar vermek

Açgözlü bir algoritma bir define avcısına benzer. Avcı her yol ayrımında en çok altın görünen yöne sapar. Haritanın bütününe bakmaz; yalnız önündeki seçeneklere odaklanır. Yolculuk planlarken her kavşakta hedefe en kısa görünen yolu seçmek de aynı davranıştır. Bazen bu kısa görünen yol bir çıkmaza ya da uzun bir dolambaca götürür. Algoritma geri dönmediği için bu yanlış adımı düzeltemez.

Yaklaşımın iki yüzü bu örnekte açıkça görülür. Bir yanda hız ve sadelik vardır. Her adımda yalnız bir seçenek seçilir, seçilmeyenler bir daha incelenmez. Çoğu açgözlü algoritma adayları bir kez sıralar ve sonra tek geçişte karar verir. Öbür yanda ise garanti eksikliği vardır. O an en iyi görünen seçim, bütünün en iyi çözümüne her zaman götürmez. Açgözlü algoritma birçok problemde iyi bir yaklaşık çözüm üretir, ama en iyi (optimal) çözümü bulduğu ancak kanıtla gösterilebilir.

Bu notta “en iyi çözüm”, “optimal çözüm” ve “optimum” aynı anlamda kullanılır. Bir problemin birden çok en iyi çözümü olabilir. Örneğin aynı sayıda etkinliği içeren iki farklı etkinlik kümesi, ikisi de en büyük sayıya ulaşıyorsa ikisi de en iyidir. Açgözlü algoritmanın bunlardan herhangi birini bulması yeterlidir.

7.1.2Genel şablon

Açgözlü algoritmaların çoğu aynı iskeleti izler. Önce hangi seçimlerin kısıtları bozmadığı, yani uygun (olurlu) çözümlerin ne olduğu belirlenir. Ardından bir açgözlü ölçüt seçilir: en ucuz, en erken biten, en kârlı, en sık geçen gibi. Adaylar bu ölçüte göre sıralanır. Sonra her aday sırayla incelenir. Aday mevcut çözüme eklendiğinde kısıtlar bozulmuyorsa eklenir, bozuluyorsa atlanır. Çözüm tamamlanınca algoritma durur. Sunumdaki şablon kod bu iskeleti Java biçiminde gösterir:

Cozum acgozlu(Aday[] adaylar) {
  Cozum s = new Cozum();   // boş çözüm
  sirala(adaylar);         // ölçüte göre
  for (Aday a : adaylar) {
    if (s.uygunMu(a))      // kısıt bozulmaz
      s.ekle(a);           // geri alınmaz
  }
  return s;
}

Koddaki Cozum ve Aday soyut adlardır; her problemde başka bir anlam taşırlar. Para üstünde aday bir madeni para, çözüm verilen paraların listesidir. Etkinlik seçiminde aday bir etkinlik, çözüm seçilmiş etkinliklerin kümesidir. sirala çağrısı adayları açgözlü ölçüte göre dizer. uygunMu yeni adayın kısıtları bozup bozmadığını denetler. Döngü her adayı bir kez ele alır ve ekle ile çözüme katılan aday bir daha çıkarılmaz. Koddaki yorumlar bu iki özelliği vurgular: denetim kısıtları korur, ekleme ise geri alınmaz.

Şekil 7.1 bu tek geçişi gösterir. Altı aday sıralanmış olarak gelir. a1 ve a2 kısıtları bozmaz ve eklenir. a3, o ana kadar seçilenlerle çatışır ve atlanır. a4 eklenir, a5 atlanır, a6 eklenir. Sonuç {a1, a2, a4, a6} kümesidir. a3'ün atlanması kalıcıdır: a4 ve a6 eklendikten sonra a3'e geri dönülüp “şimdi uygun mu?” diye sorulmaz.

Şablonun maliyeti iki kısımdan oluşur. n adayın sıralanması O(n log n) sürer. Ardından gelen tarama her aday için bir uygunMu denetimi yapar. Denetim sabit sürede bitiyorsa tarama O(n) sürer ve toplam maliyeti sıralama belirler: O(n log n). Bazı problemlerde adaylar baştan sıralanmaz; her adımda en iyi aday bir öncelikli kuyruktan alınır. Huffman kodlamada ve Prim algoritmasında durum budur. Kuyruk işlemlerinin her biri O(log n) sürdüğü için toplam maliyet yine çoğunlukla O(n log n) düzeyindedir. Denetim pahalıysa, örneğin iş sıralamadaki gibi bir boş zaman dilimi aranıyorsa, maliyetin baskın kısmı denetime geçer.

7.1.3Açgözlü seçim özelliği ve optimal alt yapı

Açgözlü bir algoritmanın en iyi sonucu vermesi için problemin iki özelliği birlikte taşıması gerekir. Birincisi ilk adımla ilgilidir: algoritmanın yaptığı ilk seçim, en iyi çözüme giden yolu kapatmamalıdır. İkincisi geri kalan işle ilgilidir. İlk seçimden sonra kalan problem aynı türden, daha küçük bir problem olmalıdır. Onun en iyi çözümü ilk seçimle birleşince bütünün en iyi çözümü çıkmalıdır.

İki özelliğin birlikte ne sağladığı tümevarımla görülür. Açgözlü seçim özelliği, ilk seçimi içeren bir en iyi çözüm olduğunu söyler. Bu seçim yapıldıktan sonra kalan problem aynı türdendir. Optimal alt yapı, kalan problemin en iyi çözümü ile ilk seçimin birleşiminin bütünün en iyi çözümü olduğunu söyler. Kalan problemde de açgözlü seçim özelliği geçerli olduğu için algoritmanın ikinci seçimi de yanlış yola sokmaz. Bu böyle sürer; her adımda elimizdeki kısmi çözüm, bir en iyi çözümün parçası olarak kalır. Algoritma bittiğinde kısmi çözüm tamdır ve en iyidir.

Tanımdaki “en az bir” sözcükleri önemlidir. Açgözlü seçim özelliği, her en iyi çözümün açgözlü seçimi içerdiğini söylemez. Etkinlik seçimi bunun iyi bir örneğidir: sunumdaki on etkinlikli örnekte en büyük boyut 6'dır ve bu boyutta iki farklı küme vardır. Bunlardan yalnız biri en erken biten etkinliği içerir. Özellik için bu kadarı yeterlidir.

Optimal alt yapı yalnız açgözlü algoritmalara özgü değildir. Dinamik programlama da bu özelliğe dayanır. İki yaklaşımı ayıran, açgözlü seçim özelliğidir. Dinamik programlama bir sonraki adımda hangi seçimin en iyi olduğunu bilmez; bütün seçenekleri dener ve alt problemlerin sonuçlarını bir tabloda saklar. Açgözlü algoritma ise hangi seçimin güvenli olduğunu baştan bilir ve yalnız onu yapar. Bu yüzden açgözlü algoritma, uygulanabildiği problemlerde dinamik programlamadan çok daha hızlıdır.

İki özellik birlikte sağlanmıyorsa açgözlü algoritma yalnız bir sezgisel (heuristic) yöntemdir. Sezgisel yöntem hızlıdır ve çoğu girdide makul bir sonuç verir. Ancak sonucun en iyiden ne kadar kötü olabileceğini kendi başına söylemez. {4, 3, 1} paralarıyla para üstü bunun en basit örneğidir: 6 tutarı için açgözlü algoritma 3 para verir, oysa 2 para yeterlidir.

7.1.4Değiştirme argümanı

Açgözlü seçim özelliğini kanıtlamanın en yaygın yolu değiştirme argümanıdır (exchange argument). Kanıt keyfi bir en iyi çözümle başlar. Bu çözüme O denir. O açgözlü seçimi zaten içeriyorsa söylenecek bir şey yoktur. İçermiyorsa, O'daki uygun bir öğe çıkarılır ve yerine açgözlü seçim konur. Kanıtın asıl işi iki şeyi göstermektir:

1. Değişiklikten sonra çözüm hâlâ uygundur; hiçbir kısıt bozulmaz.
2. Değişiklikten sonra çözüm daha kötü olmaz; amaç değeri ya aynı kalır ya iyileşir.

Bu iki madde gösterilince açgözlü seçimi içeren bir en iyi çözüm bulunmuş olur. Optimal alt yapı ile birlikte tümevarım uygulanır ve sonuç bütün adımlara yayılır.

Argümanın gücü, en iyi çözümün neye benzediğini bilmeye gerek bırakmamasıdır. O hakkında yalnız uygun ve en iyi olduğu bilinir. Kanıt O'yu adım adım açgözlü çözüme benzetir ve her adımda kalitenin düşmediğini gösterir. Açgözlü kanıtların çoğu bu kalıba uyar. Etkinlik seçiminde ilk etkinlik değiştirilir. Kesirli sırt çantasında bir nesnenin bir parçası başka bir nesnenin parçasıyla yer değiştirir. Kesim özelliğinde bir kenar başka bir kenarla, Huffman kodlamada iki yaprak birbiriyle yer değiştirir.

Örnek kolay görünür, çünkü kısıt yalnız seçilen öğe sayısıyla ilgilidir. Kısıtlar karmaşıklaştıkça değiştirmenin uygunluğu bozmadığını göstermek zorlaşır. Etkinlik seçiminde bu adım bitiş zamanlarının karşılaştırılmasını, Huffman kodlamada ise ağaçtaki derinliklerin karşılaştırılmasını gerektirir.

7.1.5Güçlü ve zayıf yanlar

Açgözlü yaklaşımın güçlü yanları kısaca şöyle sıralanabilir:

• Anlaşılır ve kısa kod. Algoritmanın tamamı çoğu zaman bir sıralama ve bir döngüden oluşur. Bu notta verilen Java kodlarının hiçbiri yirmi satırı geçmez.
• Hız. Sıralama ve tek geçiş toplam O(n log n) sürer. Aynı problemi dinamik programlama ile çözmek çoğu zaman bir tablo doldurmayı ve daha yüksek bir maliyeti gerektirir.
• Az bellek. Yalnız mevcut kısmi çözüm tutulur. Alt problemlerin sonuçlarını saklayan bir tablo gerekmez.
• Doğru problemde en iyi sonuç. Minimum kapsayan ağaç, Huffman kodlama ve etkinlik seçimi gibi problemlerde açgözlü algoritma kanıtlanmış olarak en iyidir.
• Zor problemlerde iyi bir başlangıç. En iyi çözümü bulmanın çok pahalı olduğu problemlerde açgözlü algoritma hızlı bir yaklaşık çözüm ya da daha iyi yöntemler için bir başlangıç noktası verir.

Zayıf yanlar da en az bunlar kadar önemlidir:

• Garanti yoktur. {1, 3, 4} paralarıyla para üstü ve 0/1 sırt çantası, açgözlü sonucun en iyiden kötü olduğu bilinen örneklerdir.
• Her problem için ayrı kanıt gerekir. Bir açgözlü algoritmanın bir problemde doğru olması, benzer görünen başka bir problemde doğru olacağını göstermez.
• Ölçüt seçimi belirleyicidir. Aynı problem için akla gelen birçok ölçütten genellikle yalnız biri doğrudur. Yanlış ölçüt, kodu tamamen doğru yazılmış bir algoritmayı yanlış yapar.
• Hata düzeltilemez. Bir karar verildikten sonra geri alınmadığı için erken yapılan kötü bir seçimin etkisi sonuna kadar taşınır.

7.1.6Açgözlü yaklaşım ve böl ve fethet

Böl ve fethet de bir problemi daha küçük problemlere indirger. Bu benzerlik iki yaklaşımın karıştırılmasına yol açabilir. Aradaki fark, küçültmenin nasıl yapıldığındadır. Böl ve fethet problemi önceden belirlenmiş bir kuralla böler, örneğin diziyi ortadan ikiye. Bu bölmede bir seçim yoktur. Sonra bütün parçaları çözer ve sonuçları birleştirir. Açgözlü yaklaşım ise bir seçim yapar ve bu seçimden sonra geriye tek bir alt problem kalır. O alt problem çözülür; başka bir parça yoktur. Tablo 7.1 farkları beş başlık altında toplar.

Maliyet satırı da bu farkı yansıtır. Birleştirme sıralamasının süresi T(n) = 2T(n/2) + O(n) bağıntısından ana teoremle bulunur ve O(n log n)'dir. Açgözlü bir algoritmanın süresi için genellikle bir bağıntı kurmaya gerek yoktur; sıralama ve tarama maliyetleri doğrudan toplanır. Doğruluk satırı ise iki yaklaşımın en önemli farkını gösterir. Böl ve fethette alt problemler doğru çözülür ve birleştirme doğruysa sonuç kendiliğinden doğrudur. Açgözlü yaklaşımda sonucun doğru olması, yapılan seçimin güvenli olmasına bağlıdır ve bu ayrıca kanıtlanmalıdır.

7.2Para üstü problemi

Açgözlü yaklaşımın en tanıdık örneği para üstü vermektir. Bir kasiyer 68 kuruşu en az sayıda madeni parayla ödemek isterse önce 50'lik, sonra 10'luk, sonra 5'lik ve en sonda üç tane 1'lik verir. Her adımda kalan tutara sığan en büyük parayı seçer. Bu yöntem gündelik para sistemlerinde kusursuz çalışır. Ancak para birimleri farklı seçilirse aynı yöntem en iyi sonucu kaçırabilir. Bu kesim hem yöntemin işlediği hem de yanıldığı durumları inceler.

7.2.1Problem ve açgözlü ölçüt

En küçük paranın 1 olması, her tutarın ödenebilmesini garanti eder. Bu koşul yoksa bazı tutarlar hiç ödenemez; örneğin yalnız 3 ve 5'lik paralarla 7 ödenemez. Açgözlü ölçüt şöyledir: kalan tutardan büyük olmayan en büyük para seçilir; tutar sıfır olana kadar bu adım tekrarlanır. Sunumdaki Java kodu bu kuralı iki iç içe döngüyle uygular:

// para[] büyükten küçüğe sıralı
static int paraUstu(int[] para, int tutar) {
  int adet = 0;
  for (int p : para) {
    while (tutar >= p) {
      tutar -= p;
      adet++;
    }
  }
  return adet;
}

Kod, para dizisinin büyükten küçüğe sıralı geldiğini varsayar. Dış döngü her para türünü bu sırayla bir kez ele alır. İç while döngüsü, o para kalan tutara sığdığı sürece onu kullanır: tutardan düşer ve sayacı artırır. Para artık sığmadığında iç döngü biter ve bir sonraki, daha küçük para türüne geçilir. En küçük para 1 olduğu için son türden sonra tutar her zaman sıfırdır.

Maliyet hesabı iki kısımdan oluşur. Dış döngü k kez döner ve her dönüşte en az bir while koşulu sınanır; bu O(k) eder. İç döngünün gövdesi her çalıştığında bir para seçilir; gövde toplam adet kez çalışır. Toplam süre O(k + adet)'tir. Para dizisi sıralı gelmezse buna O(k log k)'lik bir sıralama eklenir. İç döngü bölme ve kalan işlemiyle de yazılabilir: adet += tutar / p; tutar %= p;. Bu sürüm para sayısından bağımsız olarak O(k) sürer ve büyük tutarlarda daha hızlıdır. Sonuç aynıdır.

7.2.2Kanonik bir sistemde adım adım

Sunumdaki ilk örnekte paralar {50, 25, 10, 5, 1}, tutar 68'dir. Tablo 7.2 her adımı verir.

Sonuç 68 = 50 + 10 + 5 + 1 + 1 + 1, yani 6 paradır. Bu, 68 için gerçekten en az para sayısıdır. Daha azının mümkün olmadığı şöyle görülebilir. 1 dışındaki bütün paralar 5'in katıdır ve 68'in 5'e bölümünden kalan 3'tür. Bu yüzden her çözümde en az üç tane 1'lik para bulunur. En fazla 5 paralık bir çözüm olsaydı, 1'likler dışındaki en fazla iki para 65'i ödemek zorunda kalırdı. Oysa iki parayla 65 ödenemez: 50 + 10 = 60, 50 + 25 = 75 ve 25 + 25 = 50'dir; 65'e eşit bir iki para toplamı yoktur. Tek parayla ya da hiç parasız da ödenemez.

Açgözlü sonucun her tutar için en iyi olduğu para sistemlerine kanonik para sistemi denir. {50, 25, 10, 5, 1} ve {25, 10, 5, 1} kanonik sistemlerdir. Türk lirasının madeni paralarına karşılık gelen {100, 50, 25, 10, 5, 1} kuruş da kanoniktir. Euro sisteminin {200, 100, 50, 20, 10, 5, 2, 1} sent dizisi de öyledir. Notun doğrulama betiği bu sistemlerin her birinde 1 ile 499 arasındaki bütün tutarları dinamik programlamayla karşılaştırmış ve hiçbir farka rastlamamıştır. Gündelik para sistemlerinin kanonik olması tesadüf değildir; sistemler zaten bu özellik gözetilerek tasarlanır.

7.2.3Kod izleme: {4, 3, 1} ve 10

Şimdi para birimleri {4, 3, 1} olsun ve paraUstu 10 tutarıyla çağrılsın. Paralar büyükten küçüğe sıralı verilmiştir. Bu sistem kanonik değildir; açgözlü sonucun en iyi olup olmayacağı baştan bilinmez. Tablo 7.3 kodun her adımında değişkenlerin değerini gösterir.

Kod 4 döndürür: 10 = 4 + 4 + 1 + 1. Oysa 10 = 4 + 3 + 3 yalnız 3 para kullanır. Hata ikinci adımda yapılmıştır. İlk 4'lük seçildikten sonra kalan 6 tutarı için açgözlü kural yine 4'ü seçer, çünkü 4 hâlâ sığar. Oysa 6, iki tane 3'lükle ödenebilirdi. İkinci 4'lük seçildiği anda kalan 2 için 3'lük para işe yaramaz hâle gelir ve 2, iki tane 1'likle ödenir. İzlemenin dördüncü satırı bu sonucu gösterir: 3'lük para hiç kullanılmaz.

7.2.4Açgözlü seçim neden yanılır?

Aynı sistemde 6 tutarı daha da kısa bir karşı örnektir. Açgözlü algoritma önce 4'ü seçer, kalan 2'yi iki tane 1'likle öder: 6 = 4 + 1 + 1, 3 para. En iyi çözüm ise 6 = 3 + 3, 2 paradır. Şekil 7.4 bu iki sonucu gösterir.

Burada açgözlü seçim özelliği bozulmuştur. İlk açgözlü seçim 4'tür, ama 6'nın tek en iyi çözümü olan 3 + 3, 4'ü içermez. 4'ü içeren her çözüm en az 3 para kullanır. Değiştirme argümanı da bu sistemde işlemez: en iyi çözümdeki 3'lüklerden biri 4'lükle değiştirilirse toplam 7 olur ve çözüm uygunluğunu kaybeder.

Bir para sisteminin kanonik olup olmadığını anlamak için tek bir tutarın denenmesi yetmez. {4, 3, 1} sisteminde 1'den 10'a kadar olan tutarlardan yalnız 6 ve 10'da açgözlü yanılır; 1–5, 7, 8 ve 9 tutarlarında açgözlü sonuç en iyidir. 20'ye kadar hatalı tutarlar 6, 10, 14 ve 18'dir. Sunumdaki ikinci karşı örnek sistemi {10, 7, 1}'dir. Bu sistemde ilk hatalı tutar 14'tür: açgözlü 10 + 1 + 1 + 1 + 1 ile 5 para kullanır, en iyi çözüm 7 + 7 ile 2 paradır. 15 için açgözlü 6 para (10 + beş tane 1) verir, en iyi çözüm 7 + 7 + 1 ile 3 paradır.

Bir sistemin kanonik olup olmadığı genel olarak kolayca görülmez. Komşu paraların birbirinin katı olması yeterli bir koşuldur: {100, 50, 10, 5, 1} gibi bir sistemde her büyük para, kendinden küçük paraların yerine geçebilir. Ancak bu koşul gerekli değildir; {25, 10, 5, 1} sisteminde 25, 10'un katı değildir, ama sistem yine kanoniktir. Kozen ve Zaks'ın gösterdiği gibi, kanonik olmayan bir sistemin en küçük karşı örneği en büyük iki paranın toplamından küçüktür. Bu yüzden bir sistemi denetlemek için bu sınıra kadar olan tutarları dinamik programlamayla karşılaştırmak yeterlidir. {4, 3, 1} için sınır 7'dir ve 6 bu aralıktadır. {10, 7, 1} için sınır 17'dir ve 14 bu aralıktadır.

7.2.5En iyi sonuç: dinamik programlama

Para sistemi kanonik değilse en iyi sonucu dinamik programlama verir. Fikir, her tutar için en az para sayısını küçükten büyüğe hesaplamaktır. enAz[t], t tutarını ödemek için gereken en az para sayısı olsun. enAz[0] = 0'dır. t > 0 için son kullanılan para p ise geriye t − p tutarı kalır ve onun da en iyi biçimde ödenmesi gerekir. Bütün paralar denenir ve en iyisi seçilir:

enAz[t] = 1 + min { enAz[t − p] : p ≤ t }

Bu bağıntı optimal alt yapının bir örneğidir: t'nin en iyi çözümünden son para çıkarılırsa, kalan paralar t − p'nin en iyi çözümünü oluşturur. Açgözlü algoritmadan farkı, son paranın hangisi olacağının bilinmemesi ve bütün seçeneklerin denenmesidir. Tablo 7.4 {4, 3, 1} sistemi için 0'dan 10'a kadar tabloyu açgözlü sonuçla yan yana verir.

Tablonun iki hücresi ayrıntılı hesaplanırsa bağıntının işleyişi görülür. t = 6 için üç seçenek vardır: son para 1 ise 1 + enAz[5] = 3, son para 3 ise 1 + enAz[3] = 2, son para 4 ise 1 + enAz[2] = 3. En küçüğü 2'dir ve 3'lük parayla elde edilir. t = 10 için seçenekler 1 + enAz[9] = 4, 1 + enAz[7] = 3 ve 1 + enAz[6] = 3'tür; en küçüğü 3'tür. Açgözlü algoritma ise yalnız 4'lük seçeneği izler ve 10 için 4 para bulur.

Dinamik programlamanın bedeli süredir. Tablo T + 1 hücrelidir ve her hücre k para türünü dener; toplam O(k · T) zaman ve O(T) bellek gerekir. Açgözlü algoritma ise O(k + adet) sürede biter ve ek bellek kullanmaz. Sunumdaki etkileşimli slayt iki yöntemi yan yana çalıştırır: istenen para kümesi ve tutar girilir, açgözlü sonuç ile dinamik programlamanın en iyi sonucu karşılaştırılır. Hazır düğmelerden biri {1, 7, 10} ve 14 örneğini, öteki kanonik TL kuruş sistemini ve 68 tutarını yükler.

7.3Etkinlik seçimi

Bir konferans salonunu kullanmak isteyen birçok etkinlik vardır. Her etkinliğin bir başlangıç ve bir bitiş saati bellidir. Salonda aynı anda yalnız bir etkinlik yapılabilir. Yönetim, birbiriyle çakışmayan olabildiğince çok etkinliği kabul etmek ister. Etkinliklerin süresi ya da önemi değil, yalnız sayısı önemlidir. Bu problem, açgözlü bir algoritmanın en iyi sonucu verdiği ve bunun kısa bir kanıtla gösterilebildiği klasik bir örnektir.

7.3.1Problemin tanımı

Aralıkların yarı açık olması, bir etkinliğin bittiği anda bir başkasının başlayabileceği anlamına gelir. Örneğin [3, 4) ile [4, 6) çakışmaz. Bitiş anı etkinliğe dahil değildir. Sunumdaki örnekte on etkinlik vardır (Tablo 7.5).

Kaba kuvvetle bütün alt kümeleri denemek 2ⁿ küme demektir; on etkinlik için 1024 küme, kırk etkinlik için bir trilyonu aşan küme. Açgözlü algoritma ise etkinlikleri bir kez sıralar ve tek geçişte seçer.

7.3.2Hangi ölçüt?

Açgözlü bir algoritma kurmak için önce “her adımda hangi etkinlik seçilsin?” sorusuna cevap vermek gerekir. Akla gelen dört ölçüt vardır:

1. En erken başlayan. Salon olabildiğince erken dolsun.
2. En kısa süren. Kısa etkinlikler salonu az meşgul eder.
3. En az çakışan. Başka etkinlikleri en az engelleyen seçilsin.
4. En erken biten. Salon olabildiğince erken boşalsın.

Her biri makul görünür, ama yalnız sonuncusu her girdide en iyi sonucu verir. Bir ölçütün yanlış olduğunu göstermek için tek bir karşı örnek yeter. Şekil 7.5 ilk iki ölçüt için sunumdaki karşı örnekleri gösterir.

Üstteki örnekte [0, 10) etkinliği en erken başlar. Açgözlü algoritma onu seçer ve onunla çakışan [1, 3), [4, 6) ve [7, 9) etkinliklerini atar; sonuç 1 etkinliktir. Oysa bu üç kısa etkinlik birbiriyle çakışmaz ve birlikte seçilebilir. Alttaki örnekte [4, 7) en kısa etkinliktir (3 birim). Açgözlü onu seçer, ama bu etkinlik hem [0, 5) ile hem [6, 11) ile çakışır. Sonuç yine 1 etkinliktir; en iyi çözüm ise iki uzun etkinliği birlikte seçer.

En az çakışan ölçütü daha ince bir karşı örnek gerektirir, çünkü küçük örneklerde çoğu zaman doğru sonuç verir. Tablo 7.6 on bir etkinlikli bir karşı örnek verir. En iyi çözüm A, B, C ve D'den oluşur ve 4 etkinlik içerir. Ancak çakışma sayısı en küçük olan etkinlik M'dir: yalnız B ve C ile çakışır. Açgözlü önce M'yi seçer ve böylece B'yi de C'yi de kaybeder. Kalan etkinliklerden en fazla iki tane daha seçilebilir; sonuç 3 etkinliktir. Doğrulama betiği eşitliklerin her türlü bozulmasını denemiş ve bu ölçütün bu girdide 3'ü geçemediğini göstermiştir.

En erken biten ölçütünün arkasındaki düşünce şudur: salonu en erken boşaltan etkinlik, geri kalan etkinliklere en çok zaman bırakır. Geri kalan zaman ne kadar uzunsa, oraya o kadar çok etkinlik sığabilir. Ölçüt etkinliğin süresine ya da başlangıcına değil, yalnız bitişine bakar.

7.3.3Kod ve izleme

Sunumdaki sec metodu etkinlikleri bitiş zamanına göre sıralar, ilkini seçer ve sonra her etkinliği son seçilenin bitişiyle karşılaştırır:

static void sec(Etkinlik[] e) {
  Arrays.sort(e, (x, y) -> x.bitis - y.bitis);
  int i = 0;                 // son seçilen
  System.out.print(e[i].id + " ");
  for (int j = 1; j < e.length; j++) {
    if (e[j].bas >= e[i].bitis) {
      System.out.print(e[j].id + " ");
      i = j;
    }
  }
}

Kodda Etkinlik sınıfının id, bas ve bitis alanları vardır. Arrays.sort çağrısındaki (x, y) -> x.bitis - y.bitis ifadesi bir karşılaştırıcıdır: x'in bitişi daha küçükse negatif bir değer döner ve x öne geçer. Java'nın nesne dizileri için kullandığı sıralama kararlıdır; bitişi eşit iki etkinlik dizideki ilk sıralarını korur. i değişkeni son seçilen etkinliğin dizideki yerini tutar. Sıralı dizinin ilk öğesi en erken biten etkinliktir ve koşulsuz seçilir. Döngü j = 1'den başlar. e[j].bas >= e[i].bitis koşulu, j. etkinliğin son seçilenden sonra başladığını, yani onunla çakışmadığını sınar. Koşul doğruysa etkinlik yazdırılır ve i güncellenir.

Burada önemli bir gözlem vardır: yeni etkinlik yalnız son seçilenle karşılaştırılır, bütün seçilenlerle değil. Bu yeterlidir, çünkü etkinlikler bitişe göre sıralıdır. Son seçilen, seçilenlerin içinde en geç biten etkinliktir. Yeni etkinlik ondan sonra başlıyorsa, daha önce biten bütün seçilenlerden de sonra başlar.

Sıralama sonrası dizi şöyledir: #7 [0, 2), #1 [1, 3), #8 [3, 4), #2 [2, 5), #3 [4, 6), #5 [5, 7), #4 [6, 8), #6 [8, 9), #9 [7, 9), #10 [10, 12). #6 ile #9'un bitişi aynıdır (9); kararlı sıralama #6'yı önde tutar. Tablo 7.7 döngünün her adımını verir.

Program 7 8 3 4 6 10 yazar; 6 etkinlik seçilmiştir. Bu sayı gerçekten en büyüktür: doğrulama betiği 1024 alt kümenin hepsini denemiş ve 7 etkinlikli çakışmasız bir küme bulamamıştır. 6 etkinlikli iki küme vardır: açgözlünün bulduğu {7, 8, 3, 4, 6, 10} ve {1, 8, 3, 4, 6, 10}. İkincisi, #7 yerine #1 ile başlar. Bu durum açgözlü seçim özelliğinin “en az bir” en iyi çözümden söz ettiğini somut olarak gösterir: en erken biten #7'yi içermeyen bir en iyi çözüm de vardır, ama #7'yi içeren bir tane de vardır.

İzlemedeki üç adım, yarı açık aralıkların önemini gösterir. #3 tam 4'te başlar ve #8 tam 4'te biter; #4 tam 6'da başlar ve #3 tam 6'da biter; #6 tam 8'de başlar ve #4 tam 8'de biter. Koşul >= yerine > yazılsaydı, son seçilenin bittiği anda başlayan etkinlikler atlanırdı. #8'den sonra #3 yerine #5 [5, 7) seçilirdi; ardından #6 [8, 9) ve #10 [10, 12) gelirdi ve sonuç 5 etkinlikle kalırdı.

Maliyet açıktır. Sıralama O(n log n), tek geçiş O(n) sürer; toplam O(n log n). Etkinlikler bitişe göre sıralı gelirse sıralama gereksizdir ve algoritma O(n) sürede biter. Ek bellek olarak yalnız bir i değişkeni tutulur.

7.3.4En erken biten neden doğrudur?

Kanıtta en erken biten etkinliğin özel bir rolü vardır: değiştirilen b₁'den daha geç bitmez. Bu yüzden onun yerine geçtiğinde sonraki etkinliklere engel olmaz. En erken başlayan etkinlik için aynı argüman kurulamaz: en erken başlayan etkinlik çok geç bitebilir ve b₂ ile çakışabilir. Şekil 7.5'teki [0, 10) tam olarak bu durumdadır.

Aynı problem ters yönden de çözülebilir. Etkinlikler başlangıca göre büyükten küçüğe sıralanır ve her adımda en geç başlayan etkinlik seçilir. Bu, zaman ekseni ters çevrildiğinde en erken biten ölçütünün aynısıdır ve aynı kanıtla en iyi sonucu verir. Problemin bir genellemesi olan ağırlıklı etkinlik seçiminde ise her etkinliğin bir değeri vardır ve toplam değer en büyük olmalıdır. Bu sürümde hiçbir basit açgözlü ölçüt doğru değildir; problem dinamik programlamayla çözülür.

7.4Son tarihli iş sıralama

Bir atölyede tek bir makine var ve birkaç sipariş sırada bekliyor. Her sipariş makinede bir gün sürer. Her siparişin bir teslim tarihi ve bir kârı vardır; sipariş teslim tarihine kadar bitirilirse kâr kazanılır, bitirilmezse sipariş kaybedilir. Atölye hangi siparişleri hangi günlere koyarsa toplam kârı en büyük olur? Bu problem etkinlik seçimine benzer, ama burada bütün işlerin süresi aynıdır ve önemli olan sayı değil, kârdır.

7.4.1Problemin tanımı

Bir işin d_i son tarihi, işin 1'den d_i'ye kadar olan dilimlerden birine konabileceği anlamına gelir. Son tarihi 1 olan bir iş yalnız birinci dilime konabilir. Son tarihi 3 olan bir iş birinci, ikinci ya da üçüncü dilime konabilir. Sunumdaki örnekte altı iş vardır (Tablo 7.8).

İlk bakışta üç işin (2, 3 ve 4) son tarihi 1'dir ve bunlardan yalnız biri yapılabilir. Hangisinin yapılacağı ve öteki işlerin nereye konacağı birlikte düşünülmelidir.

7.4.2Açgözlü ölçüt ve en geç boş dilim

Açgözlü algoritma iki karar verir. Birincisi işlerin hangi sırayla ele alınacağıdır: işler kâra göre azalan sırayla incelenir, yani en kârlı iş önce. İkincisi her işin hangi dilime konacağıdır: iş, son tarihinden önceki en geç boş dilime konur. Son tarihine kadar boş dilim kalmamışsa iş atlanır ve bir daha ele alınmaz.

İkinci kararın gerekçesi şudur. Bir işi gereğinden erken bir dilime koymak, son tarihi daha yakın olan bir işin yerini kapatabilir. Örneğin son tarihi 3 olan bir iş birinci dilime konursa, sonradan gelecek ve son tarihi 1 olan bir işin gidebileceği tek yer dolmuş olur. Aynı iş üçüncü dilime konsaydı birinci dilim boş kalırdı. En geç boş dilim, erken dilimleri son tarihi daha yakın işlere bırakır ve esnekliği korur.

7.4.3Kod ve izleme

Sunumdaki isSirala metodu bu iki kuralı uygular ve toplam kârı döndürür:

static int isSirala(Is[] is, int n) {
  Arrays.sort(is, (a, b) -> b.kar - a.kar);
  int[] slot = new int[n];
  Arrays.fill(slot, -1);
  int toplam = 0;
  for (int i = 0; i < n; i++) {
    int j = Math.min(n, is[i].sonTarih) - 1;
    for (; j >= 0; j--) {
      if (slot[j] == -1) {
        slot[j] = is[i].id;
        toplam += is[i].kar;
        break;
      }
    }
  }
  return toplam;
}

Is sınıfının id, sonTarih ve kar alanları vardır. Arrays.sort çağrısındaki karşılaştırıcı b.kar - a.kar, kârı büyük olan işi öne alır. Kararlı sıralama sayesinde eşit kârlı işler ilk sıralarını korur. slot dizisi n dilimi tutar: slot[j], j + 1. dilime konan işin numarasıdır, boşsa −1'dir. Java'da diziler 0'dan başladığı için birinci dilim slot[0]'dadır. n iş en fazla n dilim kullanabilir; bu yüzden n'den büyük son tarihler n'ye indirilir. Math.min(n, is[i].sonTarih) - 1 ifadesi bunu yapar ve işin konabileceği en geç dilimin indisini verir. İç döngü bu dilimden geriye doğru ilk boş dilimi arar. Boş dilim bulunursa iş yerleştirilir, kâr toplama eklenir ve break ile arama biter. Döngü j = −1'e kadar inerse uygun dilim yoktur ve iş sessizce atlanır.

Kâra göre sıralanmış dizi İş 5 (50), İş 3 (40), İş 4 (30), İş 6 (30), İş 1 (20), İş 2 (10) şeklindedir. Tablo 7.9 her işin yerleştirilmesini adım adım verir. Tabloda dilimler 1'den numaralanır.

Metot 140 döndürür. Makine birinci gün İş 3'ü, ikinci gün İş 6'yı, üçüncü gün İş 5'i, dördüncü gün İş 1'i yapar. Beşinci ve altıncı dilimler boş kalır; hiçbir işin son tarihi 4'ü geçmediği için bu dilimlerin kullanılması zaten mümkün değildir. 140'ın en büyük toplam kâr olduğu, doğrulama betiğinde altı işin bütün alt kümeleri denenerek gösterilmiştir.

İzlemenin ilginç adımı İş 4'tür. Kârı 30'dur ve İş 6 ile eşittir, ama son tarihi 1'dir ve birinci dilimi daha kârlı İş 3 almıştır. İş 4 için başka bir dilim yoktur. İş 6 ise son tarihi 2 olduğu için ikinci dilime sığar. Eşit kârlı iki işten birinin yapılıp ötekinin yapılamaması, son tarihlerin farklı olmasından kaynaklanır.

7.4.4Yanlış ölçütler

İki karardan her biri yanlış seçilebilir. Önce işlerin sırası ele alınsın. İşleri son tarihe göre sıralamak doğal görünür: önce acil işler yapılsın. Ancak bu ölçüt kârı dikkate almaz. Son tarihi 1 olan iki iş düşünülsün: birinin kârı 10, ötekinin 40'tır. Yalnız biri yapılabilir. Son tarihe göre sıralamada (kararlı sıralamayla) ilk gelen iş seçilir; ilk gelen kârı 10 olan işse sonuç 10'dur. Kâra göre sıralama ise 40'lık işi seçer. Sunumdaki altı işte son tarihe göre sıralama ve en geç boş dilim kuralı 110 kâr verir; kâr sırası 140 verir.

Sonra dilim seçimi ele alınsın. İş, son tarihinden önceki en erken boş dilime konsun. Sunumdaki altı işte İş 5 (son tarih 3) birinci dilime gider. Ardından gelen İş 3'ün tek seçeneği birinci dilimdir, ama o dolmuştur; 40 kârlı iş kaybedilir. Algoritma sonunda İş 5, İş 6 ve İş 1'i yapar ve yalnız 100 kâr elde eder. En geç boş dilim kuralıyla aynı işler 140 kâr getirir. İki işli bir örnek daha kısadır: X'in son tarihi 2, kârı 50; Y'nin son tarihi 1, kârı 40 olsun. En erken boş dilim kuralı X'i birinci dilime koyar ve Y'yi kaybeder: 50. En geç boş dilim kuralı X'i ikinci dilime koyar, Y birinci dilime sığar: 90.

7.4.5Doğruluk ve maliyet

Algoritmanın doğruluğu iki parçada gösterilir. Birinci parça, en geç boş dilim kuralının bir işi ancak gerçekten sığmıyorsa reddettiğidir.

İkinci parça, kâra göre azalan sıranın doğru olduğudur ve bir değiştirme argümanıyla gösterilir. En kârlı iş a olsun ve tek başına son tarihine yetişebilsin. O, a'yı içermeyen bir en iyi çözüm olsun. O'nun 1–d(a) dilimlerinden biri boşsa a oraya eklenir ve kâr artar; bu, O'nun en iyi olmasıyla çelişir. Hepsi doluysa bu dilimlerden birindeki b işi çıkarılıp yerine a konur. a kendi son tarihinden önceki bir dilime konduğu için çözüm uygundur. k(a) ≥ k(b) olduğu için kâr azalmaz. Demek ki a'yı içeren bir en iyi çözüm vardır. Sunum bu sonucu daha genel bir dille de anar: birlikte son tarihlerine yetiştirilebilen iş kümeleri bir matroid oluşturur ve matroidlerde ağırlığa göre azalan açgözlü seçim her zaman en iyidir. Kruskal algoritmasının doğruluğu da aynı genel sonucun bir örneğidir.

Maliyet şöyle hesaplanır. Sıralama O(n log n) sürer. Her iş için dilim araması en fazla min(n, d_i) dilime bakar; en büyük son tarih d_max ise arama toplam O(n · d_max) sürer. d_max, n'ye kadar çıkabildiği için en kötü durum O(n²)'dir. Örneğin bütün işlerin son tarihi n ise i. iş i dilime bakar ve toplam 1 + 2 + … + n = n(n + 1)/2 bakış yapılır. Bu maliyet ayrık kümeler (union-find) yapısıyla düşürülebilir. Her dolu dilim, solundaki ilk boş dilimi gösteren bir kümeye bağlanır. Bir işin en geç boş dilimi tek bir bul çağrısıyla bulunur; dilim dolunca soldaki kümeyle birlestir yapılır. Yol kısaltma ve rütbeye göre birleştirme ile her işlem neredeyse sabit sürer ve dilim araması toplamda neredeyse O(n)'e iner. Toplam maliyeti bu durumda sıralama belirler.

7.5Kesirli sırt çantası

Bir yolcunun sırt çantası en fazla 50 kilogram taşıyabilir. Önünde birkaç çuval baharat vardır; her çuvalın bir ağırlığı ve bir değeri bellidir. Baharat bölünebilir: bir çuvalın yarısı alınırsa değerinin yarısı kazanılır. Yolcu çantaya ne koyarsa taşıdığı değer en büyük olur? Bu soru kesirli sırt çantası problemidir. Nesneler bölünemediğinde, yani her nesne ya bütünüyle alındığında ya hiç alınmadığında problemin adı 0/1 sırt çantasıdır. İki problem birbirine çok benzer, ama açgözlü yaklaşım yalnız birincisinde en iyi sonucu verir.

7.5.1Problem ve oran ölçütü

Bir nesnenin ne kadar “verimli” olduğunu ağırlık başına getirdiği kâr gösterir. Bu değere nesnenin oranı denir: k_i / w_i. Açgözlü ölçüt, oranı en büyük nesneden başlayarak sığdığı kadarını almaktır. Bir nesnenin tamamı sığıyorsa tamamı alınır. Sığmıyorsa kalan kapasite kadar bir parçası alınır ve çanta dolar. Sunumdaki örnekte kapasite W = 50'dir ve üç nesne vardır (Tablo 7.10).

Oranlar 6, 5 ve 4'tür; nesneler zaten oran sırasındadır. Nesne 1'in tamamı alınır (10 kg, 60 kâr). Nesne 2'nin tamamı alınır (20 kg, 100 kâr). Geriye 20 kg kapasite kalır, ama nesne 3 30 kg'dır. Nesne 3'ün 20/30'u alınır ve 120 · 20/30 = 80 kâr kazanılır. Toplam 60 + 100 + 80 = 240'tır.

Dikkat edilirse oran ölçütü kârı en büyük nesneyi önce almaz. Nesne 3'ün kârı en büyüktür (120), ama ağırlığı da en büyüktür ve kilogram başına en az kârı getirir. Kâra göre azalan sırayla almak nesne 3'ün tamamını (30 kg, 120) ve nesne 2'nin tamamını (20 kg, 100) seçer ve 220'de kalır. Ağırlığa göre artan sırayla almak bu örnekte oran sırasıyla aynı sonucu verir, ama bu bir rastlantıdır: ağır ve çok kârlı bir nesne ile hafif ama değersiz bir nesne bulunan bir girdide yanılır.

7.5.2Kod ve izleme

Sunumdaki kesirli metodu nesneleri orana göre azalan sıralar ve çantayı doldurur:

static double kesirli(Nesne[] s, int W) {
  Arrays.sort(s, (a, b) -> Double.compare(b.oran(), a.oran()));
  double kar = 0;
  int kalan = W;
  for (Nesne x : s) {
    if (x.agirlik <= kalan) {        // tamamı sığar
      kalan -= x.agirlik;
      kar += x.kar;
    } else {                         // kesirli parça
      kar += x.kar * (double) kalan / x.agirlik;
      break;
    }
  }
  return kar;
}

Nesne sınıfının kar ve agirlik alanları ile oran() metodu vardır; oran(), (double) kar / agirlik değerini döndürür. Karşılaştırıcı Double.compare(b.oran(), a.oran()) oranı büyük olanı öne alır. Burada çıkarma yerine Double.compare kullanılır, çünkü oranlar ondalıklıdır ve iki oranın farkı bir tam sayıya çevrilirse 0,5 gibi farklar kaybolur. kalan, çantada kalan kapasitedir. Döngü her nesne için önce tamamının sığıp sığmadığına bakar. Sığıyorsa kapasiteden ağırlığı düşer ve kârı ekler. Sığmıyorsa else dalında nesnenin kalan / agirlik kadarlık bir parçasını alır. Çanta artık tam dolmuştur ve break ile döngüden çıkılır. Kesirli parçanın kârı hesaplanırken (double) dönüşümü önemlidir: kalan / x.agirlik tam sayı bölmesi olarak yazılsaydı 20/30 sıfıra yuvarlanırdı.

Son satırda kalan 20 olarak kalır, çünkü else dalı kapasiteyi güncellemez; hemen ardından döngü kırıldığı için bu değer bir daha kullanılmaz. Metot 240.0 döndürür.

Maliyetin baskın kısmı sıralamadır: O(n log n). Tarama en fazla n nesneye bakar ve O(n) sürer. Sıralama yerine her adımda en büyük oranlı nesne bir öbekten alınabilir; çanta erken dolarsa öbekten yalnız birkaç nesne çıkarılır ve toplam süre O(n + m log n)'ye iner (m, alınan nesne sayısıdır). Doğrusal zamanda çalışan, ortanca bulmaya dayanan bir yöntem de vardır.

7.5.3Oran ölçütü neden en iyidir?

Kanıtın can alıcı adımı, ağırlığın küçük parçalar hâlinde değiştirilebilmesidir. δ kilogram bir nesneden çıkarılıp öbürüne eklenebilir, çünkü nesneler bölünebilir. En yüksek oranlı nesnenin her kilogramı, aynı ağırlıktaki başka her seçenekten en az onun kadar kâr getirir. Bu yüzden onu sonuna kadar almamak için bir neden yoktur.

7.5.40/1 sırt çantasında oran ölçütü

Nesneler bölünemezse kanıttaki değiştirme adımı çöker. Aynı üç nesne ve 50 kg'lık çanta ele alınsın, ama bu kez her nesne ya bütünüyle alınsın ya hiç alınmasın. Oran ölçütü nesne 1'i ve nesne 2'yi alır (30 kg, 160 kâr). Nesne 3 kalan 20 kg'a sığmaz ve atlanır. Sonuç 160'tır. Oysa nesne 2 ile nesne 3 birlikte tam 50 kg tutar ve 220 kâr getirir. Bütün seçimler karşılaştırılınca en iyisinin bu olduğu görülür. Tek nesneler 60, 100 ve 120 getirir. İkili seçimler 1 + 2 = 160, 1 + 3 = 180 ve 2 + 3 = 220 getirir. Üç nesne birden 60 kg tutar ve sığmaz.

0/1 durumunda oran ölçütü 20 kg'lık boşluğu dolduramaz. Kesirli durumda bu boşluk nesne 3'ün bir parçasıyla doldurulur. 0/1 durumunda ise parça alınamaz ve boşluk değersiz kalır. Değiştirme argümanı da işlemez: en iyi çözümdeki nesne 3 çıkarılıp yerine nesne 1 konursa ağırlık 30 kg'a düşer ama kâr 220'den 160'a iner. Ağırlıklar eşit olmadığı için değiştirme “aynı ağırlık, daha çok kâr” biçiminde yapılamaz. 0/1 sırt çantası dinamik programlamayla O(n · W) sürede çözülür.

Kesirli çözümün değeri 0/1 çözümünün değeri için bir üst sınırdır: 0/1 çözümü kesirli problemin de uygun bir çözümüdür, bu yüzden kesirli en iyinin değerini geçemez. Örnekte 220 ≤ 240'tır. Bu sınır, 0/1 sırt çantasını dal ve sınır yöntemiyle çözen algoritmalarda budama için kullanılır.

7.6Minimum kapsayan ağaçta açgözlü seçim

Minimum kapsayan ağaç, açgözlü yaklaşımın en başarılı uygulamalarından biridir. Bağlı, ağırlıklı ve yönsüz bir çizgenin kapsayan ağacı, çizgenin bütün düğümlerini içeren, bağlı ve döngüsüz bir alt çizgesidir; V düğümlü bir çizgede tam olarak V − 1 kenarı vardır. Kenar ağırlıklarının toplamı en küçük olan kapsayan ağaca minimum kapsayan ağaç (minimum spanning tree, MST) denir. Bir şehirler ağını en az kablo ile bağlamak bu problemin tipik bir uygulamasıdır. Kruskal, Prim ve Borůvka algoritmaları MST'yi bulur ve üçü de açgözlüdür. Bu kesim algoritmaları baştan anlatmaz; üçünün açgözlü seçiminin neden güvenli olduğunu tek bir özellik üzerinden açıklar.

7.6.1Kesim özelliği

Bir çizgenin düğümleri iki boş olmayan kümeye ayrılsın: S ve V − S. Bu ayrıma bir kesim (cut) denir. Bir ucu S'de, öteki ucu V − S'de olan kenarlar kesimi geçer. Her kapsayan ağaç kesimi geçen en az bir kenar içermek zorundadır; yoksa S ile V − S arasında bağlantı kurulamaz.

Şekil 7.12'deki çizgede kesimi dört kenar geçer: p–s (9), r–s (4), r–t (8) ve q–t (11). En hafifleri r–s'dir ve tek en hafif kenar olduğu için her MST'de bulunur. Çizgenin MST'si gerçekten t–u (2), p–r (3), p–q (4), r–s (4) ve s–u (6) kenarlarından oluşur; toplam ağırlık 19'dur. Kesimi geçen kenarlardan yalnız r–s ağaca girer. Bu tesadüf değildir: MST'nin S ile V − S'yi tam olarak bir kenarla bağlaması yeterlidir ve bu kenar en ucuzu olmalıdır.

Kesim özelliğinin açgözlü algoritmalar için anlamı şudur. Algoritma o ana kadar seçtiği kenarlarla bazı bileşenler kurmuştur. Bu bileşenlerden birini öbürlerinden ayıran bir kesim seçilir. Seçilmiş kenarların hiçbiri bu kesimi geçmez. Kesimi geçen en hafif kenar eklenirse, seçilmiş kenarlarla birlikte yine bir MST'nin parçası olarak kalınır. Kanıttaki değiştirme bu durumda da çalışır, çünkü çıkarılan e' kesimi geçer ve bu yüzden seçilmiş kenarlardan biri değildir. Algoritma bu yüzden hiçbir seçimini geri almak zorunda kalmaz.

Ağırlıkların hepsi farklıysa her kesimin en hafif kenarı tektir ve MST de tektir. Şekildeki çizgede p–q ve r–s'nin ikisinin de ağırlığı 4'tür, yani ağırlıklar tümüyle farklı değildir; yine de bu çizgenin MST'si tektir. Tekliğin koşulu yeterlidir, gerekli değildir. Eşit ağırlıklar birden çok MST'ye yol açabilir; ama bütün MST'lerin toplam ağırlığı aynıdır.

7.6.2Kruskal, Prim ve Borůvka: üç kesim

Üç MST algoritması aynı özelliği farklı kesimlerle kullanır. Fark, her adımda hangi kesimin seçildiğidir. Tablo 7.13 üç algoritmayı yan yana verir.

Kruskal kenarları artan ağırlık sırasıyla inceler. Sıradaki kenar iki farklı bileşeni bağlıyorsa eklenir, aynı bileşenin iki düğümünü bağlıyorsa döngü kuracağı için atlanır. Eklenen kenarın kullandığı kesim, uçlarından birinin bileşeni ile geri kalan düğümler arasındaki kesimdir. Bu kesimi geçen daha hafif bir kenar olsaydı daha önce incelenir ve eklenirdi; demek ki eklenen kenar kesimin en hafifidir. Bileşen denetimi ayrık kümeler yapısıyla yapılır. Süreyi sıralama belirler: O(E log E). E ≤ V² olduğu için log E ≤ 2 log V'dir ve bu süre O(E log V) diye de yazılır.

Prim tek bir ağacı bir düğümden başlayarak büyütür. Her adımda ağaçtaki bir düğümü ağaç dışındaki bir düğüme bağlayan en hafif kenar eklenir. Kullanılan kesim, ağacın düğümleri ile geri kalan düğümler arasındaki kesimdir. Ağaç dışındaki her düğümün ağaca en ucuz bağlantısı bir öncelikli kuyrukta tutulur. İkili öbekle süre O((V + E) log V)'dir; bağlı çizgede bu O(E log V)'ye eşittir. Yoğun çizgelerde dizi taramalı bir sürüm O(V²) ile daha hızlı olabilir.

Borůvka turlar hâlinde çalışır. Her turda her bileşen kendinden çıkan en hafif kenarı bulur ve bu kenarların hepsi birlikte eklenir. Her bileşen kendi kesimini, yani “bu bileşen ile geri kalan her şey” kesimini kullanır. Her tur bileşen sayısını en az yarıya indirdiği için en fazla ⌈log₂ V⌉ tur vardır ve her tur O(E) sürer; toplam O(E log V)'dir. Bileşenlerin seçimleri birbirinden bağımsız olduğu için algoritma paralel çalışmaya uygundur. Ağırlıklar eşit olabiliyorsa tutarlı bir eşitlik bozucu gerekir; yoksa iki bileşen eşit ağırlıklı farklı kenarlar seçip bir döngü kurabilir.

Üç algoritma aynı çizgede aynı MST'yi bulur, yeter ki ağırlıklar farklı olsun. Ağırlıklar farklıysa MST tektir ve hepsinin bulduğu ağaç odur. Eşit ağırlıklar varsa farklı ağaçlar bulabilirler, ama toplam ağırlıkları aynıdır. Farkları kenarları ele alma sırasında ve gereken veri yapısındadır. Tüm kenarların ağırlığı aynı olduğunda örneğin her kapsayan ağaç bir MST'dir; Kruskal bu durumda kenar listesinin sırasına göre herhangi bir kapsayan ağacı üretir.

Bir kenarın ağırlığı tek başına onun MST'de olup olmayacağını söylemez. Her MST'de bulunan kenarlar, bir kesimin tek en hafif kenarı olanlardır. Hiçbir MST'de bulunmayan kenarlar ise bir döngünün tek en ağır kenarı olanlardır; bu ikinci kurala döngü özelliği denir ve ters silme algoritması ona dayanır. Kenarlara aynı sabitin eklenmesi MST'yi değiştirmez, çünkü kenarların sırası korunur ve bütün kapsayan ağaçlarda V − 1 kenar olduğundan bütün toplamlar aynı miktarda artar. Kenarlar azalan sırada işlenirse Kruskal aynı biçimde maksimum kapsayan ağacı bulur.

7.7Huffman kodlama

Bir metin bilgisayarda bitlerle saklanır. Her karaktere bir bit dizisi, yani bir kod sözcüğü atanır ve metin bu kodların art arda yazılmasıyla oluşur. ASCII gibi kodlamalarda her karakterin kodu aynı uzunluktadır. Ancak gerçek metinlerde karakterler eşit sıklıkta geçmez. Türkçe bir metinde “a” ve “e” harfleri çok sık, “ğ” ve “j” çok seyrek görülür. Sık karakterlere kısa, seyrek karakterlere uzun kodlar verilirse metnin toplam uzunluğu kısalır. Huffman kodlama bu fikri en iyi biçimde uygulayan açgözlü bir algoritmadır.

7.7.1Sabit ve değişken uzunluklu kodlar

Huffman kodlama kayıpsız bir veri sıkıştırma yöntemidir: sıkıştırılmış veri çözüldüğünde özgün veri bit bit aynen geri gelir. Yöntemi David Huffman 1952'de, öğrenciyken bir dönem ödevi olarak geliştirmiştir. Sunumdaki örnek metin 25 karakter uzunluğundadır ve yalnız altı farklı karakter içerir: F, O, R, G, E ve T. Altı karakteri birbirinden ayırmak için sabit uzunluklu bir kodda ⌈log₂ 6⌉ = 3 bit gerekir; 2 bit yalnız dört karakteri ayırabilir. Bu durumda metin 25 × 3 = 75 bit tutar. Her karakter 8 bitlik ASCII ile saklansaydı 200 bit tutardı.

Değişken uzunluklu bir kodda kod sözcüklerinin uzunlukları farklıdır. Metnin toplam uzunluğu her karakterin frekansı ile kod uzunluğunun çarpımlarının toplamıdır:

Toplam bit = Σ frekans(c) · uzunluk(c)

Bu toplamı küçültmek için en sık karakterlerin kodları kısa tutulmalıdır. Ancak kodlar keyfî biçimde kısaltılamaz; kısaltılmış kodların hâlâ tek anlamlı çözülebilmesi gerekir.

7.7.2Önek-özgür kodlar

Kodlar a = 0, b = 01, c = 1 olsun. “01” bit dizisi alındığında bunun “ab” mi yoksa yalnız “b” mi olduğu anlaşılamaz. Sorunun kaynağı, a'nın kodu 0'ın, b'nin kodu 01'in başında yer almasıdır. Kod sözcükleri arasına bir ayırıcı konarak bu sorun çözülebilir, ama ayırıcı da bit harcar. Daha iyi bir çözüm, hiçbir kodun bir başka kodun başlangıcı olmamasıdır.

Önek-özgür kodlar ikili ağaçlarla gösterilir. Kökten başlanır; sol kenar 0, sağ kenar 1 anlamına gelir. Her karakter bir yapraktadır ve kökten o yaprağa giden yoldaki bitler karakterin kodudur. Bir karakter iç düğümde dursaydı, onun kodu altındaki yaprakların kodlarının öneki olurdu. Karakterler yalnız yapraklarda durduğu için hiçbir kod bir başkasının öneki olamaz. Bir kodun uzunluğu, karakterin ağaçtaki derinliğidir.

Çözme işlemi ağaç üzerinde yapılır. Kökten başlanır; her bit okunduğunda 0 ise sol, 1 ise sağ çocuğa inilir. Bir yaprağa varılınca o yapraktaki karakter yazılır ve köke dönülür. Bir kod sözcüğünün bittiği an, yaprağa varıldığı andır ve bu an kesin olarak bilinir. Örneğin Şekil 7.13'ün sağındaki ağaçla “00110” dizisi 00 | 1 | 1 | 0… diye okunur: ilk iki bit a'yı, sonraki bit c'yi, bir sonraki yine c'yi verir. Son 0 tek başına bir yaprağa ulaşmaz; dizi eksik gelmiştir.

Optimal bir önek-özgür kodun ağacı tam bir ikili ağaçtır: her iç düğümün iki çocuğu vardır. Tek çocuklu bir iç düğüm olsaydı, o düğüm atlanıp çocuğu yukarı taşınabilirdi; altındaki bütün kodlar bir bit kısalırdı ve kodlar yine önek-özgür kalırdı. Şekildeki sol ağaçta kökün sol çocuğu olan a düğümünün tek çocuğu vardır; sağ ağaç bu yüzden daha iyidir.

7.7.3Algoritmanın adımları

Huffman algoritması ağacı aşağıdan yukarıya kurar. Her karakter başlangıçta kendi frekansıyla tek düğümlü bir ağaçtır. Her adımda frekansı en küçük iki ağaç birleştirilir: ikisi yeni bir iç düğümün çocukları olur ve yeni düğümün frekansı çocuklarının frekanslarının toplamıdır. Tek ağaç kalınca o ağaç Huffman ağacıdır. Adımlar şöyle sıralanır:

1. Her karakterin frekansı hesaplanır.
2. Her karakter için bir yaprak oluşturulur. En küçük frekanslı iki düğüm birleştirilerek yeni bir iç düğüm yapılır; bu adım tek düğüm kalana kadar tekrarlanır.
3. Ağaçta her karakterin kodu, kökten yaprağa giden yoldan okunur: sol kenar 0, sağ kenar 1.
4. Metin bu kodlarla kodlanır.

Açgözlü seçim ikinci adımdadır: her birleştirmede o an en küçük frekanslı iki ağaç seçilir. Bu iki ağacın yaprakları birleştirmeden sonra bir seviye derine iner, yani kodları bir bit uzar. En seyrek karakterlerin kodlarını uzatmak, toplam bit sayısını en az artıran seçimdir. Sunumdaki örneğin frekansları Tablo 7.14'te verilmiştir.

n karakter için tam olarak n − 1 birleştirme yapılır, çünkü her birleştirme ağaç sayısını bir azaltır ve n ağaçtan bir ağaca inilir. Bu yüzden Huffman ağacında n yaprak ve n − 1 iç düğüm vardır. Örnekte altı karakter, beş birleştirme vardır.

7.7.4Ağacı kurmak: kod ve izleme

Sunumdaki huffman metodu ağacı bir öncelikli kuyrukla kurar:

static Dugum huffman(char[] h, int[] f) {
  PriorityQueue<Dugum> kuyruk =
    new PriorityQueue<>((a, b) -> a.f - b.f);
  for (int k = 0; k < h.length; k++)
    kuyruk.add(new Dugum(h[k], f[k]));
  while (kuyruk.size() > 1) {
    Dugum sol = kuyruk.poll();
    Dugum sag = kuyruk.poll();
    Dugum ata = new Dugum('\0', sol.f + sag.f);
    ata.sol = sol;
    ata.sag = sag;
    kuyruk.add(ata);
  }
  return kuyruk.poll();
}

Dugum sınıfının dört alanı vardır: karakter h, frekans f, sol ve sağ çocuk. Yapraklarda çocuklar null'dır. Kuyruk, (a, b) -> a.f - b.f karşılaştırıcısıyla kurulan bir PriorityQueue'dur. Java'nın bu sınıfı bir en küçük öbektir (min-heap); poll() her çağrıldığında frekansı en küçük düğümü çıkarır. İlk döngü her karakter için bir yaprak oluşturup kuyruğa ekler. while döngüsü kuyrukta birden çok düğüm olduğu sürece döner. Her turda iki kez poll() çağrılır; ilk çıkan sol, ikinci çıkan sağ çocuk olur. Yeni iç düğümün karakteri '\0''dır, çünkü iç düğümler bir karakter taşımaz; frekansı iki çocuğun toplamıdır. Yeni düğüm kuyruğa geri eklenir. Döngü bitince kuyrukta tek düğüm kalır ve bu düğüm ağacın köküdür.

Tablodaki kuyruk içerikleri frekans sırasıyla yazılmıştır; öbeğin dizideki gerçek düzeni farklıdır. İkinci ve üçüncü turlarda eşitlik vardır. İkinci turda G4 ile R4'ün, üçüncü turda (5) ile E5'in frekansı aynıdır. Hangisinin önce çıkacağı öbeğin iç düzenine, dolayısıyla karakterlerin kuyruğa eklenme sırasına bağlıdır. Tablo sunumdaki izlemeyi izler. Karakterler F, O, R, G, E, T sırasıyla eklendiğinde Java'nın PriorityQueue'su üçüncü turda önce E5'i çıkarır ve E sol çocuk olur. Bu durumda kodlar E = 00, F = 010, O = 011 olur; geri kalan kodlar değişmez. Kod uzunlukları ve toplam bit sayısı iki durumda da aynıdır: E 2 bit, F ve O 3 bit.

Ağacın yapısı tablodan okunabilir. Kökün sol çocuğu (10), sağ çocuğu (15)'tir. (10)'un çocukları (5) ve E, (15)'in çocukları T ve (8)'dir. (5)'in altında F ve O, (8)'in altında G ve R vardır. E ve T derinlik 2'de, F, O, G ve R derinlik 3'tedir. En sık iki karakter, en kısa kodları almıştır.

Ağacın toplam bit maliyeti iç düğümlerin frekanslarının toplamına da eşittir: 5 + 8 + 10 + 15 + 25 = 63. Bunun nedeni şudur: bir karakter, kökten yaprağına giden yoldaki her iç düğümün frekansına bir kez katkı yapar. Yoldaki iç düğüm sayısı karakterin derinliğidir. Böylece her karakterin frekansı derinliği kadar sayılmış olur ve toplam Σ frekans · derinlik'e eşit çıkar. Bu gözlem, Huffman'ın her birleştirmede neden en küçük iki frekansı seçtiğini de açıklar: her birleştirmenin maliyeti yeni iç düğümün frekansıdır ve algoritma her adımda bu maliyeti en küçük tutar.

Maliyet şöyledir. n yaprağın kuyruğa eklenmesi O(n log n) sürer. Döngü n − 1 kez döner ve her turda iki poll ile bir add yapar; her biri O(log n)'dir. Toplam O(n log n)'dir. Burada n farklı karakter sayısıdır, metnin uzunluğu değildir. Frekanslar baştan sıralıysa iki sıradan kuyruk ile O(n) sürede çalışan bir sürüm de yazılabilir: birinci kuyruk sıralı yaprakları, ikinci kuyruk sırayla oluşan iç düğümleri tutar. Oluşan iç düğümlerin frekansları artan sırada geldiği için ikinci kuyruk kendiliğinden sıralı kalır.

7.7.5Kodları üretmek: kod ve izleme

Ağaç kurulduktan sonra her karakterin kodu ağacın bir kez gezilmesiyle bulunur. Sunumdaki özyinelemeli kodUret metodu bunu yapar:

static void kodUret(Dugum d, String kod) {
  if (d.sol == null) {      // yaprak
    System.out.println(d.h + " = " + kod);
    return;
  }
  kodUret(d.sol, kod + "0"); // sol: 0
  kodUret(d.sag, kod + "1"); // sağ: 1
}

Metot bir düğüm ve o düğüme gelene kadar biriken bit dizisini alır. Düğüm bir yapraksa, yani sol çocuğu null'sa, karakter ve kodu yazdırılır. Huffman ağacı tam bir ikili ağaç olduğu için yalnız sol çocuğa bakmak yeterlidir: iç düğümlerin iki çocuğu da vardır, yaprakların hiç çocuğu yoktur. Düğüm iç düğümse metot önce sol çocuğa koda “0” ekleyerek, sonra sağ çocuğa “1” ekleyerek iner. Bu bir önce-sıra (preorder) gezintisidir; yapraklar soldan sağa sırayla yazdırılır. İlk çağrı kodUret(kok, "") biçimindedir.

Metot toplam 11 kez çağrılır: 6 yaprak ve 5 iç düğüm için birer kez. Her düğüm bir kez ziyaret edildiği için gezinti O(n) düğüm ziyareti yapar. Özyineleme derinliği ağacın yüksekliği kadardır; örnekte kökten en derin yaprağa 3 kenar vardır. Dizgi birleştirme kod + "0" her çağrıda yeni bir dizgi oluşturur ve uzunluğu kadar zaman alır. Bu maliyet de sayılırsa toplam iş, bütün kodların uzunlukları toplamıyla orantılıdır. Kodlar bir StringBuilder ile ya da bir karakter dizisinde tutulursa bu ek maliyet önlenir.

7.7.6Kodlama, çözme ve kazanç

Tablo 7.17 her karakterin kodunu ve metindeki toplam katkısını verir.

Huffman kodu metni 63 bitle yazar; sabit 3 bitlik kod 75 bit kullanır. Kazanç (75 − 63) / 75 = %16'dır. Karakter başına ortalama 63 / 25 = 2,52 bit düşer. Kazanç, frekansların ne kadar dengesiz olduğuna bağlıdır. Bütün karakterler eşit sıklıkta geçseydi kazanç çok az olurdu; a–f örneğindeki gibi bir karakter çok baskınsa kazanç büyür.

Kodlama için her karakterin kodu sırayla yazılır. “FORTE” sözcüğü 000 | 001 | 111 | 10 | 01 olur, yani 13 bit. Sabit kodla aynı sözcük 5 × 3 = 15 bit tutardı. Kodlama sırasında bitler arasına ayırıcı konmaz; buradaki dikey çizgiler yalnız okumayı kolaylaştırmak içindir.

Çözme için ağaç kullanılır. “1100110” bit dizisi alınsın. Kökten başlanır. 1 ile sağa, (15)'e; 1 ile sağa, (8)'e; 0 ile sola, G'ye inilir. G yazılır ve köke dönülür. 0 ile sola, (10)'a; 1 ile sağa, E'ye inilir. E yazılır, köke dönülür. 1 ile sağa, (15)'e; 0 ile sola, T'ye inilir. T yazılır. Sonuç 110 | 01 | 10, yani “GET”'tir. Çözme her bit için bir kenar iner; m bitlik bir dizi O(m) sürede çözülür.

Sol ve sağ çocukların yeri keyfîdir. Örneğin T, (15)'in sağ çocuğu yapılabilir. Bu durumda kodlar değişir, ama kod uzunlukları ve toplam 63 bit değişmez. Aynı nedenle eşit frekanslı düğümlerin hangisinin önce seçildiği de kod uzunluklarını değiştirebilir, ama toplam bit sayısını değiştirmez. Bir metnin birden çok en iyi önek-özgür kodu olabilir.

Sıkıştırılmış veri tek başına çözülemez; aynı ağaç ya da kod tablosu çözücünün elinde de bulunmalıdır. Bu yüzden ağaç (ya da her karakterin kod uzunluğu) sıkıştırılmış veriyle birlikte gönderilir. Kısa metinlerde bu ek bilgi kazancın tamamını yiyebilir. 25 karakterlik örnekte altı karakterin kod tablosu, kazanılan 12 bitten çok daha fazla yer tutar. Huffman kodlama bu yüzden uzun metinlerde ve büyük dosyalarda anlamlıdır.

Bir kodun ne kadar iyi olabileceğinin teorik bir alt sınırı da vardır. Karakter c'nin metindeki oranı p_c ise karakter başına ortalama bit sayısı H = −Σ p_c log₂ p_c değerinin altına inemez. Bu değere metnin entropisi denir. Örnek metnin entropisi yaklaşık 2,48 bittir; Huffman kodu 2,52 bit kullanır. Huffman kodunun ortalaması her zaman entropi ile entropi artı bir bit arasındadır.

7.7.7Huffman kodu neden en iyidir?

Bir önek-özgür kod ağacı T'nin maliyeti B(T) = Σ f(c) · d_T(c)'dir; f(c) karakterin frekansı, d_T(c) ağaçtaki derinliğidir. Huffman'ın kurduğu ağacın bu maliyeti en küçük yaptığı iki adımda gösterilir: açgözlü seçim ve optimal alt yapı.

İki teorem birlikte tümevarımla Huffman algoritmasının doğruluğunu verir. Algoritma ilk adımda en küçük iki frekansı birleştirir; açgözlü seçim teoremi bu seçimi içeren bir en iyi ağaç olduğunu söyler. Birleştirilen iki karakter tek bir z karakteri gibi davranır ve problem bir karakter küçülür. Optimal alt yapı teoremi, küçük problemin en iyi ağacından asıl problemin en iyi ağacının elde edildiğini söyler. Böylece Huffman kodu, önek-özgür kodlar arasında Σ frekans · derinlik toplamını en küçük yapan koddur.

7.7.8Maliyet ve kullanım alanları

Huffman kodlamanın bütün aşamalarının maliyeti şöyledir. m karakterlik bir metinde n farklı karakter olsun. Frekans sayımı metni bir kez okur: O(m). Ağacın kurulması O(n log n), kodların üretilmesi O(n) düğüm ziyareti sürer. Kodlama metni bir kez daha okur ve her karakterin kodunu tablodan alır: O(m) karakter ve çıktının bit sayısı kadar iş. Genellikle n, m'den çok küçüktür (örneğin bir baytlık karakterlerde n ≤ 256); bu yüzden toplam süre pratikte metnin uzunluğuyla doğru orantılıdır.

Huffman kodlama tek başına değil, çoğu zaman başka yöntemlerle birlikte kullanılır. ZIP ve gzip dosyalarının ve PNG resimlerinin kullandığı DEFLATE biçimi, önce tekrar eden dizgileri geriye dönük göstericilerle kısaltır, sonra çıkan sembolleri Huffman ile kodlar. JPEG resim ve MP3 ses biçimlerinde de veri önce dönüştürülür ve nicelenir; son aşamadaki entropi kodlaması Huffman kodlarıyla yapılır. Dizgi Sıkıştırma simülatörü RLE ve LZW yöntemlerini adım adım gösterir. LZW sözlük tabanlıdır: tekrar eden dizgilere kod verir. Huffman ise frekans tabanlıdır: tek tek karakterlere frekanslarına göre kod verir. İki yaklaşımın farkı simülatördeki örneklerle Huffman'ın sonuçları karşılaştırılarak görülebilir.

7.8Diğer açgözlü algoritmalar

Açgözlü fikir birçok başka algoritmanın da temelindedir. Bunların bir kısmı kanıtlanmış olarak en iyi sonucu verir. Bir kısmı ise en iyi sonucu garanti etmez, ama sonucun en iyiden ne kadar uzak olabileceği bilinir.

Dijkstra ve Prim. İki algoritma da her adımda bir öncelikli kuyruktan en küçük anahtarlı düğümü alır ve onu kalıcı olarak seçer. Dijkstra'da anahtar, kaynaktan o düğüme bilinen en kısa uzaklıktır; Prim'de, düğümü ağaca bağlayan en ucuz kenarın ağırlığıdır. Seçilen düğüm bir daha değiştirilmez. Dijkstra negatif ağırlıklı kenar bulunmayan çizgelerde en kısa yolları doğru bulur; negatif kenar varsa kalıcı sayılan bir uzaklık sonradan kısalabilir ve açgözlü seçim yanılır. Prim ise kesim özelliğine dayandığı için ağırlıkların işaretinden bağımsız olarak doğrudur.

Çizge boyama. Komşu düğümlerin farklı renk alması koşuluyla bir çizgeyi en az renkle boyamak NP-zor bir problemdir. Açgözlü boyama düğümleri belli bir sırayla ele alır ve her düğüme komşularının kullanmadığı en küçük rengi verir. Hızlıdır, ama kullanılan renk sayısı sıraya bağlıdır. Altı düğümlü bir döngü düşünülsün: a1 – b2 – a3 – b1 – a2 – b3 – a1. Bu döngü iki renkle boyanabilir: a'lar bir renk, b'ler öbür renk. Düğümler a1, a2, a3, b1, b2, b3 sırasıyla boyanırsa gerçekten iki renk yeter. Ancak sıra a1, b1, a2, b2, a3, b3 olursa a1 ve b1 komşu olmadıkları için ikisi de 1 rengini alır. a2, b1'e komşu olduğu için 2'yi, b2, a1'e komşu olduğu için yine 2'yi alır. a3 hem b1'e (1) hem b2'ye (2) komşudur ve 3'ü alır; b3 de aynı nedenle 3'ü alır. Kötü bir sıra bir renk fazla kullandırmıştır. Açgözlü boyama en fazla “en büyük derece artı bir” renk kullanır; bu sınır her zaman sağlanır.

Kutulara yerleştirme (bin packing). Boyutları verilen nesneler, kapasitesi sabit olan en az sayıda kutuya yerleştirilmek istenir. Bu problem de NP-zordur. İlk sığan kuralı her nesneyi sığdığı ilk kutuya koyar; hiçbirine sığmıyorsa yeni bir kutu açar. En iyi sığan kuralı ise nesneyi, koyulduğunda en az boşluk bırakan kutuya koyar. Kapasite 10 ve nesneler 2, 5, 4, 7, 1, 3, 8 olsun. İlk sığan bu sırayla dört kutu açar: [2, 5, 1], [4, 3], [7], [8]. Nesneler önce büyükten küçüğe sıralanırsa (azalan sırayla ilk sığan) üç kutu yeter: [8, 2], [7, 3], [5, 4, 1]. Toplam boyut 30 olduğu için üçten az kutu mümkün değildir. Azalan sırayla ilk sığanın en fazla yaklaşık 11/9 · OPT + 1 kutu kullandığı kanıtlanmıştır; burada OPT en az kutu sayısıdır.

En büyük kapsama (maximum coverage). Bir öğeler evreni ve bu öğelerin alt kümeleri verilir; en fazla k küme seçilerek olabildiğince çok öğe kapsanmak istenir. Açgözlü algoritma her adımda henüz kapsanmamış öğelerden en çoğunu kapsayan kümeyi seçer. Bu yöntemin en iyinin en az 1 − 1/e ≈ 0,632'si kadar öğe kapsadığı, yani en iyinin yaklaşık %63'üne ulaştığı kanıtlanmıştır. Daha iyi bir oranı polinom sürede garanti eden bir algoritma, P = NP olmadıkça yoktur.

Bu son örnekler, açgözlü algoritmaların NP-zor problemlerdeki rolünü gösterir. En iyi çözümü bulmak çok pahalıdır, ama açgözlü bir algoritma hızlıca bir çözüm üretir ve bu çözümün kalitesi için kanıtlanmış bir alt sınır verir. Böyle algoritmalara yaklaşım algoritması denir; çözümün en iyiye en kötü durumdaki oranına da yaklaşım oranı denir.

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

Tablo 7.18 notta incelenen problemleri açgözlü ölçüt, süre ve en iyilik bakımından karşılaştırır.

Tablonun son sütunu, açgözlü yaklaşımın en önemli dersini özetler. Dört problemde açgözlü algoritma en iyidir ve bu, birer değiştirme argümanıyla kanıtlanmıştır. Para üstünde sonuç para sistemine bağlıdır. 0/1 sırt çantasında ise oran ölçütü en iyiyi kaçırır. İş sıralamadaki O(n²), sunumdaki doğrudan dilim aramasının en kötü durumudur; ayrık kümelerle bu da O(n log n)'ye iner.

Notun farklı yerlerinde ayrıntılı ele alınan hatalar şöyle toplanabilir:

• Açgözlüyü kanıtsız doğru saymak. {1, 3, 4} paralarıyla 6 tutarında açgözlü 3 para, en iyi çözüm 2 para kullanır. Her problemde açgözlü seçim özelliği gösterilmelidir; birkaç başarılı deneme kanıt değildir.
• Yanlış ölçüt. Etkinlik seçiminde en erken başlayan, en kısa süren ya da en az çakışan etkinliği seçmek en iyi sonucu garanti etmez. Doğru ölçüt en erken bitendir.
• 0/1 sırt çantasında oran ölçütü. Kesirli problemde en iyi olan oran ölçütü, nesneler bölünemediğinde en iyiyi garanti etmez.
• En erken boş dilim. İş sıralamada işi son tarihinden önceki en erken boş dilime koymak, son tarihi yakın işlere yer bırakmaz. En geç boş dilim seçilmelidir.
• Kesim özelliğini yanlış okumak. Güvenli olan, bir kesimi geçen en hafif kenardır. Tüm çizgedeki en hafif kenarlar körü körüne alınırsa döngü oluşabilir; Kruskal bu yüzden döngü kuran kenarı atar.
• Huffman'da ağaçsız çözme. Kod tablosu ya da ağaç gönderilmezse veri çözülemez. Tek karakterli metinde kök bir yapraktır; koda en az 1 bit verilmelidir.

7.10Özet

• Açgözlü algoritma: çözümü adım adım kurar, her adımda bir ölçüte göre o an en iyi görünen seçimi yapar ve kararlarını geri almaz. Tipik yapı sıralama ve tek geçiştir; süre çoğunlukla O(n log n)'dir.
• Doğruluk koşulları: açgözlü seçim özelliğine göre ilk seçimi içeren bir en iyi çözüm vardır. Optimal alt yapıya göre kalan problemin en iyi çözümü, ilk seçimle birlikte bütünün en iyi çözümünü verir. İki özellik birlikte sağlanırsa açgözlü algoritma en iyidir; sağlanmazsa yalnız bir sezgiseldir.
• Değiştirme argümanı: keyfi bir en iyi çözümün bir parçası açgözlü seçimle değiştirilir; çözümün uygun kaldığı ve kötüleşmediği gösterilir. Etkinlik seçimi, iş sıralama, kesirli sırt çantası, kesim özelliği ve Huffman kanıtları bu kalıbı kullanır.
• Para üstü: sığan en büyük para seçilir; O(k + adet). Kanonik sistemlerde (ör. {50, 25, 10, 5, 1}) en iyidir; {4, 3, 1} sisteminde 6 ve 10 tutarları, {10, 7, 1} sisteminde 14 tutarı karşı örnektir. En iyi sonuç enAz[t] = 1 + min enAz[t − p] bağıntısıyla O(k · T) sürede bulunur.
• Etkinlik seçimi: etkinlikler bitişe göre sıralanır; son seçilenin bitişinden sonra başlayan her etkinlik seçilir. O(n log n); sunumdaki on etkinlikten 6'sı seçilir.
• İş sıralama: işler kâra göre azalan sırayla, son tarihinden önceki en geç boş dilime konur. Doğrudan aramayla en kötü O(n²), ayrık kümelerle neredeyse sıralama süresi. Sunumdaki altı işte toplam kâr 140'tır.
• Kesirli sırt çantası: nesneler kâr/ağırlık oranına göre azalan sırayla, sığdığı kadar alınır; son nesneden bir parça alınabilir. O(n log n); örnekte 240. 0/1 sürümde aynı ölçüt 160 verir, en iyisi 220'dir.
• MST ve kesim özelliği: bir kesimi geçen en hafif kenar bir MST'ye aittir. Kruskal (iki bileşeni ayıran kesim), Prim (ağaç ile geri kalanı) ve Borůvka (her bileşen ile geri kalanı) bu özelliği farklı kesimlerle kullanır; üçü de O(E log V)'dir.
• Huffman kodlama: en düşük frekanslı iki ağaç tekrar tekrar birleştirilir; sol kenar 0, sağ kenar 1. Kodlar önek-özgürdür ve Σ frekans · derinlik toplamı en küçüktür. Örnekte 63 bit (sabit kodla 75); ağaç O(n log n) sürede kurulur ve çözücüye gönderilmelidir.
• Yaklaşım algoritmaları: çizge boyama, kutulara yerleştirme ve en büyük kapsama gibi NP-zor problemlerde açgözlü algoritmalar en iyiyi garanti etmez, ama kanıtlanmış oranlarla iyi çözümler üretir.

7.11Kavram listesi

• açgözlü algoritma greedy algorithm
• açgözlü seçim özelliği greedy-choice property
• optimal alt yapı optimal substructure
• değiştirme argümanı exchange argument
• sezgisel heuristic
• para üstü problemi coin change problem
• kanonik para sistemi canonical coin system
• etkinlik seçimi activity selection
• son tarihli iş sıralama job sequencing with deadlines
• matroid matroid
• kesirli sırt çantası fractional knapsack
• 0/1 sırt çantası 0/1 knapsack
• minimum kapsayan ağaç minimum spanning tree (MST)
• kesim cut
• kesim özelliği cut property
• Huffman kodlama Huffman coding
• önek-özgür kod prefix-free code
• sıkıştırma compression
• entropi entropy
• öncelikli kuyruk priority queue
• çizge boyama graph coloring
• yaklaşım algoritması approximation algorithm
• yaklaşım oranı approximation ratio

7.12Kendini Dene

1. Para sistemi {9, 6, 5, 1} olsun. 11 ve 12 tutarları için açgözlü para üstü kaç para kullanır? En iyi çözümler nedir? Bu sistem kanonik midir?

   Cevap

   11 için açgözlü 9 + 1 + 1 ile 3 para kullanır; en iyisi 6 + 5 ile 2 paradır. 12 için açgözlü 9 + 1 + 1 + 1 ile 4 para kullanır; en iyisi 6 + 6 ile 2 paradır. Sistem kanonik değildir. 11, bu sistemde açgözlünün yanıldığı en küçük tutardır ve en büyük iki paranın toplamı olan 15'ten küçüktür.

2. Sekiz etkinlik (s, f) çiftleriyle verilmiştir ve 1'den 8'e numaralıdır: (0, 3), (1, 2), (2, 5), (3, 4), (4, 7), (5, 6), (6, 9), (8, 10). En erken biten ölçütü hangi etkinlikleri seçer?

   Cevap

   Bitişe göre sıra: #2 (1, 2), #1 (0, 3), #4 (3, 4), #3 (2, 5), #6 (5, 6), #5 (4, 7), #7 (6, 9), #8 (8, 10). #2 seçilir (son bitiş 2). #1 0'da başlar, atlanır. #4 3'te başlar, seçilir (4). #3 atlanır. #6 5'te başlar, seçilir (6). #5 atlanır. #7 6'da başlar, seçilir (9). #8 8'de başlar, 8 < 9 olduğu için atlanır. Sonuç 4 etkinliktir: #2, #4, #6, #7. Bütün alt kümeler denenirse 5 etkinlikli çakışmasız bir küme bulunamaz.

3. Etkinlik seçiminde her adımda en geç başlayan etkinliği seçen algoritma en iyi sonucu verir mi? Gerekçelendiriniz.

   Cevap

   Evet. Zaman ekseni ters çevrilirse (her [s, f) aralığı [−f, −s) olur) en geç başlayan etkinlik, en erken biten etkinliğe dönüşür ve çakışma ilişkisi değişmez. En erken biten için yapılan değiştirme argümanı aynen geçerlidir. En geç başlayan a, bir en iyi çözümün en son etkinliğinin yerine konabilir. a o etkinlikten daha erken başlamaz ve önceki etkinliklerle çakışmaz.

4. Yedi iş (ad, son tarih, kâr) olarak verilmiştir: (A, 3, 35), (B, 4, 30), (C, 4, 25), (D, 2, 20), (E, 3, 15), (F, 1, 12), (G, 2, 5). Açgözlü iş sıralama dilimleri nasıl doldurur ve toplam kâr kaçtır? İşler en erken boş dilime konsaydı sonuç ne olurdu?

   Cevap

   Kâr sırası A, B, C, D, E, F, G'dir. A → 3. dilim; B → 4. dilim; C'nin son tarihi 4'tür, 4 ve 3 doludur, 2. dilime konur; D'nin son tarihi 2'dir, 2 doludur, 1. dilime konur. E, F ve G için uygun boş dilim kalmamıştır. Dilimler 1–4: D, C, A, B; toplam kâr 20 + 25 + 35 + 30 = 110, en iyi sonuçtur. En erken boş dilim kuralıyla A 1. dilime, B 2. dilime, C 3. dilime gider; D, E, F ve G'ye yer kalmaz ve toplam 90'da kalır.

5. Kapasite W = 20, nesneler (kâr, ağırlık) olarak (48, 12), (30, 10), (28, 10), (5, 1) olsun. Kesirli sırt çantasının değeri nedir? Nesneler bölünemeseydi oran ölçütü ne bulurdu, en iyi sonuç ne olurdu?

   Cevap

   Oranlar 4; 3; 2,8 ve 5'tir. Oran sırası (5, 1), (48, 12), (30, 10), (28, 10)'dur. (5, 1) ve (48, 12) tümüyle alınır: 13 kg, 53 kâr. Kalan 7 kg için (30, 10)'un 7/10'u alınır: 21. Kesirli değer 74'tür. 0/1 durumunda oran ölçütü (5, 1) ve (48, 12)'yi alır; ardından gelen iki nesne de kalan 7 kg'a sığmaz ve sonuç 53'tür. En iyi 0/1 seçim (30, 10) ile (28, 10)'dur: tam 20 kg, 58 kâr.

6. Frekanslar A:1, B:1, C:2, D:3, E:5, F:8 olsun. Huffman ağacının birleştirmelerini, kod uzunluklarını ve toplam bit sayısını bulunuz. Sabit uzunluklu kodla karşılaştırınız.

   Cevap

   Birleştirmeler: 1 + 1 = 2; 2 + 2 = 4; 3 + 4 = 7; 5 + 7 = 12; 8 + 12 = 20. Her birleştirme bir önceki birleştirmenin sonucunu içerdiği için ağaç tek yöne doğru uzar. Kod uzunlukları F 1, E 2, D 3, C 4, A ve B 5 bittir. Toplam bit 8 · 1 + 5 · 2 + 3 · 3 + 2 · 4 + 1 · 5 + 1 · 5 = 45'tir; iç düğümlerin toplamı da 2 + 4 + 7 + 12 + 20 = 45 verir. Altı karakter için sabit kod 3 bit ister: 20 × 3 = 60 bit.

7. Kodlar F = 000, O = 001, E = 01, T = 10, G = 110, R = 111 olsun. 11001101001111 bit dizisi hangi metne çözülür? Aynı metin 3 bitlik sabit kodla kaç bit tutardı?

   Cevap

   Soldan okunur: 110 → G, 01 → E, 10 → T, 10 → T, 01 → E, 111 → R. Metin “GETTER”dır. Huffman ile 14 bit, sabit kodla 6 × 3 = 18 bit tutar. Hiçbir kod bir başkasının öneki olmadığı için her kodun bittiği yer kesin olarak bellidir.

8. Aşağıdaki iki ifade doğru mudur? (a) Ağırlıkları farklı bağlı bir çizgede en hafif kenar her MST'dedir. (b) En ağır kenar hiçbir MST'de bulunmaz.

   Cevap

   (a) Doğrudur. En hafif kenarın iki ucundan biri S'ye, öteki V − S'ye konarak bir kesim kurulur. Bu kenar kesimi geçen kenarların en hafifidir ve tek en hafif olduğu için kesim özelliğine göre her MST'dedir. (b) Yanlıştır. En ağır kenar bir köprü olabilir: silindiğinde çizge ikiye ayrılıyorsa her kapsayan ağaçta bulunmak zorundadır. Bir kenarın MST'den dışlanması için bir döngünün tek en ağır kenarı olması gerekir.

9. Kesirli sırt çantası için verilen değiştirme argümanı, 0/1 sırt çantasında hangi adımda bozulur?

   Cevap

   Kanıt, en iyi çözümden düşük oranlı bir nesnenin δ kilogramını çıkarıp yerine yüksek oranlı nesnenin δ kilogramını koyar. Bu değiştirme ağırlığı korur ve kârı azaltmaz. 0/1 durumunda nesneler parça parça alınamaz; ancak bütün nesneler değiştirilebilir. Ağırlıkları farklı iki nesne değiştirildiğinde ya kapasite aşılır ya da çantada değersiz bir boşluk kalır. Uygunluk koşulu ya da “daha kötü olmaz” koşulu bozulur.

10. n = 10⁶ işin hepsinin son tarihi n olsun. Doğrudan dilim aramasıyla iş sıralama kaç dilim bakışı yapar? Ayrık kümelerle bu sayı yaklaşık ne olur?

    Cevap

    i. iş en geç dilimden başlayıp geriye doğru ilk boş dilimi arar; önceki i − 1 iş en sondaki dilimleri doldurduğu için i dilime bakar. Toplam 1 + 2 + … + n = n(n + 1)/2 ≈ 5 · 10¹¹ bakıştır. Ayrık kümelerle her iş birkaç bul ve birlestir çağrısıyla yerleşir ve toplam iş neredeyse doğrusal, yani birkaç milyon adım düzeyindedir. Bu durumda süreyi n log₂ n ≈ 2 · 10⁷ karşılaştırma yapan sıralama belirler.

7.13İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 15: etkinlik seçimi, açgözlü stratejinin öğeleri ve Huffman kodlarının en iyiliği, burada özetlenen kanıtların tam biçimiyle verilir.
• J. Kleinberg ve É. Tardos, Algorithm Design (2006), Bölüm 4: aralık çizelgeleme, “açgözlü önde kalır” ve değiştirme argümanı kanıt teknikleri ile en az çakışan ölçütüne karşı örnekler ayrıntılı tartışılır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 5.5: Huffman sıkıştırmasının Java ile eksiksiz bir uygulaması, ağacın dosyaya yazılması ve okunması dahil.
• D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes” (1952): yöntemin ilk yayımlandığı kısa ve okunaklı özgün makale.

7.14Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 15: Greedy Algorithms; Bölüm 21: Minimum Spanning Trees).
2. D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Proceedings of the IRE 40(9), 1098–1101, 1952.
3. J. Kleinberg, É. Tardos, Algorithm Design, Addison-Wesley, 2006 (Bölüm 4: Greedy Algorithms).
4. D. Kozen, S. Zaks, “Optimal Bounds for the Change-Making Problem”, Theoretical Computer Science 123(2), 377–388, 1994.
5. J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society 7(1), 48–50, 1956.
6. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Kesim 4.3: Minimum Spanning Trees; Kesim 5.5: Data Compression).

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