Örnekle Açgözlü Algoritma: Nedir, Yöntem ve Yaklaşım

Açgözlü yaklaşımı anlamak için özyineleme ve bağlam değiştirme konusunda yeterli bilgiye sahip olmanız gerekir. Bu, kodun nasıl izleneceğini anlamanıza yardımcı olur. Açgözlü paradigmayı kendi gerekli ve yeterli ifadelerinizle tanımlayabilirsiniz.

Açgözlü paradigmayı iki koşul tanımlar.

• Her aşamalı çözüm, problemi en iyi kabul gören çözüme doğru yapılandırmalıdır.
• Sorunun yapılanmasının sonlu sayıda açgözlü adımla durdurulabilmesi yeterlidir.

Teorileştirmeye devam ederek, Açgözlü arama yaklaşımıyla ilişkili geçmişi anlatalım.

Açgözlülüğün Tarihi Algorithms

İşte açgözlü algoritmaların önemli bir dönüm noktası:

• Açgözlü algoritmalar, 1950'lerde birçok grafik yürüyüş algoritması için kavramsallaştırıldı.
• Esdger Djikstra, minimum yayılan ağaçlar oluşturmak için algoritmayı kavramsallaştırdı. Hollanda'nın başkenti Amsterdam'daki rotaların kapsamını kısaltmayı hedefledi.
• Aynı on yılda Prim ve Kruskal, ağırlıklı rotalar boyunca yol maliyetlerini en aza indirmeye dayalı optimizasyon stratejileri elde etti.
• 70'lerde Amerikalı araştırmacılar Cormen, Rivest ve Stein, klasik algoritmalara giriş kitaplarında açgözlü çözümlerin yinelemeli bir alt yapılanmasını önerdiler.
• Açgözlü arama paradigması, 2005 yılında NIST kayıtlarında farklı bir optimizasyon stratejisi türü olarak kaydedildi.
• Bugüne kadar, açık-en kısa-yol-önce (OSPF) gibi web'i çalıştıran protokoller ve diğer birçok ağ paketi anahtarlama protokolü, ağda harcanan süreyi en aza indirmek için açgözlü stratejiyi kullanıyordu.

Açgözlü Stratejiler ve Kararlar

En kolay haliyle mantık "açgözlü" veya "açgözlü değil" şeklinde özetlendi. Bu ifadeler, her algoritma aşamasında ilerlemek için benimsenen yaklaşımla tanımlandı.

Örneğin, Djikstra'nın algoritması, bir maliyet fonksiyonu hesaplayarak İnternet'teki ana bilgisayarları tanımlayan adım adım açgözlü bir strateji kullandı. Maliyet fonksiyonu tarafından döndürülen değer, bir sonraki yolun "açgözlü" veya "açgözlü olmayan" olup olmadığını belirledi.

Kısacası, bir algoritma herhangi bir aşamada yerel olarak açgözlü olmayan bir adım atarsa ​​açgözlü olmaktan çıkar. Açgözlülük sorunları, açgözlülüğün daha fazla kapsamı kalmadığında sona erer.

Açgözlü Algoritmanın Özellikleri

Açgözlü algoritmanın önemli özellikleri şunlardır:

• Maliyetleri veya değer atıflarını içeren sıralı bir kaynak listesi vardır. Bunlar bir sistemdeki kısıtlamaları ölçer.
• Kısıtlamanın geçerli olduğu sürede maksimum kaynak miktarını alırsınız.
• Örneğin, bir aktivite planlama probleminde kaynak maliyetleri saat cinsindendir ve aktivitelerin seri sırayla gerçekleştirilmesi gerekmektedir.

Açgözlü Yaklaşımı neden kullanmalısınız?

Açgözlü yaklaşımı kullanmanın nedenleri şunlardır:

• Açgözlü yaklaşımın, onu optimizasyona uygun hale getirebilecek birkaç ödünleşimi vardır.
• Öne çıkan nedenlerden biri, en uygun çözüme hemen ulaşmaktır. Etkinlik seçme probleminde (Aşağıda açıklanmıştır) eğer mevcut aktivite tamamlanmadan önce daha fazla aktivite yapılabilirse bu aktiviteler aynı sürede yapılabilir.
• Diğer bir neden de, tüm çözümleri birleştirmeye gerek kalmadan, bir sorunu bir koşula dayalı olarak yinelemeli olarak bölmektir.
• Etkinlik seçme probleminde “özyinelemeli bölme” adımı, bir öğe listesinin yalnızca bir kez taranması ve belirli etkinliklerin dikkate alınmasıyla gerçekleştirilir.

Etkinlik seçme problemi nasıl çözülür?

Etkinlik planlama örneğinde her etkinlik için bir "başlangıç" ve "bitiş" zamanı vardır. Her Etkinlik referans olması amacıyla bir sayıyla indekslenir. İki etkinlik kategorisi vardır.

1. dikkate alınan aktivite: Geriye kalan birden fazla Aktiviteyi yapabilme yeteneğinin analiz edildiği referans olan Aktivitedir.
2. kalan aktiviteler: dikkate alınan faaliyetten önce bir veya daha fazla endeksteki faaliyetler.

Toplam süre, aktiviteyi gerçekleştirmenin maliyetini verir. Yani (bitiş – başlangıç) bize bir aktivitenin maliyeti olarak süreyi verir.

Açgözlü kapsamın, dikkate alınan bir aktivite süresinde gerçekleştirebileceğiniz kalan aktivite sayısı olduğunu öğreneceksiniz.

ArchiAçgözlü yaklaşımın yapısı

AŞAMA 1) Göz önünde bulundurulan Endeks olarak 0 endeksinden başlayarak faaliyet maliyetleri listesini tarayın.

AŞAMA 2) Zamanla daha fazla aktivite tamamlanabildiğinde, düşünülen aktivite biter, kalan bir veya daha fazla aktiviteyi aramaya başlanır.

AŞAMA 3) Daha fazla kalan aktivite yoksa mevcut kalan aktivite bir sonraki dikkate alınan aktivite haline gelir. Dikkate alınan yeni etkinlikle 1. ve 2. adımı tekrarlayın. Eğer kalan aktivite yoksa 4. adıma geçin.

ADIM 4) Dikkate alınan endekslerin birliğini döndürün. Bunlar, verimi en üst düzeye çıkarmak için kullanılacak etkinlik endeksleridir.

Kod Açıklama

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Kodun açıklaması:

1. Dahil edilen başlık dosyaları/sınıfları
2. Kullanıcı tarafından sağlanan maksimum etkinlik sayısı.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Kodun açıklaması:

1. Akış işlemleri için ad alanı.
2. TIME için bir sınıf tanımı
3. Bir saatlik zaman damgası.
4. TIME varsayılan yapıcısı
5. Saat değişkeni.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Kodun açıklaması:

1. Etkinlikten bir sınıf tanımı
2. Süreyi tanımlayan zaman damgaları
3. Varsayılan yapıcıda tüm zaman damgaları 0 olarak başlatılır

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Kodun açıklaması:

1. Zamanlayıcı sınıfı tanımının 1. kısmı.
2. Dikkate Alınan Dizin, taramanın başlangıç ​​noktasıdır. dizi.
3. Başlatma dizini rastgele zaman damgaları atamak için kullanılır.
4. Bir dizi etkinlik nesnesi, new operatörü kullanılarak dinamik olarak tahsis edilir.
5. Planlanan işaretçi, açgözlülük için geçerli temel konumu tanımlar.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Kodun açıklaması:

1. Zamanlayıcı oluşturucusu – zamanlayıcı sınıfı tanımının 2. kısmı.
2. Dikkate alınan dizin, geçerli taramanın geçerli başlangıcını tanımlar.
3. Mevcut açgözlülük düzeyi başlangıçta tanımsızdır.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
…
…

Kodun açıklaması:

1. Halihazırda planlanan etkinliklerin her birinin başlangıç ​​saatlerini ve bitiş saatlerini başlatmak için bir for döngüsü.
2. Başlangıç ​​zamanı başlatma.
3. Bitiş zamanı başlatma her zaman başlangıç ​​saatinden sonra veya tam olarak başlangıç ​​saatinde.
4. Tahsis edilen süreleri yazdırmak için bir hata ayıklama ifadesi.

	public:
   		 Activity * activity_select(int);
};

Kodun açıklaması:

1. Bölüm 4 – zamanlayıcı sınıfı tanımının son kısmı.
2. Etkinlik seçme işlevi, bir başlangıç ​​noktası indeksini temel alır ve açgözlü arayışı, açgözlü alt problemlere böler.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
… 

1. Kapsam çözümleme işleci (::) kullanılarak işlev tanımı sağlanır.
2. Dikkate alınan Endeks, değere göre adlandırılan Endekstir. greedy_extent, dikkate alınan Dizinden hemen sonra başlatılan bir dizindir.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
…
...

Kodun açıklaması:

1. Temel mantık: Açgözlülüğün kapsamı faaliyet sayısıyla sınırlıdır.
2. Mevcut Faaliyetin başlangıç ​​saatleri, dikkate alınan Faaliyetin (dikkate alınan indeks tarafından verilir) bitmesinden önce programlanabilir olarak kontrol edilir.
3. Bu mümkün olduğu sürece isteğe bağlı bir hata ayıklama ifadesi yazdırılır.
4. Etkinlik dizisindeki sonraki dizine ilerleyin

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Kodun açıklaması:

1. Koşullu kontroller tüm faaliyetlerin kapsanıp kapsanmadığını kontrol eder.
2. Değilse, geçerli nokta olarak kabul edilen Endeks ile açgözlülüğünüzü yeniden başlatabilirsiniz. Bu, problem ifadesini açgözlülükle bölen yinelenen bir adımdır.
3. Eğer evet ise, açgözlülüğü genişletme kapsamı olmadan arayan kişiye geri döner.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Kodun açıklaması:

1. Zamanlayıcıyı çağırmak için kullanılan ana işlev.
2. Yeni bir Zamanlayıcı başlatıldı.
3. Faaliyet tipinin bir işaretçisini döndüren aktivite seçme işlevi, açgözlü görev bittikten sonra arayan kişiye geri döner.

Çıktı:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

Açgözlü Tekniğin Sınırlamaları

Sıralama gibi her alt problem için bir çözümün gerekli olduğu Açgözlü problemler için uygun değildir.

Bu tür Açgözlü algoritma uygulama problemlerinde Açgözlü yöntem yanlış olabilir; en kötü durumda optimal olmayan bir çözüme bile yol açabilir.

Dolayısıyla açgözlü algoritmaların dezavantajı, mevcut açgözlü durumun önünde ne olduğunu bilmemektir.

Aşağıda Açgözlü yöntemin dezavantajının bir tasviri bulunmaktadır:

Burada bir ağaç (daha yüksek değer daha yüksek açgözlülük) olarak gösterilen açgözlü taramada, 40 değerindeki bir algoritma durumunun bir sonraki değer olarak 29'u alması muhtemeldir. Ayrıca görevi 12'de bitiyor. Bu da 41 değerine tekabül ediyor.

Bununla birlikte, algoritma optimalin altında bir yol izlemişse veya bir fethetme stratejisi benimsemişse. daha sonra 25'i 40 takip edecek ve toplam maliyet iyileştirmesi 65 olacaktır ki bu, optimal olmayan bir karar olarak 24 puan daha yüksek olarak değerlendirilmektedir.

Açgözlülük Örnekleri Algorithms

Çoğu ağ algoritması açgözlü yaklaşımı kullanır. İşte birkaç Açgözlü algoritma örneğinin listesi:

• Prim'in Minimal Yayılan Ağaç Algoritması
• Gezgin Satıcı Sorunu
• Grafik – Harita Boyama
• Kruskal'ın Minimal Yayılan Ağaç Algoritması
• Dijkstra'nın Minimal Yayılan Ağaç Algoritması
• Grafik – Köşe Kapağı
• Sırt Çantası Sorunu
• İş Planlama Sorunu

ÖZET

Özetlemek gerekirse, makale açgözlü paradigmayı tanımladı, açgözlü optimizasyon ve özyinelemenin bir noktaya kadar en iyi çözümü elde etmenize nasıl yardımcı olabileceğini gösterdi. Açgözlü algoritma, birçok dilde Greedy algoritması olarak problem çözümü için yaygın olarak uygulamaya konulmuştur. Python, C, C#, PHP, Java, vb. Açgözlü algoritma örneğinin aktivite seçimi, açgözlü yaklaşımı kullanarak maksimum verim elde edebilecek stratejik bir problem olarak tanımlandı. Son olarak açgözlü yaklaşımın sakıncaları açıklandı.