Açgözlü Algoritma
- İngilizcesi
- Greedy Algorithm
- Okunuşu
- gridi elgıridım
Günlük kullanımda iki ad da yaygın.
Kısaca
Açgözlü algoritma, önceki kararları yeniden düşünmeden her adımda o an en iyi görünen seçimi yaparak çözümü adım adım kuran bir algoritmadır.
Açgözlü algoritma (greedy algorithm) nedir?
Açgözlü algoritma bir problemi bir dizi seçimle çözer ve her adımda o an en iyi görünen seçeneği, yani yerel olarak en iyi seçimi alır. Verilen bir kararı bir daha asla gözden geçirmez. Bu, açgözlü algoritmaları yazması basit ve genellikle çok hızlı yapar; ancak yalnızca doğru yapıya sahip problemlerde en iyi genel cevabı bulurlar.
Açgözlü yaklaşımın çalışması, bir problemin iki özelliğe sahip olmasıyla garanti edilir: açgözlü seçim özelliği, yani yerel olarak en iyi seçimin her zaman bir optimal çözümün parçası olabilmesi; ve optimal alt yapı, yani bu seçimden sonra geriye kalanın aynı problemin daha küçük bir sürümü olması. Birinci özelliği kanıtlamak zor kısımdır ve çoğu zaman bir değişim argümanıyla (exchange argument) yapılır; bu, herhangi bir optimal çözümün daha kötüye gitmeden açgözlü seçimi içerecek biçimde değiştirilebileceğini gösterir. Birçok açgözlü algoritma girdisini sıralayarak başlar; bu yüzden genellikle O(n log n) sürede çalışırlar.
Mümkün olan en az madeni parayla para üstü vermek klasik örnektir: 25, 10, 5 ve 1 sentlik madeni paralarla, sığan en büyük parayı vermeye devam etmek en iyi cevabı verir. Bilinen açgözlü algoritmalar arasında Dijkstra'nın en kısa yol algoritması, minimum kapsayan ağaçlar için Prim ve Kruskal algoritmaları, veri sıkıştırma için Huffman kodlaması ve her zaman en erken biten toplantıyı seçerek bir odaya en çok toplantıyı sığdıran aralık zamanlaması (interval scheduling) bulunur. Bir problem tam olarak çözülemeyecek kadar zor olduğunda açgözlü yöntemler, her zaman en iyisi olmasa da iyi bir cevap veren hızlı sezgisel yöntemler olarak da işe yarar.
Açgözlü algoritmalar, ikisi de optimal alt yapılı problemler üzerinde çalıştığı için sıklıkla dinamik programlamayla karıştırılır. Açgözlü algoritma her adımda tek bir seçime bağlanırken dinamik programlama her seçimi değerlendirir ve alt problemlerin saklanmış sonuçlarını birleştirir; bu daha yavaştır ama açgözlülüğün başarısız olduğu durumlarda doğrudur. Madeni para örneği farkı gösterir: 1, 3 ve 4 değerli paralarla 6 oluşturmak açgözlü yöntemle 4 + 1 + 1, yani üç para verir; dinamik programlama ise yalnızca iki para olan 3 + 3'ü bulur.
Önemli noktalar
- Açgözlü algoritma her zaman o an en iyi görünen seçimi alır ve asla geri dönmez.
- Yalnızca problem açgözlü seçim özelliğine ve optimal alt yapıya sahip olduğunda optimaldir.
- Örnekleri arasında Dijkstra algoritması, Huffman kodlaması ve Kruskal ile Prim'in minimum kapsayan ağaç algoritmaları bulunur.
- Açgözlü algoritmalar genellikle hızlıdır; girdiyi önce sıraladıkları için çoğu kez O(n log n) sürer.
- Dinamik programlama tüm seçimleri değerlendirir, bu yüzden açgözlü seçimlerin başarısız olduğu problemleri çözer.
Örnek
def max_meetings(meetings):
# Greedy choice: always take the meeting that ends earliest
chosen, free_at = [], 0
for start, end in sorted(meetings, key=lambda m: m[1]): # O(n log n)
if start >= free_at: # it fits after the last chosen meeting
chosen.append((start, end))
free_at = end
return chosen
meetings = [(9, 12), (9, 10), (10, 11), (11, 13), (12, 14), (13, 15)]
print(max_meetings(meetings)) # [(9, 10), (10, 11), (11, 13), (13, 15)]Sık sorulan sorular
Açgözlü algoritma ne zaman optimal cevabı verir?
Problem açgözlü seçim özelliğine, yani yerel olarak en iyi bir seçimin en iyi genel çözümü asla dışarıda bırakmadığı bir yapıya ve optimal alt yapıya sahip olduğunda. Aralık zamanlaması, minimum kapsayan ağaçlar ve Huffman kodlaması kanıtlanmış durumlardır; diğer birçok problemde açgözlü yöntem yalnızca bir yaklaşık çözüm verir.
Açgözlü algoritma ile dinamik programlama arasındaki fark nedir?
Açgözlü algoritma, o an en iyi görünene göre adım başına geri döndürülemez tek bir seçim yapar. Dinamik programlama ise alt problemlerin saklanmış cevaplarını kullanarak tüm seçimleri değerlendirir; bu daha çok zaman ve bellek harcar ama açgözlü seçimlerin başarısız olduğu yerde optimumu bulur.
Dijkstra algoritması açgözlü müdür?
Evet. Her adımda bilinen en küçük uzaklıklı ziyaret edilmemiş düğümü kesinleştirir; bu açgözlü bir seçimdir ve hiçbir kenar ağırlığı negatif olmadığı sürece doğru olduğu kanıtlanmıştır.
İlgili sayfalar
- Dinamik ProgramlamaVeri Yapıları, s. 13Dinamik programlama, bir problemi çakışan alt problemlere bölüp her cevabı saklayarak hiçbirini iki kez çözmeden problemi çözme tekniğidir.
- Dijkstra AlgoritmasıVeri Yapıları, s. 12Dijkstra algoritması, tüm kenar ağırlıkları sıfır ya da pozitifken bir başlangıç düğümünden diğer tüm düğümlere en kısa yolları bulan çizge algoritmasıdır.
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
- Sıralama AlgoritmasıVeri Yapıları, s. 30Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
- Geri İzlemeVeri Yapıları, s. 16Geri izleme, çözümü her seferinde bir seçimle kuran ve çıkmaza girdiğinde son seçimi geri alarak başka bir seçenek deneyen bir arama tekniğidir.
- Öncelik KuyruğuVeri Yapıları, s. 27Öncelik kuyruğu, her öğenin bir önceliği olduğu ve ne zaman eklendiğine bakılmaksızın en yüksek öncelikli öğenin her zaman önce çıkarıldığı bir koleksiyondur.
- Union-FindVeri Yapıları, s. 35Union-find (ayrık küme birleşimi), öğe gruplarını izleyip birleştiren ve iki öğenin bağlı olup olmadığını neredeyse anında söyleyen veri yapısıdır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin