Ahne algoritm koos näitega: mis on, meetod ja lähenemisviis

Mis on ahne algoritm?

A Ahne algoritm jagab rekursiivselt ressursside komplekti selle ressursi maksimaalse kohese kättesaadavuse alusel mis tahes teostusetapis.

Ahne lähenemisviisiga probleemi lahendamine toimub kahes etapis:

1. Üksuste loendi skannimine
2. Optimeerimine

Mõlemad etapid töötavad paralleelselt, kuna sisendmassiiv jagatakse järk-järgult.

Ahne lähenemise järgimiseks on abiks rekursiooni ja kontekstivahetuse tundmine. trace koodi. Ahnet paradigmat saab kirjeldada vajalike ja piisavate lausete paariga.

Ahne paradigma määratlevad kaks tingimust.

• Iga sammhaaval tehtav valik peab suunama probleemi parima vastuvõetava lahenduse poole.
• Probleemi struktuur peab peatuma lõpliku arvu ahnete sammude järel.

Nüüd, kui teooria on paigas, vaatame ahne otsingu lähenemisviisi ajalugu.

Ahne ajalugu Algorithms

Siin on ahnete algoritmide ajaloo olulised verstapostid:

• Ahned algoritmid kontseptualiseeriti esmakordselt graafikõndimise algoritmide jaoks 1950. aastatel.
• Edsger Dijkstra töötas välja oma lühima tee algoritmi, et lühendada marsruute läbi Hollandi pealinna Amsterdami.
• Samal kümnendil töötasid Prim ja Kruskal välja optimeerimisstrateegiad, mis minimeerivad kaalutud marsruutide kulusid, et luua minimaalsed ulatuvad puud.
• 70ndatel kirjeldasid Ameerika teadlased Cormen, Leiserson, Rivest ja Stein oma klassikalises töös ahnete lahenduste rekursiivset alamstruktureerimist. Introduction to Algorithms õpik.
• Ahne otsingu paradigma kataloogiti NISTi andmetes 2005. aastal eraldi optimeerimisstrateegiana.
• Tänapäevani kasutavad veebiprotokollid, näiteks OSPF (Open Shortest Path First) ja paljud pakettkommutatsiooniprotokollid, võrgu transiidiaja minimeerimiseks ahnet strateegiat.

Ahned strateegiad ja otsused

Loogika taandub igal etapil binaarseks valikuks – „ahne” või „mitteahne” –, lähtudes algoritmi edasiliikumise suunast.

Näiteks Dijkstra algoritm tuvastab internetis hostid, hinnates igal sammul kulufunktsiooni. Kulufunktsiooni tagastatud väärtus otsustab, kas järgmine tee on „ahne“ või „mitteahne“.

Lühidalt, algoritm lakkab olemast ahne hetkel, kui see astub sammu, mis pole lokaalselt optimaalne, ja ahned probleemid peatuvad, kui edasine ahne samm pole võimalik.

Ahne algoritmi omadused

Greedy algoritmi olulised omadused on järgmised:

• Ressursside järjestatud loend sisaldab kulu- või väärtusomadusi, mis kvantifitseerivad süsteemi piiranguid.
• Algoritm võtab piirangu kehtivuse piires maksimaalse hulga ressursse.
• Näiteks tegevuste ajastamise probleemis mõõdetakse ressursikulusid tundides ja tegevused tuleb läbi viia järjestikku.

Miks kasutada ahnet lähenemist?

Siin on ahne lähenemisviisi kasutamise põhjused:

• Ahne lähenemisviisil on kompromissid, mis muudavad selle optimeerimiseks hästi sobivaks.
• Kõige ilmsemaks põhjuseks on koheselt teostatava lahenduse leidmine. Allpool käsitletud tegevuste valiku probleemis, kui enne praeguse tegevuse lõppu mahub rohkem tegevusi, saab need samasse aknasse ajastada.
• Teine põhjus on see, et see jagab probleemi rekursiivselt tingimuse alusel, ilma et oleks vaja alamlahendusi ühendada.
• Tegevuste valiku probleemis saavutatakse rekursiivne jagamisetapp loendi ühekordse skaneerimise ja ainult sobivate tegevuste arvessevõtmise teel.

Kuidas lahendada tegevuse valiku probleemi

Tegevuste ajastamise näites on igal tegevusel algus- ja lõppaeg ning see on tähistatud numbriga. Tegevusi on kahte kategooriat:

1. Kaalutav tegevus: võrdlustegevus, mille põhjal mõõdetakse võimet sobitada rohkem ülejäänud tegevusi.
2. Ülejäänud tegevused: tegevused ühe või mitme indeksiga enne vaadeldavat tegevust.

Tegevuse teostamise maksumus on selle kestus, mis arvutatakse järgmiselt (lõpp – algus).

Ahne ulatus on lihtsalt järelejäänud tegevuste arv, mida saab vaadeldava tegevuse aja jooksul teha.

ArchiAhne lähenemisviisi

Step 1) Skannige tegevuskulude loendit, alustades indeksiga 0 kui vaadeldava indeksiga.

Step 2) Kui vaadeldava tegevuse lõppemise ajaks saab lõpetada rohkem tegevusi, otsige üles need ülejäänud tegevused.

Step 3) Kui rohkem tegevusi ei saa ajastada, saab praegusest allesjäänud tegevusest järgmine kaalutav tegevus. Korrake 1. ja 2. sammu uue kaalutava tegevusega. Kui tegevusi pole enam alles, minge 4. sammu juurde.

Step 4) Tagasta vaadeldavate indeksite ühend — need on aktiivsusindeksid, mis maksimeerivad läbilaskevõimet.

ArchiAhne lähenemisviisi

Code Selgitus

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

#define MAX_ACTIVITIES 12

Koodi selgitus:

1. Kaasatud päisefailid/klassid
2. Kasutaja poolt konfigureeritavate tegevuste maksimaalne arv.

using namespace std;

class TIME
{
    public:
    int hours;

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

Koodi selgitus:

1. Deklareerib voogedastustoimingute standardse nimeruumi.
2. Klassi määratlus TIME jaoks
3. Tunni ajatempel.
4. Vaikekonstruktor TIME
5. Tunnid muutuvad.

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

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

Koodi selgitus:

1. Klassi definitsioon funktsioonile Activity.
2. Ajatemplid, mis koos määravad kestuse.
3. Vaikimisi konstruktoris initsialiseeritakse kõik ajatemplid väärtuseks 0.

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

Koodi selgitus:

1. Planeerija klassi määratluse 1. osa.
2. considered_index on massiivi skannimise lähtepunkt.
3. init_indexi kasutatakse seadistamise ajal juhuslike ajatemplite määramiseks.
4. Tegevusobjektide massiiv eraldatakse dünaamiliselt uue operaatoriga.
5. Ajastatud pointer hoiab praegust ahnet tulemust.

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

Koodi selgitus:

1. Ajastaja konstruktor — klassi definitsiooni 2. osa.
2. considered_index tähistab praeguse skannimise algust.
3. Ahne ulatus on alguses määratlemata.

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;

Koodi selgitus:

1. For-tsükkel initsialiseerib iga ajastatud tegevuse algus- ja lõpptunnid.
2. Lähtestab algusaja.
3. Määrab lõppaja algustunnile vastavaks või hilisemaks.
4. Silumislause prindib eraldatud kestused.

	public:
   		 Activity * activity_select(int);
};

Koodi selgitus:

1. 4. osa — ajakava klassi definitsiooni viimane osa.
2. activity_select() võtab baasiks algindeksi ja jagab ahne ülesande alamprobleemideks.

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

1. Ulatuse lahendamise operaator (::) seob funktsiooni definitsiooni ajakava klassiga.
2. considered_index antakse edasi väärtuse kaupa ja greedy_extent initsialiseeritakse kohe sellele järgneva indeksi järgi.

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;
...

Koodi selgitus:

1. Põhiloogika — ahne ulatus on piiratud MAX_ACTIVITIES-iga.
2. Praeguse tegevuse algustundi kontrollitakse vaadeldava tegevuse lõputunni suhtes.
3. Kuni tingimus kehtib, prinditakse valikuline silumislause.
4. Ahne ulatus liigub seejärel tegevusmassiivis järgmisele indeksile.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Koodi selgitus:

1. Tingimuslik klausel kontrollib, kas kõik tegevused on kaetud.
2. Kui ei, siis algoritm alustab ahnet ülesannet praegusest indeksist uuesti – see on rekursiivne samm, mis jagab probleemi ahnelt osadeks.
3. Kui jah, siis kontroll naaseb helistajale ja ahnuse laiendamiseks pole enam ruumi.

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

Koodi selgitus:

1. Põhifunktsioon käivitab ajakava.
2. Uus ajastaja objekt on eksemplariga loodud.
3. Funktsioon activity_select() tagastab kutsujale tegevusviite, kui ahne ülesanne lõpeb.

Väljund:

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

Ahne tehnika piirangud

Ahne lähenemine ei sobi probleemide jaoks, mis nõuavad iga alamprobleemi jaoks optimaalset lahendust, näiteks sortimine.

Sellistel juhtudel võib ahne meetod olla vale – halvimal juhul annab see mitteoptimaalse lahenduse.

Ahnete algoritmide peamine puudus on see, et nad valivad teadmata, mis ootab ees praegust ahnet olekut.

Allolev diagramm illustreerib ahne meetodi seda puudust.

Siin puuna näidatud ahnes skaneerimises (kõrgem väärtus tähendab suuremat ahnust) valiks algoritm väärtusel 40 järgmisena 29 ja lõpetaks seejärel 12 juures, kokku 41.

Seevastu jaga-ja-valitse strateegia puhul järgneks 25-le 40, kokku tehes 65, mis on 24 punkti kõrgem kui kohalikul tasandil ahne valik.

Ahne näited Algorithms

Enamik võrgualgoritme tugineb ahnele lähenemisviisile. Levinud ahnete algoritmide näited hõlmavad järgmist:

• Primi minimaalse ulatuvpuu algoritm
• Rändmüügimehe probleem (ligikaudne)
• Graafiku kaardi värvimine
• Kruskali minimaalse ulatuvusega puu algoritm
• Dijkstra lühima tee algoritm
• Graafi tipu kate
• Seljakoti probleem
• Tööde järjestamine tähtaegadega

KKK