Örneklerle Açgözlü Algoritma: Açgözlü Yöntem & Yaklaşmak

İçindekiler:

Anonim

Açgözlü Algoritma nedir?

Gelen Açgözlü Algoritma kaynakların bir dizi yinelemeli yürütme herhangi bir aşamasında maksimum, yani kaynağın hemen doluluk durumuna göre ayrılır.

Açgözlü yaklaşıma dayalı bir sorunu çözmek için iki aşama vardır

  1. Öğe listesi taranıyor
  2. Optimizasyon

Bu aşamalar, dizinin bölünmesi sırasında bu Açgözlü algoritma eğitiminde paralel olarak ele alınmıştır.

Açgözlü yaklaşımı anlamak için özyineleme ve bağlam değiştirme konusunda çalışma bilgisine sahip olmanız gerekir. Bu, kodu nasıl izleyeceğinizi anlamanıza yardımcı olur. Açgözlü paradigmayı kendi gerekli ve yeterli ifadelerinize göre tanımlayabilirsiniz.

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

  • Her adım adım çözüm, en çok kabul gören çözüme doğru bir sorun oluşturmalıdır.
  • Sorunun yapılanmasının sınırlı sayıda açgözlü adımda durması yeterlidir.

Teorileştirme devam ederken, Açgözlü arama yaklaşımı ile ilişkili tarihi anlatalım.

Bu Açgözlü algoritma eğitiminde şunları öğreneceksiniz:

  • Açgözlü Algoritmaların Tarihi
  • Açgözlü Stratejiler ve Kararlar
  • Açgözlü Yaklaşımın Özellikleri
  • Açgözlü Yaklaşımı neden kullanmalısınız?
  • Aktivite seçimi problemi nasıl çözülür
  • Açgözlü yaklaşımın mimarisi
  • Açgözlü Algoritmaların Dezavantajları

Açgözlü Algoritmaların Tarihi

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, algoritmayı minimum genişleyen ağaçlar oluşturmak için kavramsallaştırdı. Hollanda'nın başkenti Amsterdam'daki güzergahların açıklığını kısaltmayı hedefledi.
  • Aynı on yılda, Prim ve Kruskal, ağırlıklı rotalar boyunca yol maliyetlerini en aza indirmeye dayalı optimizasyon stratejilerine ulaştı.
  • 70'lerde, Amerikalı araştırmacılar, Cormen, Rivest ve Stein, algoritmalara klasik giriş kitaplarında açgözlü çözümlerin yinelemeli bir alt yapısı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, önce en kısa yolu aç (OSPF) ve diğer birçok ağ paketi anahtarlama protokolü gibi web'i çalıştıran protokoller, bir ağda harcanan zamanı en aza indirmek için açgözlü stratejiyi kullanır.

Açgözlü Stratejiler ve Kararlar

Mantık, en kolay şekliyle "açgözlü" veya "açgözlü değil" olarak ö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 aşamalı açgözlü bir strateji kullandı. Maliyet işlevi tarafından döndürülen değer, sonraki yolun "açgözlü" veya "açgözlü" olup olmadığını belirler.

Kısacası, bir algoritma herhangi bir aşamada yerel açgözlü olmayan bir adım atarsa ​​açgözlü olmaktan çıkar. Açgözlülük sorunları, açgözlülük kapsamı kalmadan durur.

Açgözlü Yaklaşımın Özellikleri

Açgözlü yöntem algoritmasının önemli özellikleri şunlardır:

  • Maliyetler veya değer atıflarıyla birlikte sıralı bir kaynak listesi vardır. Bunlar, bir sistemdeki kısıtlamaları nicelleştirir.
  • Bir kısıtlamanın geçerli olduğu süre içinde maksimum miktarda kaynak alacaksınız.
  • Örneğin, bir faaliyet çizelgeleme probleminde, kaynak maliyetleri saat cinsindendir ve faaliyetlerin seri sırayla gerçekleştirilmesi gerekir.

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, optimizasyona uygun hale getirebilecek birkaç ödünleşime sahiptir.
  • Öne çıkan nedenlerden biri, en uygun çözüme hemen ulaşmaktır. Aktivite seçme probleminde (aşağıda açıklanmıştır) mevcut aktivite bitmeden daha fazla aktivite yapılabiliyorsa bu aktiviteler aynı anda yapılabilir.
  • Diğer bir neden, tüm çözümleri bir araya getirmeye gerek kalmadan bir sorunu bir duruma göre yinelemeli olarak bölmektir.
  • Aktivite seçme probleminde, "özyinelemeli bölme" adımı, bir öğe listesinin yalnızca bir kez taranması ve belirli aktiviteler dikkate alınarak gerçekleştirilir.

Aktivite seçimi problemi nasıl çözülür

Aktivite planlama örneğinde, her aktivite için bir "başlangıç" ve "bitiş" zamanı vardır. Her Aktivite referans için bir numara ile indekslenir. İki aktivite kategorisi vardır.

  1. dikkate alınan aktivite : kalan birden fazla Aktiviteyi yapabilme yeteneğinin analiz edildiği referans olan Aktivitedir.
  2. Kalan etkinlikler: dikkate alınan etkinlikten önce bir veya daha fazla dizinde bulunan etkinlikler.

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

Açgözlü boyutun, dikkate alınan bir etkinlik sırasında gerçekleştirebileceğiniz kalan etkinlik sayısı olduğunu öğreneceksiniz.

Açgözlü yaklaşımın mimarisi

AŞAMA 1)

Endeks olarak dikkate alınan Endeks 0'dan başlayarak aktivite maliyetleri listesini tarayın.

ADIM 2)

Zamana kadar daha fazla aktivite tamamlandığında, dikkate alınan aktivite biter, kalan bir veya daha fazla aktiviteyi aramaya başlayın.

AŞAMA 3)

Kalan başka etkinlik yoksa, geçerli kalan etkinlik bir sonraki değerlendirilen etkinlik olur. Yeni dikkate alınan etkinlikle 1. ve 2. adımı tekrarlayın. Kalan etkinlik yoksa 4. adıma gidin.

ADIM 4)

Dikkate alınan endekslerin birleşimini döndür. Bunlar, verimi en üst düzeye çıkarmak için kullanılacak etkinlik endeksleridir.

Açgözlü Yaklaşım Mimarisi

Kod Açıklama

#include#include#include#define MAX_ACTIVITIES 12

Kod 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;}};

Kod açıklaması:

  1. Akış işlemleri için ad alanı.
  2. TIME için bir sınıf tanımı
  3. Bir saat zaman damgası.
  4. Bir TIME varsayılan kurucusu
  5. Saat değişkeni.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Kod açıklaması:

  1. Aktiviteden bir sınıf tanımı
  2. Süre tanımlayan zaman damgaları
  3. Varsayılan kurucuda 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;

Kod açıklaması:

  1. Planlayıcı sınıf tanımının 1. Bölümü.
  2. Düşünülen Dizin, diziyi taramak için başlangıç ​​noktasıdır.
  3. Başlatma indeksi, rastgele zaman damgaları atamak için kullanılır.
  4. Yeni operatör kullanılarak dinamik olarak bir etkinlik nesneleri dizisi tahsis edilir.
  5. Zamanlanmış işaretçi açgözlülük için geçerli temel konumu tanımlar.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Kod açıklaması:

  1. Zamanlayıcı yapıcısı - zamanlayıcı sınıf tanımının 2. bölümü.
  2. Dikkate alınan dizin, geçerli taramanın geçerli başlangıcını tanımlar.
  3. Mevcut açgözlü kapsam başlangıçta tanımlanmamıştı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);}… …

Kod 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 sonra veya tam olarak başlangıç ​​saatinde
  4. Ayrılan süreleri yazdırmak için bir hata ayıklama ifadesi.
public:Activity * activity_select(int);};

Kod açıklaması:

  1. Bölüm 4 - zamanlayıcı sınıf tanımının son bölümü.
  2. Etkinlik seçme işlevi, temel olarak bir başlangıç ​​noktası indeksi 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ünürlük operatörü (: :) 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 İndeks'ten sonra başlatılan indekstir.
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++;}… …

Kod açıklaması:

  1. Temel mantık - Açgözlü kapsam, faaliyetlerin sayısıyla sınırlıdır .
  2. Geçerli Aktivitenin başlangıç ​​saatleri, dikkate alınan Aktivite (dikkate alınan indeks tarafından verilir) bitmeden önce planlanabilir 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 ilerle
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Kod açıklaması:

  1. Koşullu, tüm faaliyetlerin kapsanmış olup olmadığını kontrol eder.
  2. Değilse, mevcut nokta olarak kabul edilen Endeks ile açgözlünüzü yeniden başlatabilirsiniz. Bu, problem ifadesini açgözlülükle bölen yinelemeli bir adımdır.
  3. Eğer evet ise, açgözlülüğü genişletmek için bir kapsam olmadan arayana geri döner.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Kod açıklaması:

  1. Zamanlayıcıyı çağırmak için kullanılan ana işlev.
  2. Yeni bir Zamanlayıcı somutlaştırılır.
  3. Açgözlü görev bittikten sonra arayana geri dönen bir etkinlik türü işaretçisi döndüren etkinlik seçme işlevi.

Çıktı:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Açgözlü Algoritmaların Dezavantajları

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öntemi yanlış olabilir; en kötü durumda, optimal olmayan bir çözüme bile götürür.

Bu nedenle, açgözlü algoritmaların dezavantajı, mevcut açgözlü durumun önünde ne olduğunu bilmemeyi kullanmaktır.

Aşağıda, Greedy yönteminin dezavantajının bir tasviri bulunmaktadır:

Burada bir ağaç olarak gösterilen açgözlü taramada (daha yüksek değer daha yüksek açgözlülük), 40 değerindeki bir algoritma durumu, bir sonraki değer olarak 29'u alır. Dahası, görevi 12'de bitiyor. Bu 41 değerine denk geliyor.

Bununla birlikte, algoritma optimalin altında bir yol izlediyse veya bir fetih stratejisi benimserse. daha sonra 25'i 40 takip eder ve toplam maliyet iyileştirmesi 65 olur ve bu da optimum altı bir karar olarak 24 puan daha yüksek değerdedir.

Açgözlü Algoritma Örnekleri

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

  • Prim'in Minimal Kapsayan Ağaç Algoritması
  • Seyahat Eden Satıcı Problemi
  • Grafik - Harita Renklendirme
  • Kruskal'ın Minimal Kapsayan Ağaç Algoritması
  • Dijkstra'nın Minimal Kapsayan Ağaç Algoritması
  • Grafik - Köşe Kapağı
  • Sırt Çantası Sorunu
  • İş Planlama Problemi

Ö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, açgözlü algoritma Python, C, C #, PHP, Java vb. Gibi birçok dilde problem çözme için yaygın olarak uygulamaya alınmıştır. yaklaşmak. Sonunda, açgözlü yaklaşımın kullanımının sakıncaları açıklandı.