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

Açgözlü Algoritma Nedir?

A Açgözlü algoritma Bir kaynak kümesini, yürütmenin herhangi bir aşamasında o kaynağın maksimum anlık kullanılabilirliğine göre özyinelemeli olarak böler.

Açgözlü yaklaşım ile bir problemi çözmenin iki aşaması vardır:

1. Öğe listesinin taranması
2. Optimizasyon

Giriş dizisi kademeli olarak bölündükçe her iki aşama da paralel olarak ilerler.

Açgözlü yaklaşımı izlemek için, özyineleme ve bağlam değiştirme konusunda temel bir bilgiye sahip olmak faydalı olacaktır. tracKodun kendisi. Açgözlü paradigma, gerekli ve yeterli ifadelerden oluşan bir çift ile tanımlanabilir.

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

• Her aşamada yapılacak seçimler, sorunu en iyi kabul gören çözüme doğru yönlendirmelidir.
• Problem yapısı, sonlu sayıda açgözlü adımda durmalıdır.

Teoriyi ele aldıktan sonra, açgözlü arama yaklaşımının ardındaki tarihe bir göz atalım.

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

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

• Açgözlü algoritmalar ilk olarak 1950'lerde grafik gezintisi algoritmaları için kavramsallaştırılmıştır.
• Edsger Dijkstra, Hollanda'nın başkenti Amsterdam'daki güzergahları kısaltmak için en kısa yol algoritmasını geliştirdi.
• Aynı on yılda Prim ve Kruskal, minimum yayılma ağaçları oluşturmak için ağırlıklı rotalar boyunca yol maliyetlerini en aza indiren optimizasyon stratejileri geliştirdiler.
• 70'lerde Amerikalı araştırmacılar Cormen, Leiserson, Rivest ve Stein, klasik çalışmalarında açgözlü çözümlerin özyinelemeli alt yapısını tanımladılar. Introduction to Algorithms ders kitabı.
• Açgözlü arama paradigması, 2005 yılında NIST kayıtlarında ayrı bir optimizasyon stratejisi olarak kataloglanmıştır.
• Günümüzde bile, Open Shortest Path First (OSPF) gibi web protokolleri ve birçok paket anahtarlama protokolü, ağ üzerindeki geçiş süresini en aza indirmek için açgözlü stratejiyi kullanmaktadır.

Açgözlü Stratejiler ve Kararlar

Algoritmanın ilerleme yönüne bağlı olarak, her aşamada mantık ikili bir seçime indirgeniyor: "açgözlü" veya "açgözlü değil".

Örneğin, Dijkstra algoritması, her adımda bir maliyet fonksiyonunu değerlendirerek İnternet üzerindeki sunucuları belirler. Maliyet fonksiyonunun döndürdüğü değer, bir sonraki yolun "açgözlü" mü yoksa "açgözlü olmayan" mı olduğuna karar verir.

Özetle, bir algoritma yerel olarak en uygun olmayan bir adım attığı anda açgözlü olmayı bırakır ve açgözlü problemler, daha fazla açgözlü adım mümkün olmadığında durur.

Açgözlü Algoritmanın Özellikleri

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

• Kaynakların sıralı bir listesi, sistem üzerindeki kısıtlamaları nicelleştiren maliyet veya değer atıfları içerir.
• Algoritma, belirli bir süre kısıtlaması dahilinde maksimum kaynak miktarını kullanır.
• Örneğin, bir faaliyet planlama probleminde kaynak maliyetleri saat cinsinden ölçülür ve faaliyetler seri bir sırayla gerçekleştirilmelidir.

Neden Açgözlü Yaklaşımı Kullanmalıyız?

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

• Açgözlü yaklaşımın, onu optimizasyona oldukça uygun kılan bazı dezavantajları vardır.
• En bariz sebep, hemen uygulanabilir bir çözüm üretmektir. Aşağıda ele alınan faaliyet seçimi probleminde, mevcut faaliyet bitmeden önce birden fazla faaliyet uygunsa, bunlar aynı zaman dilimine planlanabilir.
• Bir diğer neden ise, alt çözümleri birleştirmeye gerek kalmadan, bir problemi koşula bağlı olarak özyinelemeli olarak bölmesidir.
• Faaliyet seçimi probleminde, özyinelemeli bölme adımı, listeyi bir kez tarayarak ve yalnızca uygun faaliyetleri dikkate alarak gerçekleştirilir.

Faaliyet Seçimi Problemini Nasıl Çözebiliriz?

Etkinlik planlama örneğinde, her etkinliğin bir başlangıç ​​ve bitiş zamanı vardır ve referans için bir numara ile indekslenir. İki etkinlik kategorisi vardır:

1. Değerlendirilen faaliyet: Geri kalan faaliyetlerin yerine getirilme yeteneğinin ölçüldüğü referans faaliyet.
2. Kalan faaliyetler: dikkate alınan faaliyetten önce bir veya daha fazla endeksteki faaliyetler.

Bir faaliyetin maliyeti, o faaliyetin süresidir ve (bitiş – başlangıç) olarak hesaplanır.

Açgözlü kapsam, basitçe, ele alınan bir faaliyetin süresi içinde gerçekleştirilebilecek kalan faaliyetlerin sayısıdır.

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

) 1 Adım Değerlendirilen endeks olarak 0'dan başlayarak faaliyet maliyetleri listesini tarayın.

) 2 Adım Eğer incelenen faaliyet sona erdiğinde birden fazla faaliyet tamamlanabiliyorsa, kalan faaliyetleri arayın.

) 3 Adım Eğer daha fazla etkinlik planlanamıyorsa, mevcut kalan etkinlik bir sonraki değerlendirilecek etkinlik olur. 1. ve 2. adımları yeni değerlendirilecek etkinlikle tekrarlayın. Eğer hiç etkinlik kalmadıysa, 4. adıma geçin.

) 4 Adım Değerlendirilen endekslerin birleşimini döndürün; bunlar verimliliği en üst düzeye çıkaran faaliyet endeksleridir.

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

Code 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 yapılandırılabilecek 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 standart ad alanını tanımlar.
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. Activity için bir sınıf tanımı.
2. Birlikte bir süreyi tanımlayan zaman damgaları.
3. Varsayılan yapıcı fonksiyonda 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. considered_index, diziyi taramaya başlama noktasıdır.
3. init_index, kurulum sırasında rastgele zaman damgaları atamak için kullanılır.
4. Yeni operatör ile dinamik olarak bir Activity nesne dizisi tahsis edilir.
5. Planlanmış işaretçi, mevcut açgözlü sonucu tutar.

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

Kodun açıklaması:

1. Zamanlayıcı yapıcı metodu — sınıf tanımının 2. bölümü.
2. considered_index, mevcut taramanın başlangıcını işaretler.
3. Açgözlülüğün kapsamı başlangıçta belirsizdir.

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);
 }
&#8230;
&#8230;

Kodun açıklaması:

1. Bir for döngüsü, planlanan her aktivitenin başlangıç ​​ve bitiş saatlerini belirler.
2. Başlangıç ​​zamanını başlatır.
3. Bitiş saatini başlangıç ​​saatinde veya sonrasında olacak şekilde ayarlar.
4. Bir hata ayıklama ifadesi, ayrılan süreleri yazdırır.

	public:
   		 Activity * activity_select(int);
};

Kodun açıklaması:

1. Bölüm 4 — Zamanlayıcı sınıfı tanımının son bölümü.
2. `activity_select()` fonksiyonu, başlangıç ​​indeksini temel alarak açgözlü aramayı 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 operatörü (::), fonksiyon tanımını Zamanlayıcı sınıfına bağlar.
2. considered_index değeri iletilir ve greedy_extent, hemen ardından gelen indekse başlatılır.

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++;
    	}
&#8230;
...

Kodun açıklaması:

1. Temel mantık şu: Açgözlülüğün kapsamı MAX_ACTIVITIES ile sınırlandırılmıştır.
2. Mevcut faaliyetin başlangıç ​​saati, incelenen faaliyetin bitiş saatiyle karşılaştırılır.
3. Bu koşul sağlandığı sürece, isteğe bağlı bir hata ayıklama mesajı yazdırılır.
4. Ardından, açgözlü kapsam, etkinlik dizisindeki bir sonraki indekse ilerler.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Kodun açıklaması:

1. Şartlı kontrol, tüm faaliyetlerin kapsanıp kapsanmadığını denetler.
2. Aksi takdirde, algoritma açgözlü arayışı mevcut indeksten yeniden başlatır; bu, problemi açgözlü bir şekilde bölen özyinelemeli bir adımdır.
3. Eğer evet ise, kontrol çağırana geri döner ve açgözlülüğün genişletilmesi için hiçbir olanak kalmaz.

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

Kodun açıklaması:

1. Ana fonksiyon, Zamanlayıcıyı çağırır.
2. Yeni bir Zamanlayıcı nesnesi oluşturuluyor.
3. `activity_select()` fonksiyonu, açgözlü arama sona erdiğinde çağırana bir `Activity` işaretçisi döndürür.

Çı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ı

Açgözlü yaklaşım, sıralama gibi her alt problem için en uygun çözümü gerektiren problemler için uygun değildir.

Bu gibi durumlarda açgözlü yöntem yanlış olabilir; en kötü durumda ise optimal olmayan bir çözüm üretir.

Açgözlü algoritmaların temel dezavantajı, mevcut açgözlü durumun ilerisinde ne olacağını bilmeden seçim yapmalarıdır.

Aşağıdaki diyagram, açgözlü yöntemin bu dezavantajını göstermektedir.

Burada ağaç şeklinde gösterilen açgözlü taramada (daha yüksek değer daha yüksek açgözlülük anlamına gelir), 40 değerindeki bir algoritma bir sonraki adımda 29'u seçecek, ardından 12'de bitirecek ve toplamda 41'e ulaşacaktır.

Buna karşılık, böl ve yönet stratejisi 25'i 40 ile takip ederek toplamda 65'e ulaşır ki bu, yerel olarak açgözlü tercihten 24 puan daha yüksektir.

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

Çoğu ağ algoritması açgözlü bir yaklaşıma dayanır. Yaygın açgözlü algoritma örnekleri şunlardır:

• Prim'in Minimum Yayılma Ağacı Algoritması
• Gezgin Satıcı Problemi (yaklaşık)
• Grafik Harita Boyama
• Kruskal'ın Minimum Yayılma Ağacı Algoritması
• Dijkstra'nın En Kısa Yol Algoritması
• Grafik Köşe Örtüsü
• Sırt Çantası Sorunu
• Son Teslim Tarihleriyle İş Sıralaması

SSS