Açgözlü algoritma nedir?

0 beğenilme 0 beğenilmeme
470 kez görüntülendi

Bir algoritmanın "açgözlü" (greedy) olması ne demek? 

1, Kasım, 2017 Teorik Bilgisayar Bilimi kategorisinde Salih Durhan (1,287 puan) tarafından  soruldu

1 cevap

0 beğenilme 0 beğenilmeme

Tarihin geç olmasına karşın yeni görenler için hızlı bir cevap

Açgözlü algoritma 

iteratif bir algoritmanın her iterasyonda en iyi sonucu seçerek devam etmesidir.

örnek bir ağaç üzerindeki en büyük elemanı BFS ile aradığınızı düşünün

- 45
- -├13
- -│ ├28
- -│ `34
- -`25
- - ├1
- - `2

Eğer bu ağacı greedy yaklaşımı ile ararsanız sonuç 2 çıkacaktır.

çünkü greedy önce roottan başlayacak
45
sonra rootun çocukları arasından en büyüğü seçecek
25
en sonunda da onun çocukları arasından en büyüğünü seçecektir
2

ve sonuç bariz şekilde hatalı çıkacaktır.
ki buna da greedy algoritmaların lokal maximuma/minimuma takılması denir.
greedy sezgisel bir yaklaşımdır ve ancak veri setiniz tamamını arayamayacağınız büyüklükteyse hızlı sonuç almak için kullanılabilecek diğer sezgisellerden biridir. Ancak oldukça ilkeldir bilinmelidir mecbur değilseniz veya gerçekten faydalı olduğu bir nokta göremezseniz uygulanması iyi sonuç vermez 

birde eğer veri setiniz sıralıysa tabiki uygulamanız çok iyi sonuç verecektir.


15, Nisan, 15 aernile (20 puan) tarafından  cevaplandı
...