Her adımda yerel olarak en iyi seçimi yapan algoritma türü.
Temel Özellikler
- Açgözlü Seçim Özelliği: Yerel optimal seçim global optimuma götürür
- Optimal Alt Yapı: Problemin optimal çözümü alt problemlerin optimal çözümlerini içerir
Çalışma Prensibi
- Mevcut durumda en iyi seçimi yap
- Bu seçimi geri almadan devam et
- Gelecekteki sonuçları düşünme
- Problem çözülene kadar tekrarla
Örnek: Madeni Para Problemi
63 kuruş için 1, 5, 10, 25 kuruşluk paralarla ödeme:
- 25 kuruş kullan → Kalan: 38
- 25 kuruş kullan → Kalan: 13
- 10 kuruş kullan → Kalan: 3
- 1 kuruş kullan → Kalan: 2
- 1 kuruş kullan → Kalan: 1
- 1 kuruş kullan → Kalan: 0
Toplam: 6 madeni para
Kullanım Alanları
- Minimum Kapsayan Ağaç (Prim, Kruskal)
- En kısa yol (Dijkstra)
- Etkinlik seçimi problemi
- Huffman kodlaması
- Kesirli sırt çantası
Sınırlamalar
- Her zaman optimal çözüm vermez
- Problem yapısına bağımlıdır
- Açgözlü seçim özelliği gereklidir
Avantajları
- Basit ve anlaşılır
- Genellikle hızlı
- Bellek kullanımı az