Bu eğitimde, Açgözlü Algoritmanın ne olduğunu öğreneceksiniz. Ayrıca, açgözlü bir yaklaşımın bir örneğini bulacaksınız.
Açgözlü bir algoritma, o anda mevcut olan en iyi seçeneği seçerek, getireceği sonuç hakkında endişelenmeden bir sorunu çözmeye yönelik bir yaklaşımdır. Başka bir deyişle, yerel olarak en iyi seçimler, küresel olarak en iyi sonuçları üretmeyi amaçlamaktadır.
Bu algoritma tüm problemler için en iyi seçenek olmayabilir. Bazı durumlarda yanlış sonuçlar verebilir.
Bu algoritma, verilen kararı tersine çevirmek için asla geri dönmez. Bu algoritma, yukarıdan aşağıya bir yaklaşımla çalışır.
Bu algoritmanın temel avantajı:
- Algoritmanın tanımlanması daha kolaydır .
- Bu algoritma diğer algoritmalardan daha iyi performans gösterebilir (ancak her durumda değil).
Makul çözüm
Soruna en uygun çözümü sağlayan, uygulanabilir bir çözümdür.
Açgözlü algoritma
- Başlangıç olarak, çözüm seti (cevapları içeren) boştur.
- Her adımda, çözüm setine bir öğe eklenir.
- Çözüm seti uygunsa, mevcut öğe saklanır.
- Aksi takdirde, öğe reddedilir ve bir daha asla dikkate alınmaz.
Örnek - Açgözlü Yaklaşım
Sorun: Mümkün olan en az sayıda jeton kullanarak bir miktarda değişiklik yapmanız gerekiyor. Miktar: 28 $ Mevcut paralar: 5 $ jeton $ 2 jeton $ 1 jeton
Çözüm:
- Boş bir çözüm kümesi = () oluşturun.
- madeni para = (5, 2, 1)
- toplam = 0
- Toplam ≠ 28 iken, aşağıdakileri yapın.
- Madeni paralardan, + C <28 toplamı olacak şekilde bir C jetonu seçin.
- C + toplamı> 28 ise, çözüm yok döndür.
- Aksi takdirde, toplam = toplam + C.
- Çözüm kümesine C ekleyin.
İlk 5 iterasyona kadar, çözüm seti 5 $ 5 jeton içerir. Bundan sonra 1 $ 2 jeton ve son olarak 1 $ 1 jeton alıyoruz.
Açgözlü Algoritma Uygulamaları
- Seçim Sıralaması
- Sırt Çantası Sorunu
- Az yer kaplayan ağaç
- Tek Kaynaklı En Kısa Yol Problemi
- İş Planlama Problemi
- Prim'in Minimal Kapsayan Ağaç Algoritması
- Kruskal'ın Minimal Kapsayan Ağaç Algoritması
- Dijkstra'nın Minimal Kapsayan Ağaç Algoritması
- Huffman Kodlama
- Ford-Fulkerson Algoritması
