Greedy Algorithm (Açgözlü Algoritma)

#algoritma #optimizasyon #karar-agaci #arama

Açgözlü algoritma, her adımda yerel olarak en iyi seçimi yaparak global bir hedefe ulaşmaya çalışan, geri dönüş yapmayan bir problem çözme yaklaşımıdır.

Açgözlü algoritma (Greedy Algorithm), bir problemi çözerken her adımda o anki duruma göre yerel olarak en iyi görünen kararı veren ve bu kararları geri almadan ilerleyen bir algoritma tasarım paradigmasıdır. "Açgözlü" adı, algoritmanın şu anın en iyi seçimini yaparken gelecekteki sonuçları göz ardı etmesinden kaynaklanmaktadır. Temel mantığı şudur: Her karar noktasında mevcut bilgilerle alınabilecek en iyi seçimi yap, bu kararı kesin kabul et ve bir sonraki adıma geç. Geri dönüş (backtracking) ya da yeniden değerlendirme yapılmaz. Bu özellik açgözlü algoritmaları genellikle çok hızlı kılar, ancak her zaman global optimum sonucu garantilemez. Açgözlü algoritmaların doğru çalışabilmesi için iki matematiksel koşulun sağlanması gerekir: Açgözlü Seçim Özelliği (Greedy Choice Property) — her adımdaki yerel optimal seçim, global optimum çözümün bir parçasıdır; ve Optimal Alt Yapı (Optimal Substructure) — problemin optimal çözümü, alt problemlerin optimal çözümlerini içerir. Bu koşullar sağlandığında açgözlü algoritmalar kusursuz çalışır: Kruskal ve Prim algoritmaları ile Minimum Yayılan Ağaç (MST) bulma, Dijkstra algoritması ile en kısa yol hesaplama, Huffman kodlaması ile kayıpsız veri sıkıştırma ve çizelgeleme problemleri bunların en bilinen örnekleridir. Yapay zeka ve makine öğrenmesinde açgözlü yaklaşım yaygındır. Karar ağaçlarında her düğüm için en bilgi kazandıran özelliği seçme, greedy decoding ile büyük dil modellerinde her adımda en yüksek olasılıklı token üretme ve nöral mimari arama süreçlerinde açgözlü stratejiler kullanılır. Özellik seçimi (feature selection) aşamasında da açgözlü ileri seçim (greedy forward selection) sık tercih edilir. Açgözlü algoritmaların dezavantajı, yerel optimuma takılıp global optimumu kaçırabilmesidir. Örneğin gezgin satıcı probleminde açgözlü yaklaşım iyi ama çoğunlukla optimal olmayan sonuçlar verir. Bu sınırlamayı aşmak için simüle tavlama (Simulated Annealing), genetik algoritmalar veya dinamik programlama tercih edilebilir. Beam search ise açgözlü decoding ile kapsamlı arama arasında bir denge kurar.

Açgözlü Algoritma Nasıl Çalışır?

Algoritma, problem çözümünü adım adım inşa eder. Her adımda mevcut seçenekler arasından yerel olarak en iyi olanı seçer ve bu seçimi kalıcı kabul eder. Geri dönüş yapılmaz; önceki kararlar sorgulanmaz. Bu 'şimdinin en iyisini al' prensibi, algoritmanın hem gücünü hem de sınırını belirler. Sonuç genellikle O(n log n) veya daha iyi bir karmaşıklıkla elde edilir.

Doğru Çalışması İçin Gereken Koşullar

Açgözlü algoritmanın global optimumu garanti edebilmesi için iki temel koşulun sağlanması gerekir: (1) Açgözlü Seçim Özelliği — her adımda yerel optimal seçim, nihai optimal çözümün bir parçasıdır; (2) Optimal Alt Yapı — problemin optimal çözümü, daha küçük alt problemlerin optimal çözümlerinden oluşur. Bu koşullar sağlanmazsa algoritma yaklaşık sonuçlar üretir.

Klasik Uygulamalar

Huffman kodlaması karakterlere frekanslarına göre değişken uzunluklu kod atar ve sıkıştırmayı optimize eder. Kruskal algoritması her adımda en düşük ağırlıklı kenarı seçerek minimum yayılan ağacı bulur. Prim algoritması mevcut ağacı en yakın komşuyla genişleterek aynı sonuca ulaşır. Dijkstra algoritması her adımda en kısa geçici yolu kesinleştirerek tek kaynaklı kısa yol problemini çözer. Çizelgeleme problemlerinde de işleri son teslim tarihine göre sıralayan açgözlü kararlar yaygındır.

Yapay Zeka ve Makine Öğrenmesindeki Rolü

Büyük dil modellerinde metin üretme sırasında kullanılan greedy decoding, her adımda en yüksek olasılıklı token'ı seçer; bu hızlı ama tekrara düşebilen çıktılar üretebilir. Karar ağaçları (CART, ID3) her düğümde bilgi kazancı en yüksek özelliği açgözlü seçer. Beam search ise birden fazla en iyi adayı paralel takip ederek saf açgözlü decoding'e göre daha iyi sonuçlar elde eder. Özellik seçimi süreçlerinde greedy forward ve backward selection yaygın kullanılır.

Sınırlamalar ve Alternatifler

Açgözlü algoritmalar yerel optimuma takılabilir; gezgin satıcı (TSP) gibi NP-zor problemlerde genellikle suboptimal çözümler üretir. Bu durumlarda dinamik programlama (garanti) veya sezgisel yöntemler (simüle tavlama, genetik algoritmalar, karınca kolonisi optimizasyonu) tercih edilir. Hangi yöntemi seçeceğiniz, çözüm kalitesi ile hesaplama maliyeti arasındaki dengeye bağlıdır.

Sık Sorulan Sorular

  • check_circle Açgözlü algoritma her zaman en iyi sonucu verir mi? Hayır. Yalnızca 'açgözlü seçim özelliği' ve 'optimal alt yapı' koşullarını sağlayan problemlerde global optimum garanti edilir. Diğer durumlarda yerel optimuma takılabilir.
  • check_circle Dinamik programlama ile farkı nedir? Dinamik programlama tüm alt problem çözümlerini saklayarak kesin optimum bulur; daha fazla bellek kullanır. Açgözlü algoritma kararları geri almadan ilerler; daha hızlı ama bazen suboptimal.
  • check_circle Greedy decoding nedir? Büyük dil modellerinde her token üretim adımında en yüksek olasılıklı kelimeyi seçme yöntemidir. Hızlıdır ancak çeşitlilik azalabilir; beam search veya sampling yöntemleri alternatif olarak kullanılır.
  • check_circle Beam search açgözlü bir algoritma mıdır? Beam search, açgözlü decoding ile tam arama arasında bir uzlaşıdır. Her adımda en iyi k aday (beam width) takip edilir. k=1 olduğunda saf greedy decoding'e eşdeğerdir.