Açgözlü Algoritmalar Nedir?
Açgözlü algoritmalar, bir problemi adım adım çözerken her aşamada o an için en iyi görünen seçeneği seçmeye dayanan bir optimizasyon stratejisidir. Bu yaklaşım, her adımda yapılan yerel optimum seçimlerin, genel olarak en iyi çözümü vereceği varsayımına dayanır.
Açgözlü algoritmalar, her adımda o anki en iyi seçeneği belirleyerek ilerleyen ve genellikle global optimum çözümü bulmaya çalışan algoritma tasarlama tekniğidir.
Adım adım çözümlü örnekler
Deyimsel Para Üstü Problemi: Belirli bir tutarı en az sayıda madeni parayla nasıl ödersiniz?
1. En büyük değerli madeni paradan başla. 2. Kalan tutar için bu madeni paradan mümkün olduğunca fazla kullan. 3. Gerekirse daha küçük değerli madeni paralara geç ve adımları tekrarla. 4. Toplam tutar sıfırlanana kadar devam et.
Minimum Kapsayan Ağaç (MST) Problemi (Prim's Algoritması): Birbirine bağlı bir grup düğüm arasındaki maliyeti en aza indiren bir ağaç nasıl oluşturulur?
1. Rastgele bir düğüm seç ve bu düğümü içeren bir ağaç oluştur. 2. Mevcut ağaca en az maliyetle bağlanabilecek kenarı ve düğümü bul. 3. Bu kenarı ve düğümü ağaca ekle. 4. Tüm düğümler ağaca dahil olana kadar 2. ve 3. adımları tekrarla.
Aktivite Seçim Problemi: Verilen bir dizi aktivite arasından, çakışmayan ve maksimum sayıda aktiviteyi içeren bir alt küme nasıl seçilir?
1. Aktiviteleri bitiş zamanlarına göre sırala. 2. İlk aktiviteyi seç. 3. Seçilen aktivite ile çakışmayan, en erken biten bir sonraki aktiviteyi seç. 4. Tüm aktiviteler gözden geçirilene kadar 3. adımı tekrarla.
Bilgi kartları
Mini test
S1.Aşağıdakilerden hangisi açgözlü algoritmaların temel özelliğidir?
S2.Açgözlü algoritmalar hangi tür problemler için genellikle uygundur?
S3.Açgözlü bir algoritmanın her zaman optimal çözümü garanti etmediği durumlar için verilebilecek bir örnek nedir?
Sık yapılan hatalar
Açgözlü algoritmalar her zaman en iyi çözümü bulur. — Doğrusu: Açgözlü algoritmalar, yerel optimum seçimlerin global optimumu garanti edeceği varsayımına dayanır ancak bu her zaman doğru değildir.
Açgözlü algoritmalar, dinamik programlama ile aynıdır. — Doğrusu: Dinamik programlama, alt problemlerin çözümlerini saklayarak ve tekrar kullanarak optimal çözümü bulurken, açgözlü algoritmalar her adımda anlık en iyi kararı verir.
Sıkça sorulan sorular
Açgözlü bir algoritma ne zaman kullanılır?
Açgözlü algoritmalar, bir problemi çözmek için her adımda yerel olarak en iyi seçeneğin seçilebileceği ve bu seçimlerin genel olarak optimal bir sonuca yol açacağı durumlarda kullanılır. Ayrıca, problemin yapısı gereği geri adım atmadan ilerlemenin mümkün olduğu durumlarda da tercih edilir.
Açgözlü algoritmaların dinamik programlamadan farkı nedir?
Dinamik programlama, alt problemlerin çözümlerini saklayarak ve tekrar kullanarak optimal çözümü bulur; tüm olası alt yapılar dikkate alınır. Açgözlü algoritmalar ise her adımda sadece o anki en iyi görünen seçeneği seçer ve bu karardan geri dönmez. Bu nedenle açgözlü algoritmalar genellikle daha hızlıdır ancak her zaman optimal çözümü garanti etmezler.
Açgözlü algoritmaların en bilinen örnekleri nelerdir?
Deyimsel Para Üstü Problemi, Minimum Kapsayan Ağaç (Prim ve Kruskal algoritmaları), Huffman Kodlaması, Aktivite Seçim Problemi ve Graf Boyama gibi problemler açgözlü algoritmalarla çözülebilen örneklere dahildir.