şükela:  tümü | bugün
  • greedy algorihm ler dynamic problem lerin alt kumeleridir. dynamic problemler tum olasi alt kumeleri gezip (tabi ki bulduklari sonuclardan da yararlanarak son ana kadar dogru sonucu bulmamis olabilirler.) optimal cozumu bulurken, greedy algorithmlar derinlemesine inmeden sadece o an icin bir adim atar,daha sonra onu kullanarak digerlerini. dikkat edilmesi gereken nokta greedy algoritmalar daha guclu ispatlar gerektirecektir, her zaman yemez.
  • bazi insanlarin hardware duzeyinde sahip olduklari algoritma. ne ogrenirse ogrensin, degismeyen insanlar vardir bu konuda. iki adim sonrasini dusunmez mesela, bildigin mal. karar noktasinda alternatiflerden hangisi gozune guzel gozukurse onu secer. ikinci adiminda aglamaya baslar ama yine alternatiflerden hangisi daha bir iyi gozukuyorsa o an icin, gider yine secer bok varmis gibi. velhasil boyle boyle dolasir. kimisi vardir aradigini bulur, durulur. kimisi aradigini omrubillah bulamaz.

    hayatin icinden orneklerle, bir algoritmamizi aciklamis bulunuyoruz. esen kalin...
  • exponential zamanda cozulebilen bir problemi optimize etmek icin genelde icgudusel olarak ilk basvurulan yontemlerden biridir, ancak cogu zaman yanilticidir. anlik en iyi cozumleri secmek, daha sonralari karsiniza cikacak daha iyi alt cozumleri es gecmenize sebep olabilir. o yuzden tasarladiginiz greedy algoritmayi matematiksel olarak dogrulugunu kanitlamadan kullanmayin. cogu zaman dynamic programming cok daha iyi bir yoldur optimizasyon icin.
  • bunun ilişkilerde uygulanışı şöyle olabilir zannedersem; etrafımızda çok güzel/yakışıklı, hali vakti yerinde, muhabbeti hoş, vs. insanlar var. bunlar arasından istediğimiz kriterlere/kafamızdaki profile uyan, her açıdan en iyi olduğunu düşündüğümüz birisini seçiyoruz ve onunla hayat boyu mutlu olacağımızı düşünüyoruz. ilişkiyi başlatıyoruz, iyi hoş vakitler geçiyor ama belli bir süre sonra anlıyoruz ki bir problem var; yürümüyor, rahatsız ediyor bazı şeyler. hani o dışarıdan bakınca sizi cezbeden kişi aslında hayat geçirilecek biri değil. yani karar verirken bir şeyleri hesaba katmayı unutmuşuz; açgözlü davranmışız aslında!

    tabi beşer bu, şaşıyor da, ama şaşmasına rağmen aynı hatayı yapmaya devam ediyor, hatalarından çıkardığı derse geç kalıyor. önceki ilişkinin bittiği noktada yine aynı kriterleri göz önüne alarak bir ilişkiye daha başlıyor. yine aynı umutlarla; hayat boyu...

    her defasında yanıldığını anlıyor, seçim yaparken kriterleri yanlış belirliyor. daha doğrusu onu ilk görüşte kendine aşık ettiren kişi aslında hep yanlış kişi ama hep en yakın görünen de o mamafih*.

    aslında başlarda bazı özelliklerden ve güzelliklerden ödün verse çok mutlu olacak ama işte gözü doymuyor öyle olunca da; bildiğin açgözlü!

    algoritma da bu bakış açısına ve ileriyi görememeye dayanıyor. rastgele bir noktadan başlayıp, her defasında en yakına hareket ederek, en kısa turu oluşturacağına inanıyor (algoritmanın esas amacı en kısa/en az maliyetli güzergahı belirlemek olduğu için).
  • açgözlü bir algoritmadir kendileri. her ortamda genel gecer bir cozum bulma umuduyla her aşamada yerel olarak en uygun seçeneği seçmek için sezgisel çözme bulgusunu takip eden algoritmik bir paradigmadır. birçok sorunda, açgözlü bir strateji genel olarak en iyi çözümü üretmez, ancak makul zamanlarda (hangi zaman lan bu?) global optimal çözümün yereline en uygun çözümleri üretebilir.

    risk alan bir algoritmada denebilir. mesela bir yarismaya katildiniz, sizi bir alisveris merkezinin icine biraktilar, 500 altin verdiler. dediler ki bu parayla bir insani giydirebilecek kiyafetler alin getirin. corap, pantalon, gomlek, ayakkabi vs. eger siz risk alip acgozlu bir algoritma izlerseniz onunuze gelen ilk magazaya dalip kiyafetleri bulma derdine dusersiniz.

    wikipedia diyor ki;

    açgözlü algoritmaların genelde beş bileşeni vardır:

    1- bir çözümün oluşturulduğu bir aday kümesi (kiyafet magazalari)
    2- çözüme eklenecek en iyi adayı seçen bir seçim işlevi (mesela magazanin adina bakip, ne tarz bir magaza oldugunu kestirmek)
    3- bir aday, bir çözüme katkıda bulunmak için kullanılabilir olup olmadığını belirlemek için kullanılan bir fizibilite işlevi (diyelim kiyafet magazasi olup bebek magazasi ise girme, cunku burdaki kiyafetler ise yaramaz gibi)
    4- bir çözüm veya kısmi bir çözüm için bir değer atayan nesnel bir işlev (girdiniz bir magazaya, basladiniz kiyafetleri karistirmaya, o da ne? elinize petibor biskuvisi gelmis, megersem migrosa girmissiniz ama yanlis departmandasiniz)
    5- komple bir çözüm bulduğumuzu gösterecek bir çözüm işlevi (alisveris sepetinize bir baktiniz tepeden tirnaga ne eksik varsa almissiniz, islem tamam!)

    acgozlu algoritmayi tatmin eden kosullardan biri sudur: "problemin optimal bir çözümü, alt problemlere en uygun çözümleri içeriyorsa, bir sorun en iyi altyapıyı sergiler."

    yani girdiginiz magazalardan biri migros, lan burda coraptan, pentelona (selam rafet naber?) herseyi buldugunuz, e o zaman bu benim icin en iyi yerdir der ve isi bitirirsiniz. halbuki bunun yerine, atiyorum lc waikiki'ye girseydiniz, migros icindeki departmanlari dolasmak yerine direk kiyafetlere odaklanacaktiniz.

    duruma gore kullaniciya istedigini verir, geri kalan hersey icin mastercard.
  • her adimda o an icin en iyi cozumu bulan algoritmalara denir. mesela a noktasindan b noktasina giderken her sokagin sonunda haritadan bakarak en kisa sokagi seciyorsaniz aslinda bir nevi greedy algoritma uyguluyorsunuz demektir.
  • anlık çözümler insan hayatının vazgeçilmezleridir.
    ihtiyaç hasıl olduğunda eyleme geçilir ve ilerisi düşünülmez.
    örnekle açıklayalım: su içmek canlılığın gereğidir. suyun niteliği dikkate alınmaz. tatlı su da, tuzlu su da, ekşi su da, sodalı su da bir sudur. canlı tuzlu suyu içer. çok geçmeden susar. bir daha içer, bir daha…
    tanım: genel-geçer çözüme ulaşmak umuduyla bölgesel ya da nokta atışı şeklinde oluşturulan akıntının akametle sürekli bütünleşmesinin düzeneğidir.
  • literatürde açgözlülük algoritması olarak da geçer.
    yapay zekada yoğun olmak üzere yazılım dillerinde hesaplama gerektiren spesifik konular için kullanılır. özet olarak şu şekildedir.
    yapabildiğinin en iyisini yap. olmuyor mu? bir sonrakine geç ve tekrar hesapla. tıkandınız mı? bir sonraki adıma ilerle.

    bunun en ünlü örneği de para üstü verme olayıdır.
    elimizde 1tl, 50kr, 25kr, 10kr, 5kr olmak üzere paralar var. ve karşımızdakine 2.95tl para üstü vermemiz gerekiyor. öncelikle 1tl ye bakıyoruz. 2 tane verebildiğimiz için hemen onu ayırıyoruz. üçüncü 1tl bizim elimizdeki sayıyı aştığı için onu atlıyoruz ve 50 kuruşa geçiyoruz. 2x 1tl + 1x 50kr + 1x 25kr + 2x 10kr olacak şekilde dağıtımımızı yapıyoruz. algoritmamızın asıl amacı anladığımız üzere kullanıcıya minimum miktar yollama. veriyi en aza indirebilme. istersek 59 tane 5kr de verebilirdik.

    tabi ki bu algoritma öyle %100 başarılı sonuç veren bir algoritma değil. para kullanımının kolaylığı açısından bu sistem hatasız çalışmaktadır. fakat elimizdeki paralar birbirinin katı olmayacak şekilde veya ortak bölenleri olmayan cinsten olsalardı ne olurdu?

    örneğin para birimlerimiz 17kr 10kr, 2kr ve 1kr . bunların dışında para kullanmadığınız bir yerde yaşadığınızı düşünün. para üstü olarak da 32kr dönmeniz gereken bir durum olsun. algoritma bizlere 17kr + 10kr + 2x 2kr + 1kr dönüş yapıyor. toplamda 5 adet para veriyor. fakat biz buna bağlı kalmadan 3x 10kr +2kr olacak şekilde 4 adet para verebiliriz.

    kullandığımız paraüstü sisteminin hatasız çalışması bu paraların birbirinin katı olması, ortak bölenlerinin 5 olması ve 10luk tabanda kolay hesaplanabilir olmasına bağlıdır. bu algoritma da gizliden gizliye hayatımıza işlemiştir dolayısıyla.

    best-first search olarak da bilinmektedir.
    (bkz: greedy approach algoritması)
    (bkz: greedy approach)

    edit: imla.