Açgözlü Algoritmalar
Açgözlü algoritmalar, mevcut adımda en iyi görünen seçimi tekrarlayarak bir çözümü artımlı olarak inşa etmekte ve bu tür yerel olarak en uygun seçimlerin kanıtlanabilir şekilde küresel olarak en uygun bir çözüme yol açtığı durumlarda doğru kabul edilmektedir.
Tanım
Açgözlü bir algoritma, her biri belirli bir yerel kriteri optimize etmek üzere seçilen ve önceki seçimlere asla geri dönülmeyen bir dizi seçim aracılığıyla bir çözüm inşa etmektedir; yalnızca yerel olarak en uygun seçimlerin küresel olarak en uygun bir sonuç verdiği durumlarda doğru kabul edilmektedir.
Kapsam
Bu konu, açgözlü paradigmayı; bunu haklı çıkaran açgözlü seçim özelliğini ve optimal alt yapıyı; standart ispat tekniklerini (değişim argümanları ve matris çerçevesi); ve Huffman kodlaması, minimum kapsayan ağaçlar (Kruskal ve Prim), Dijkstra'nın en kısa yolları ve aralık zamanlaması gibi kanonik açgözlü algoritmaları kapsamaktadır. Ayrıca, açgözlü stratejilerin kesin yöntemler yerine yalnızca yaklaşık sezgisel yöntemler olarak hizmet ettiği durumları da ele almaktadır.
Temel sorular
- Açgözlü seçim özelliği nedir ve belirli bir problem için nasıl ispatlanmaktadır?
- Bir değişim argümanı, açgözlü bir seçimin güvenli olduğunu nasıl göstermektedir?
- Hangi problemler, açgözlü optimalliği garanti eden matris yapısına sahiptir?
- Açgözlü bir yöntem, kesin bir algoritma yerine yalnızca bir yaklaşım ne zaman olmaktadır?
- Açgözlü yöntem, aynı problem için dinamik programlama ile nasıl karşılaştırılmaktadır?
Anahtar kavramlar
- açgözlü seçim özelliği
- optimal alt yapı
- değişim argümanı
- matrisler
- Huffman kodlaması
- minimum kapsayan ağaç
- aralık zamanlaması
- kesirli sırt çantası problemi
Temel kuramlar
- Açgözlü seçim özelliği ve değişim argümanları
- Bir problem, küresel olarak en uygun bir çözümün optimallikten ödün vermeden açgözlü ilk seçimle uyumlu olacak şekilde her zaman değiştirilebildiği durumlarda açgözlü bir çözümü kabul etmektedir; değişim (veya 'açgözlü önde kalır') argümanları bunu resmileştirmektedir.
- Matrisler ve açgözlü optimallik
- Olası çözümler, ağırlıklı bir matrisin bağımsız kümelerini oluşturduğunda, açgözlü algoritma her zaman maksimum ağırlıklı bağımsız bir küme bulmaktadır; bu durum, Kruskal'ın minimum kapsayan ağaç algoritmasının optimalliği gibi sonuçları birleştirmektedir.
Klinik önem
Açgözlü algoritmalar, yaygın olarak kullanılan sistemleri yönlendirmektedir: veri sıkıştırma formatlarında Huffman kodlaması, ağ tasarımında minimum kapsayan ağaç algoritmaları, yönlendirme ve navigasyonda Dijkstra algoritması ve işletim sistemleri ile kaynak tahsisinde açgözlü zamanlama ve küme kapsama sezgiselleri.
Tarihçe
Açgözlü akıl yürütme, Kruskal'ın (1956) ve Prim'in (1957) minimum kapsayan ağaç algoritmaları, Huffman'ın (1952) optimal önek kodları ve Dijkstra'nın (1959) en kısa yol algoritması gibi klasik sonuçlarda görülmektedir. Açgözlü yöntemlerin ne zaman başarılı olduğunu açıklayan matris teorik açıklama, 1960'lı ve 1970'li yıllarda Edmonds ve diğerleri tarafından geliştirilmiştir.
Öne çıkan isimler
- David A. Huffman
- Joseph Kruskal
- Robert Prim
- Edsger W. Dijkstra
İlgili konular
Temel eserler
- dijkstra1959
- cormen2009
Sıkça sorulan sorular
- Açgözlü yöntem, kesirli sırt çantası problemi için neden işe yararken 0/1 sırt çantası problemi için yaramamaktadır?
- Kesirli sırt çantası probleminde, öğeler bölünebilmektedir, bu nedenle ağırlık başına en yüksek değere sahip öğeyi ilk almak her zaman güvenli ve kanıtlanabilir şekilde optimaldir. 0/1 sırt çantası probleminde ise öğeler bölünemezdir, açgözlü seçim daha iyi bir kombinasyonu engelleyebilmektedir ve kesin bir optimum için dinamik programlama gerekmektedir.
- Açgözlü bir algoritmanın doğru olduğu nasıl ispatlanmaktadır?
- İki standart teknik, herhangi bir optimal çözümü kötüleştirmeden açgözlü çözüme dönüştüren değişim argümanı ve açgözlü kısmi çözümün her adımda diğer herhangi bir çözümden en az o kadar iyi olduğunu gösteren 'açgözlü önde kalır' argümanıdır. Matris teorisi, genel bir yeterli koşul sağlamaktadır.