Açgözlü yöntem, sorunları çözmek için kullanılan Böl ve yönet gibi stratejilerden biridir. Bu yöntem optimizasyon problemlerinin çözümünde kullanılır. Optimizasyon problemi maksimum ya da minimum sonuç gerektiren bir problemdir. Bazı terimlerle anlayalım.

Açgözlü yöntem en basit ve anlaşılır yaklaşımdır. Bu bir algoritma değil, bir tekniktir. Bu yaklaşımın temel işlevi, kararın mevcut mevcut bilgilere dayanarak alınmasıdır. Mevcut bilgi ne olursa olsun, mevcut kararın gelecekteki etkisinden endişe edilmeden karar verilir.

css kullanarak kenarlık

Bu teknik temel olarak optimal olabilecek veya olmayabilecek uygun çözümü belirlemek için kullanılır. Uygun çözüm, verilen kriterleri karşılayan bir alt kümedir. Optimal çözüm, alt kümedeki en iyi ve en uygun çözüm olan çözümdür. Mümkün olması durumunda, birden fazla çözüm verilen kriterleri karşılıyorsa bu çözümler uygun olarak kabul edilecektir; optimal çözüm ise tüm çözümler arasında en iyi çözümdür.

Açgözlü yöntemin özellikleri

Açgözlü yöntemin özellikleri şunlardır:

• Çözümü en uygun şekilde oluşturmak için bu algoritma, bir kümenin seçilen tüm öğeleri içerdiği ve diğer kümenin reddedilen öğeleri içerdiği iki küme oluşturur.
• Açgözlü bir algoritma, çözümün uygulanabilir ya da optimal olması umuduyla iyi yerel seçimler yapar.

Açgözlü Algoritmanın Bileşenleri

Açgözlü algoritmada kullanılabilecek bileşenler şunlardır:

Youtube videolarını indirmek için vlc

Aday seti:Kümeden oluşturulan çözüme aday küme denir.Seçim fonksiyonu:Bu fonksiyon, çözüme eklenebilecek aday veya alt kümeyi seçmek için kullanılır.Fizibilite fonksiyonu:Adayın veya alt kümenin çözüme katkıda bulunmak için kullanılıp kullanılamayacağını belirlemek için kullanılan bir fonksiyon.Amaç fonksiyonu:Değeri çözüme veya kısmi çözüme atamak için bir fonksiyon kullanılır.Çözüm fonksiyonu:Bu fonksiyon, fonksiyonun tamamına ulaşılıp ulaşılmadığını belirtmek için kullanılır.

Açgözlü Algoritmanın Uygulamaları

• En kısa yolu bulmada kullanılır.
• Prim algoritmasını veya Kruskal algoritmasını kullanarak minimum yayılan ağacı bulmak için kullanılır.
• Son teslim tarihi olan iş sıralamasında kullanılır.
• Bu algoritma kesirli sırt çantası problemini çözmek için de kullanılır.

Açgözlü Algoritmanın sözde kodu

 Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } 

Yukarıdaki açgözlü algoritmadır. Başlangıçta çözüme sıfır değeri atanır. Açgözlü algoritmada diziyi ve eleman sayısını geçiyoruz. For döngüsünün içinde elemanları tek tek seçip çözümün uygulanabilir olup olmadığını kontrol ediyoruz. Eğer çözüm mümkünse birleştirme işlemini gerçekleştiriyoruz.

Bir örnek üzerinden anlayalım.

Diyelim ki bir 'P' sorunu var. Aşağıda gösterildiği gibi A'dan B'ye seyahat etmek istiyorum:

P : Bir → B

Sorun şu ki, bu yolculuğu A'dan B'ye gitmek zorundayız. A'dan B'ye gitmenin çeşitli çözümleri var. A'dan B'ye şu şekilde gidebiliriz: yürümek, araba, bisiklet, tren, uçak , vb. Yolculukta bir kısıtlama var, bu yolculuğu 12 saat içinde yapmamız gerekiyor. Ancak tren veya uçakla gidersem bu mesafeyi 12 saatte katedebilirim. Bu problemin birçok çözümü vardır ancak kısıtı sağlayan yalnızca iki çözüm vardır.

niyet niyet

Yolculuğu minimum maliyetle karşılamamız lazım diyorsak. Bu, bu mesafeyi mümkün olduğu kadar minimum düzeyde kat etmemiz gerektiği anlamına gelir, dolayısıyla bu sorun minimizasyon sorunu olarak bilinir. Şu ana kadar elimizde iki uygulanabilir çözüm var; biri trenle, diğeri hava yoluyla. Trenle seyahat etmek minimum maliyete yol açacağından en uygun çözümdür. Optimum çözüm aynı zamanda uygun çözümdür ancak en iyi sonucu sağlayarak çözümün minimum maliyetle en uygun çözüm olmasını sağlar. Tek bir optimal çözüm olacaktır.

Minimum veya maksimum sonucu gerektiren problem, optimizasyon problemi olarak bilinir. Açgözlü yöntem optimizasyon problemlerinin çözümünde kullanılan stratejilerden biridir.

Açgözlü algoritma kullanmanın dezavantajları

Açgözlü algoritma, daha geniş problemi dikkate almadan, her aşamada mevcut olan bilgilere dayanarak kararlar verir. Dolayısıyla açgözlü çözümün her sorun için en iyi çözümü vermeme ihtimali olabilir.

Küresel optimumu bulmak amacıyla her aşamada yerel optimum seçimini takip eder. Bir örnek üzerinden anlayalım.

Aşağıda verilen grafiği düşünün:

java dili mülakat soruları

Kaynaktan hedefe en az maliyetle gitmek zorundayız. Maliyet yolları 10, 20 ve 5 olan üç uygun çözümümüz olduğundan, 5 minimum maliyet yoludur ve dolayısıyla optimal çözümdür. Bu yerel optimumdur ve bu şekilde global optimal çözümü hesaplamak için her aşamada yerel optimumu buluruz.