Açgözlü Yaklaşımı (Greedy Approach)
Yazan: Şadi Evren ŞEKER
Algoritma üretme yöntemlerinden birisi olan açgözlü yaklaşımına göre mümkün olan ve sonuca en yakın olan seçim yapılır. Yani basitçe bir seçim yapılması gerektiğinde sonuca en çok yaklaştıracak olan seçimin yapılmasını önerir. Ancak mâlum olduğu üzere bu seçim her zaman için en iyi seçim değildir.
Örneğin para üzeri verilmesi (coin exchange problem) için açgözlü yaklaşımının kullanılmasını düşünelim. Bu problemde bir satıcı kendisinden alışveriş yapan kişiye para üzeri vermektedir. Ödenmesi gereken miktar bu örnekte 24 olsun ve para birimlerimiz 20, 19, 5, 1 olsun. (yani para birimi olarak bu para birimleri bulunuyor)
açgözlü yaklaşımına göre satıcı 24’ü tamamlamak için elindeki para birimlerinden sonuca en çok yaklaştıran 20lik birimi seçecektir. Daha sonra geriye kalan boşluğu (24-20=4) doldurmak için elindeki tek imkan olan 4 tane 1lik birimle dolduracaktır ve toplamda 5 adet bozuk parayı müşteriye geri verecektir. Oysaki aynı problem bir 19luk bir de 5lik bozuk paralar ile çözülerek 2 bozuk para vermek mümkün olabilirdi.
toplamda en kısa mesafeyi bulamayabileceği için optimal değildir.
hedefi bulamadan sonsuza kadar araştırma yapabileceği için complete değildir.
mrb Hocam
Greedy yaklaşımını Kullanarak En Optimal O(nlogn) algoritması nasıl kurabilirim
Algoritma performansı (ki bahsettiğiniz büyük O gösterimidir) problem bağımlı çıkarılır. Yani ortada bir problem varsa bu problemin çözümünde geliştirilen algoritmanın performansından bahsedebiliriz. Aç gözlü yaklaşımı (greedy approach) ise genel bir yaklaşım ismidir ve performansı, uygulandığı problem ve ortama göre değişebilir. Bu yüzden, belki de probleminizi anlatmanız durumunda istediğiniz başarıda bir performans elde edilip edilmeyeceğine bakabiliriz.
Ancak genel bir soru sorduğunuz için genel bir cevap, logaritmik performansların ancak problemin tanımlı olduğu kümeyi bölerek elde edildiğini söyleyerek verilebilir. Örneğin O(nlgn) performansı, birleştirme sıralamasında (merge sort) bulunmaktadır ve bu algoritma problemi iki parçaya böldüğü için logaritmik sonuç vermiştir.
Başarılar