Ce este un algoritm lacom?

Este posibil să fi auzit despre o mulțime de tehnici de proiectare algoritmică în timp ce citiți câteva dintre articolele de aici. Unii dintre ei sunt:

  • Forta bruta
  • Diviza și cuceri
  • Programare lacomă
  • Programare dinamică pentru a numi câteva. În acest articol, veți afla despre ce este un algoritm lacom și cum puteți utiliza această tehnică pentru a rezolva o mulțime de probleme de programare care altfel nu par banale.

Imaginați-vă că mergeți la drumeții și obiectivul dvs. este să atingeți cel mai înalt vârf posibil. Aveți deja harta înainte de a începe, dar există mii de căi posibile afișate pe hartă. Ești prea leneș și pur și simplu nu ai timp să le evaluezi pe fiecare. Înșurubați harta! Ai început să faci drumeții cu o strategie simplă – fii lacom și miop. Luați doar cărări care înclină cel mai mult în sus. Aceasta pare o strategie bună pentru drumeții. Dar este întotdeauna cel mai bun?

După ce călătoria s-a încheiat și tot corpul este dureros și obosit, te uiți pentru prima dată la harta de drumeții. O Doamne! Există un râu noroios pe care ar fi trebuit să-l traversez, în loc să merg în continuare în sus. Aceasta înseamnă că un algoritm lacom alege cea mai bună alegere imediată și nu își reconsideră niciodată alegerile. În ceea ce privește optimizarea unei soluții, aceasta înseamnă pur și simplu că soluția lacomă va încerca să găsească soluții optime locale – care pot fi multe – și ar putea pierde o soluție optimă globală.

Definiție formală

Să presupunem că aveți o funcție obiectivă care trebuie optimizată (fie maximizată, fie minimizată) la un moment dat. Un algoritm Greedy face alegeri lacome la fiecare pas pentru a se asigura că funcția obiectivă este optimizată. Algoritmul Greedy are o singură fotografie pentru a calcula soluția optimă, astfel încât să nu revină niciodată și să inverseze decizia.

Algoritmii lacomi au câteva avantaje și dezavantaje:

  • Este destul de ușor să veniți cu un algoritm lacom (sau chiar cu mai mulți algoritmi lacomi) pentru o problemă. Analiza timpului de rulare pentru algoritmii lacomi va fi în general mult mai ușoară decât pentru alte tehnici (cum ar fi Divide and conquer). Pentru tehnica Împărțiți și cuceriți, nu este clar dacă tehnica este rapidă sau lentă. Acest lucru se datorează faptului că la fiecare nivel de recursivitate, dimensiunea lui devine mai mică și numărul de subprobleme crește.
  • Partea dificilă este că pentru algoritmii lacomi trebuie să lucrați mult mai mult pentru a înțelege problemele de corectitudine. Chiar și cu algoritmul corect, este greu de demonstrat de ce este corect. A demonstra că un algoritm lacom este corect este mai mult o artă decât o știință. Implică multă creativitate. De obicei, a veni cu un algoritm poate părea a fi banal, dar dovedirea faptului că este de fapt corectă, este o problemă cu totul diferită.

Problemă de programare a intervalelor

Să ne scufundăm într-o problemă interesantă pe care o puteți întâlni în aproape orice industrie sau orice domeniu al vieții. Unele cazuri ale problemei sunt următoarele:

  • Vi se oferă un set de N programe de prelegeri pentru o singură zi la o universitate. Programul pentru o anumită prelegere este de forma (s timp, f timp) unde s timpul reprezintă ora de început pentru acea prelegere și în mod similar f timpul reprezintă timpul de finalizare. Având în vedere o listă de N orare de prelegeri, trebuie să selectăm un set maxim de prelegeri care să se desfășoare în timpul zilei astfel încât niciuna dintre prelegeri nu se suprapune una cu cealaltă, adică dacă prelegerea Li și Lj sunt incluse în selecția noastră, atunci ora de începere a j> = timpul de finalizare al lui i sau invers .
  • Prietenul tău lucrează ca consilier de tabără și el este responsabil de organizarea activităților pentru un set de rulote. Unul dintre planurile sale este următorul exercițiu de mini-triatlon: fiecare concurent trebuie să înoate 20 de ture de piscină, apoi să meargă cu 10 mile, apoi să alerge 3 mile.
  • Planul este de a trimite concurenții în mod eșalonat, prin următoarea regulă: concurenții trebuie să folosească piscina pe rând. Cu alte cuvinte, primul concurent înoată cele 20 de ture, iese și începe ciclismul.
  • De îndată ce această primă persoană iese din piscină, un al doilea concurent începe să înoate cele 20 de ture; imediat ce el sau ea este afară și începe ciclismul, un al treilea concurent începe să înoate și așa mai departe.
  • Fiecare concurent are un timp de înot proiectat, un timp de ciclism proiectat și un timp de rulare proiectat. Prietenul tău dorește să decidă asupra unui program pentru triatlon: o ordine în care să ordonezi începerea concurenților.
  • Să presupunem că timpul de finalizare al unui program este cel mai devreme moment în care toți concurenții vor fi terminati cu toate cele trei picioare ale triatlonului, presupunând că proiecțiile de timp sunt corecte. Care este cea mai bună comandă pentru trimiterea oamenilor, dacă se dorește ca întreaga competiție să se termine cât mai curând posibil? Mai precis, dați un algoritm eficient care produce un program al cărui timp de finalizare este cât mai mic posibil

Problema de programare a prelegerilor

Să ne uităm la diferitele abordări pentru rezolvarea acestei probleme.

Primul timp de începere adică selectați intervalul care are cel mai devreme timp de început. Aruncați o privire la următorul exemplu care rupe această soluție. Această soluție a eșuat, deoarece ar putea exista un interval care începe foarte devreme, dar care este foarte lung. Aceasta înseamnă că următoarea strategie pe care am putea să o încercăm ar fi aceea în care privim mai întâi intervale mai mici.

Primul timp de începere

Cel mai mic interval mai întâi adică ajungi să selectezi prelegerile în ordinea intervalului lor general, care nu este altceva decât al lor finish time - start time . Din nou, această soluție nu este corectă. Uită-te la următorul caz.

Cel mai scurt interval mai întâi

Puteți vedea clar că cea mai scurtă prelegere la intervale este cea din mijloc, dar aceasta nu este soluția optimă aici. Să analizăm încă o altă soluție pentru această problemă care derivă din această soluție.

Mai întâi intervalul cel mai puțin conflictual adică ar trebui să te uiți la intervale care cauzează cel mai mic număr de conflicte. Din nou, avem un exemplu în care această abordare nu reușește să găsească o soluție optimă.

Mai întâi intervalul cel mai puțin conflictual

Diagrama ne arată că intervalul cel mai puțin conflictiv este cel din mijloc cu doar 2 conflicte. După aceea, putem alege cele două intervale doar la capete, cu conflicte 3 fiecare. Dar soluția optimă este să alegeți cele 4 intervale la cel mai înalt nivel.

Primul timp de finisare mai devreme. Aceasta este abordarea care ne oferă întotdeauna cea mai optimă soluție la această problemă. Am obținut o mulțime de perspective din abordările anterioare și, în cele din urmă, am abordat această abordare. Sortăm intervalele în funcție de ordinea crescândă a timpilor de finisare și apoi începem să selectăm intervalele de la bun început. Uitați-vă la următorul pseudo cod pentru mai multă claritate.

function interval_scheduling_problem(requests)
    schedule gets {}
    while requests is not yet empty
        choose a request i_r in requests that has the lowest finishing time
        schedule gets schedule cup {i_r}
        delete all requests in requests that are not compatible with i_r
    end
    return schedule
end

Când folosim algoritmi Greedy

Algoritmii lacomi vă pot ajuta să găsiți soluții la o mulțime de probleme aparent dure. Singura problemă cu acestea este că s-ar putea să veniți cu soluția corectă, dar este posibil să nu puteți verifica dacă este cea corectă. Toate problemele lacome împărtășesc o proprietate comună pe care o optimă locală o poate duce în cele din urmă la valori minime globale fără a reconsidera setul de alegeri deja luate în considerare.

Algoritmii lacomi ne ajută să rezolvăm o mulțime de diferite tipuri de probleme, cum ar fi:

Cea mai scurtă problemă de cale:

Problemă minimă a arborelui de întindere într-un grafic

Problema de codificare Huffman

Problema centrelor K