Alkatīgs algoritms ar piemēriem: mantkārīga metode & Pieeja

Satura rādītājs:

Anonim

Kas ir mantkārīgs algoritms?

Jo mantkārīgs algoritmu kopums resursi ir rekursīvi sadalīta, pamatojoties uz maksimālo, tūlītēja pieejamība šī resursa jebkurā konkrētajā posmā izpildi.

Lai atrisinātu problēmu, pamatojoties uz mantkārīgu pieeju, ir divi posmi

  1. Vienumu saraksta skenēšana
  2. Optimizācija

Šie mantkārīgā algoritma apmācībā šie posmi ir aplūkoti paralēli masīva sadalīšanas gaitā.

Lai saprastu mantkārīgo pieeju, jums būs nepieciešamas praktiskas zināšanas par rekursiju un konteksta maiņu. Tas palīdz saprast koda izsekošanu. Jūs varat definēt mantkārīgo paradigmu ar saviem nepieciešamajiem un pietiekamajiem izteikumiem.

Mantkārīgo paradigmu nosaka divi nosacījumi.

  • Katram pakāpeniskam risinājumam problēma jāstrukturē tā vislabāk pieņemtā risinājuma virzienā.
  • Pietiek, ja problēmas strukturēšanu var apturēt ar noteiktu skaitu mantkārīgu soļu.

Turpinot teoretizēšanu, aprakstīsim vēsturi, kas saistīta ar mantkārīgas meklēšanas pieeju.

Šajā mantkārīgā algoritma apmācībā jūs uzzināsiet:

  • Alkatīgu algoritmu vēsture
  • Alkatīgas stratēģijas un lēmumi
  • Alkatīgās pieejas raksturojums
  • Kāpēc jāizmanto mantkārīgā pieeja?
  • Kā atrisināt aktivitātes izvēles problēmu
  • Mantkārīgās pieejas arhitektūra
  • Alkatīgu algoritmu trūkumi

Alkatīgu algoritmu vēsture

Šeit ir svarīgs alkatīgu algoritmu orientieris:

  • Alkatīgi algoritmi tika konceptualizēti daudziem grafu soļu algoritmiem 1950. gados.
  • Esdžers Džikstra algoritmu konceptualizēja, lai radītu minimālu aptverošu koku. Viņa mērķis bija saīsināt maršrutu garumu Nīderlandes galvaspilsētā Amsterdamā.
  • Tajā pašā desmitgadē Prim un Kruskal sasniedza optimizācijas stratēģijas, kuru pamatā bija ceļa izmaksu samazināšana nosvērtajos maršrutos.
  • 70. gados amerikāņu pētnieki Kormens, Rivests un Šteins savā klasiskajā ievadā algoritmu grāmatā piedāvāja mantkārīgu risinājumu rekursīvu pārstrukturēšanu.
  • Mantkārīgās meklēšanas paradigma tika reģistrēta kā cita veida optimizācijas stratēģija NIST ierakstos 2005. gadā.
  • Līdz datumam protokoli, kas darbojas tīmeklī, piemēram, atvērtais īsākais ceļš vispirms (OSPF) un daudzi citi tīkla pakešu komutācijas protokoli, izmanto mantkārīgu stratēģiju, lai samazinātu tīklā pavadīto laiku.

Alkatīgas stratēģijas un lēmumi

Loģika tās visvieglākajā formā tika vārīta līdz “mantkārīgai” vai “ne alkatīgai”. Šos apgalvojumus definēja pieeja, kas tika izmantota, lai virzītos uz priekšu katrā algoritma posmā.

Piemēram, Džikstra algoritms izmantoja pakāpenisku mantkārīgu stratēģiju, kas identificēja resursdatorus internetā, aprēķinot izmaksu funkciju. Izmaksu funkcijas atgrieztā vērtība noteica, vai nākamais ceļš ir "mantkārīgs" vai "ne alkatīgs".

Īsāk sakot, algoritms pārstāj būt alkatīgs, ja kādā posmā tas sper soli, kas nav vietējs mantkārīgs. Mantkārīgās problēmas apstājas, bez citas alkatības iespējas.

Alkatīgās pieejas raksturojums

Mantkārīgās metodes algoritma svarīgās īpašības ir šādas:

  • Ir sakārtots resursu saraksts ar izmaksām vai vērtības attiecinājumiem. Šie kvantitatīvi izsaka sistēmas ierobežojumus.
  • Jūs izmantosiet maksimālo resursu daudzumu laikā, kad tiek piemērots ierobežojums.
  • Piemēram, problēmu plānošanas problēmu gadījumā resursu izmaksas ir stundās, un darbības jāveic secīgā secībā.

Kāpēc jāizmanto mantkārīgā pieeja?

Šeit ir mantkārīgas pieejas izmantošanas iemesli:

  • Alkatīgajai pieejai ir daži kompromisi, kas var padarīt to piemērotu optimizācijai.
  • Viens no nozīmīgākajiem iemesliem ir nekavējoties panākt iespējami iespējamo risinājumu. Aktivitātes atlases problēmā (Paskaidrots tālāk), ja pirms pašreizējās darbības pabeigšanas var veikt vairāk darbību, šīs darbības var veikt vienā un tajā pašā laikā.
  • Vēl viens iemesls ir sadalīt problēmu rekursīvi, pamatojoties uz nosacījumu, un nav jāapvieno visi risinājumi.
  • Aktivitātes atlases problēmā "rekursīvās dalīšanas" solis tiek sasniegts, vienreiz skenējot vienumu sarakstu un ņemot vērā noteiktas darbības.

Kā atrisināt aktivitātes izvēles problēmu

Darbību plānošanas piemērā katrai darbībai ir norādīts sākuma un beigu laiks. Katra darbība atsaucei tiek indeksēta ar skaitli. Ir divas aktivitāšu kategorijas.

  1. uzskatāma darbība : ir darbība, kas ir atsauce, no kuras tiek analizēta spēja veikt vairāk nekā vienu atlikušo darbību.
  2. atlikušās aktivitātes: darbības vienā vai vairākos indeksos pirms attiecīgās darbības.

Kopējais ilgums norāda darbības veikšanas izmaksas. Tas nozīmē, ka (finišs - sākums) mums norāda darbības ilgumu kā darbības cenu.

Jūs uzzināsiet, ka mantkārīgais apmērs ir atlikušo darbību skaits, ko varat veikt attiecīgās darbības laikā.

Mantkārīgās pieejas arhitektūra

1. SOLIS)

Skenējiet aktivitātes izmaksu sarakstu, sākot ar indeksu 0 kā uzskatīto indeksu.

2. SOLIS)

Kad līdz laikam var pabeigt vairāk darbību, attiecīgā darbība ir pabeigta, sāciet meklēt vienu vai vairākas atlikušās darbības.

3. SOLIS)

Ja atlikušo darbību vairs nav, pašreizējā atlikusī darbība kļūst par nākamo aplūkoto darbību. Atkārtojiet 1. un 2. darbību ar jauno izskatīto darbību. Ja nav atlikušas citas darbības, pārejiet pie 4. darbības.

4. SOLIS)

Atgrieziet aplūkoto indeksu savienību. Šie ir aktivitātes indeksi, kas tiks izmantoti, lai maksimāli palielinātu caurlaidspēju.

Alkatīgās pieejas arhitektūra

Kods Paskaidrojums

#include#include#include#define MAX_ACTIVITIES 12

Koda skaidrojums:

  1. Iekļautie galvenes faili / klases
  2. Maksimālais lietotāja nodrošināto darbību skaits.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

Koda skaidrojums:

  1. Straumēšanas darbību nosaukumvieta.
  2. TIME klases definīcija
  3. Stundas laika zīmogs.
  4. TIME noklusējuma konstruktors
  5. Stundu mainīgais.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Koda skaidrojums:

  1. Klases definīcija no darbības
  2. Laika zīmogi, kas nosaka ilgumu
  3. Visi laika zīmogi tiek inicializēti uz 0 noklusējuma konstruktorā
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

Koda skaidrojums:

  1. Plānotāja klases definīcijas 1. daļa.
  2. Uzskatītais indekss ir masīva skenēšanas sākumpunkts.
  3. Inicializācijas indekss tiek izmantots nejaušu laika zīmogu piešķiršanai.
  4. Aktivitātes objektu masīvs tiek dinamiski piešķirts, izmantojot jauno operatoru.
  5. Plānotais rādītājs nosaka pašreizējo alkatības bāzes vietu.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Koda skaidrojums:

  1. Plānotāja konstruktors - plānotāja klases definīcijas 2. daļa.
  2. Apskatītais indekss nosaka pašreizējās skenēšanas pašreizējo sākumu.
  3. Pašreizējais mantkārīgais apmērs sākumā nav noteikts.
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);}… …

Koda skaidrojums:

  1. A for loop, lai inicializētu katras pašreiz plānotās darbības sākuma un beigu stundas.
  2. Sākuma laika inicializēšana.
  3. Beigu laika inicializēšana vienmēr pēc sākuma stundas vai tieši tajā.
  4. Atkļūdošanas paziņojums, lai izdrukātu piešķirtos ilgumus.
public:Activity * activity_select(int);};

Koda skaidrojums:

  1. 4. daļa - plānotāja klases definīcijas pēdējā daļa.
  2. Aktivitātes atlases funkcija kā sākumpunktu ņem sākuma punkta indeksu un alkatīgos meklējumus sadala mantkārīgos apakšproblēmos.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Izmantojot darbības jomas izšķirtspējas operatoru (: :), tiek sniegta funkcijas definīcija.
  2. Aplūkotais indekss ir indekss, ko izsauc pēc vērtības. Greedy_extent ir inicializēts tikai indekss aiz attiecīgā indeksa.
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++;}… …

Koda skaidrojums:

  1. Galvenā loģika - mantkārīgais apjoms ir ierobežots līdz aktivitāšu skaitam.
  2. Pašreizējās aktivitātes sākuma stundas tiek pārbaudītas kā ieplānotas, pirms tiek pabeigta attiecīgā darbība (norādīta pēc attiecīgā indeksa).
  3. Cik vien iespējams, tiek izdrukāts atkļūdošanas paziņojums.
  4. Pāriet uz nākamo darbības masīva indeksu
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

Koda skaidrojums:

  1. Nosacītā pārbaude, vai ir ietvertas visas darbības.
  2. Ja nē, jūs varat restartēt savu mantkārīgo, izmantojot pašreizējo indeksu. Šis ir rekursīvs solis, kas alkatīgi sadala problēmas izklāstu.
  3. Ja jā, tas atgriežas zvanītājam bez iespējas paplašināt alkatību.
int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

Koda skaidrojums:

  1. Galvenā funkcija, ko izmanto, lai izsauktu plānotāju.
  2. Tiek izveidots jauns plānotājs.
  3. Aktivitātes atlases funkcija, kas atgriež darbības veida rādītāju, atgriežas zvanītājam pēc mantkārīgā meklējuma beigām.

Izeja:

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

Alkatīgu algoritmu trūkumi

Tas nav piemērots mantkārīgām problēmām, kur nepieciešams risinājums katrai apakšproblēmai, piemēram, šķirošanai.

Šādās mantkārīgu algoritmu prakses problēmās mantkārīgā metode var būt nepareiza; sliktākajā gadījumā pat noved pie neoptimāla risinājuma.

Tāpēc alkatīgu algoritmu trūkums ir nezināšana, kas gaida pašreizējo mantkārīgo stāvokli.

Zemāk ir parādīts mantkārīgā metodes trūkums:

Alkatīgajā skenēšanā, kas šeit parādīta kā koks (augstāka vērtība ir lielāka kāre), algoritma stāvoklis vērtībā: 40, visticamāk, ņems nākamo vērtību 29. Turklāt tā meklējumi beidzas ar 12. Tas sasniedz vērtību 41.

Tomēr, ja algoritms izvēlējās mazoptimālu ceļu vai pieņēma iekarošanas stratēģiju. tad pēc 25 sekotu 40, un kopējais izmaksu uzlabojums būtu 65, kas kā neoptimāls lēmums tiek vērtēts par 24 punktiem augstāk.

Alkatīgu algoritmu piemēri

Lielākā daļa tīkla algoritmu izmanto mantkārīgu pieeju. Šeit ir saraksts ar dažiem mantkārīgu algoritmu piemēriem:

  • Prima minimālais aptverošā koka algoritms
  • Ceļojošā pārdevēja problēma
  • Grafiks - kartes krāsošana
  • Kruskaļa minimālais aptverošā koka algoritms
  • Dižkstra minimālais aptverošā koka algoritms
  • Grafiks - virsotnes vāks
  • Muguras problēma
  • Darba plānošanas problēma

Kopsavilkums:

Apkopojot, rakstā tika definēta mantkārīgā paradigma, parādīts, kā alkatīga optimizācija un rekursija var palīdzēt jums iegūt vislabāko risinājumu līdz punktam. Mantkārīgais algoritms tiek plaši izmantots problēmu risināšanas lietojumprogrammā daudzās valodās kā alkatīgs algoritms Python, C, C #, PHP, Java utt. Mantkārīgā algoritma piemēra aktivitāšu atlase tika aprakstīta kā stratēģiska problēma, kas varētu sasniegt maksimālu caurlaidspēju, izmantojot mantkārīgo pieeja. Galu galā tika izskaidroti mantkārīgās pieejas izmantošanas trūkumi.