Açgözlü Algoritma

Açgözlü algoritma (greedy algorithm), her adımda mevcut bilgiyle en iyi görünen yerel kararı veren ve önceki kararlara dönmeyen yapıcı algoritma sınıfıdır. Algoritma temeli klasik çağ kombinatorik problemlerine kadar uzanır (Kruskal 1956 ve Prim 1957 minimum yayılan ağaç; Dijkstra 1959 en kısa yol). Açgözlü yöntemin doğru çözümü ne zaman vereceği matroid teorisi ile karakterize edilir: Rado-Edmonds teoremi (Edmonds 1971), bir alt-küme sisteminin açgözlü algoritma altında tüm ağırlık fonksiyonları için optimal olmasının ancak ve ancak matroid yapısı olduğunu söyler. Bu nedenle minimum yayılan ağaç (Kruskal/Prim), Huffman kodlaması (Huffman 1952), tek-makineli weighted-completion-time (SPT/EDD kuralları, Smith 1956) gibi problemler açgözlüyle optimal çözülür. Buna karşılık knapsack, bin packing, set covering, VRP gibi problemlerde açgözlü çözüm optimumun belirli oranlarında sınırlandırılabilir (örneğin set covering için Chvátal 1979 ln(n)+1 yaklaşımı) ancak global olarak optimum değildir. Açgözlü algoritmalar pratikte üç rol üstlenir: (1) hızlı yapıcı sezgisel (warm-start), (2) approximation algoritma garanti ailesi, (3) yerel arama veya metasezgisel için başlangıç çözüm. Sezgisel olarak açgözlü TSP (en yakın komşu), VRP'de Clarke-Wright tasarruf yöntemi (1964) ve scheduling'de LPT/SPT açgözlü ailesinin endüstri standardı örnekleridir. Cormen, Leiserson, Rivest ve Stein (CLRS, 2009) bölüm 16 referans tartışmadır.