Näidetega selgitatud ahned algoritmid

Mis on ahne algoritm?

Võimalik, et olete siin mõningaid artikleid sirvides kuulnud paljudest algoritmilistest disainitehnikadest. Mõned neist on:

  • Toores jõud
  • Jaga ja võida
  • Ahne programmeerimine
  • Dünaamiline programmeerimine. Sellest artiklist saate teada, mis on ahne algoritm ja kuidas saate selle tehnika abil lahendada paljusid programmeerimisprobleeme, mis muidu ei tundu triviaalsed.

Kujutage ette, et lähete matkama ja teie eesmärk on jõuda võimalikult kõrgesse tippu. Kaart on teil juba enne alustamist olemas, kuid kaardil on näidatud tuhandeid võimalikke teid. Sa oled liiga laisk ja sul pole lihtsalt aega neid kõiki hinnata. Keerake kaarti! Alustasite matkamist lihtsa strateegiaga - olge ahne ja lühinägelik. Lihtsalt minge radadele, mis kalduvad kõige rohkem ülespoole. See tundub hea strateegia matkamiseks. Kuid kas see on alati parim?

Pärast reisi lõppu ja kogu keha valutamist ja väsimust vaatate esimest korda matkakaarti. Oh mu jumal! Seal on mudane jõgi, mille oleksin pidanud ületama, selle asemel, et pidevalt ülespoole kõndida. See tähendab, et ahne algoritm valib parima vahetu valiku ega mõtle oma valikuid kunagi uuesti läbi. Lahenduse optimeerimise mõttes tähendab see lihtsalt seda, et ahne lahendus püüab leida kohalikke optimaalseid lahendusi - mida võib olla palju - ja see võib globaalsest optimaalsest lahendusest ilma jääda.

Ametlik määratlus

Oletame, et teil on objektiivne funktsioon, mida tuleb antud punktis optimeerida (kas maksimeerida või minimeerida). Ahne algoritm teeb igal sammul ahneid valikuid, et tagada eesmärgi funktsiooni optimeerimine. Ahne algoritmil on optimaalse lahenduse arvutamiseks ainult üks lask, nii et see ei lähe kunagi tagasi ja muudab otsuse tagasi.

Ahnetel algoritmidel on mõned eelised ja puudused:

  • Ahne algoritmi (või isegi mitme ahne algoritmi) väljatöötamine probleemi jaoks on üsna lihtne. Ahnete algoritmide käitamisaja analüüsimine on üldjuhul palju lihtsam kui muude tehnikate puhul (näiteks Jaga ja võida). Jaga ja võida -tehnika jaoks pole selge, kas tehnika on kiire või aeglane. Selle põhjuseks on asjaolu, et igal rekursiooni tasandil väheneb nende suurus ja suureneb alamprobleemide arv.
  • Raske on see, et ahnete algoritmide jaoks peate korrektsuse probleemide mõistmiseks palju rohkem tööd tegema. Isegi õige algoritmi korral on raske tõestada, miks see õige on. Ahne algoritmi õigsuse tõendamine on pigem kunst kui teadus. See hõlmab palju loovust. Tavaliselt võib algoritmi väljamõtlemine tunduda tühine, kuid tõestada selle õigsust on hoopis teine ​​probleem.

Intervallide ajastamise probleem

Sukeldume huvitavasse probleemi, millega võite kokku puutuda peaaegu igas tööstusharus või igas elus. Mõned probleemi esinemisjuhud on järgmised:

  • Teile antakse N loengukava ühele päevale ülikoolis. Konkreetse loengu ajakava on kujul (s aeg, f aeg), kus s aeg tähistab selle loengu algusaega ja sarnaselt f aeg tähistab lõpuaega. Arvestades N loengukava loendit, peame valima päeva jooksul korraldatavate loengute maksimaalse kogumi nii, et   ükski loengutest ei kattuks, st kui meie valikus on loeng Li ja Lj, siis j algusaja > = i lõpuaeg või vastupidi .
  • Teie sõber töötab laagri nõustajana ja tema ülesandeks on korraldada laagriliste komplekti tegevusi. Üks tema plaanidest on järgmine minitriatloni harjutus: iga võistleja peab ujuma 20 ringi basseini, seejärel sõitma 10 miili rattaga, seejärel jooksma 3 miili.
  • Plaan on saata võistlejad järk-järgult välja järgmise reegli kaudu: võistlejad peavad basseini kasutama ükshaaval. Teisisõnu, kõigepealt ujub üks võistleja 20 ringi, saab välja ja hakkab rattaga sõitma.
  • Niipea kui see esimene inimene on basseinist väljas, alustab teine ​​võistleja 20 ringi ujumist; niipea, kui ta on väljas ja hakkab rattaga sõitma, hakkab kolmas võistleja ujuma jne.
  • Igal võistlejal on prognoositud ujumisaeg, prognoositav rattasõiduaeg ja prognoositud jooksuaeg. Teie sõber soovib otsustada triatloni ajakava: järjekord, milles järjestatakse võistlejate stardid.
  • Oletame, et ajakava täitmise aeg on kõige varasem aeg, mil kõik võistlejad lõpetavad triatloni kõigi kolme osaga, eeldades, et ajaprognoosid on täpsed. Mis on inimeste välja saatmise parim korraldus, kui keegi soovib, et kogu võistlus saaks võimalikult kiiresti läbi? Täpsemalt, andke tõhus algoritm, mis koostab ajakava, mille valmimisaeg on võimalikult väike

Loengute kavandamise probleem

Vaatame selle probleemi lahendamise erinevaid lähenemisviise.

Varaseim algusaeg kõigepealt,  st valige varaseima algusajaga intervall. Vaadake järgmist näidet, mis rikub selle lahenduse. See lahendus ebaõnnestus, kuna võib olla intervall, mis algab väga varakult, kuid see on väga pikk. See tähendab, et järgmine strateegia, mida võiksime proovida, oleks see, kui vaataksime kõigepealt väiksemaid intervalle.

Esmalt varaseim algusaeg

Esmalt väikseim intervall,  st lõpuks valite loengud nende üldise intervalli järgi, mis pole midagi muud kui nende   finish time - start time. Jällegi pole see lahendus õige. Vaadake järgmist juhtumit.

Esmalt lühim intervall

Näete selgelt, et lühim intervallloeng on keskel, kuid see pole siin optimaalne lahendus. Vaatame veel ühte probleemi lahendust, saades sellest lahendusest ülevaate.

Esmalt kõige vähem konfliktne intervall,  st peate vaatama intervalle, mis põhjustavad kõige vähem konflikte. Jällegi on meil näide, kus selline lähenemine ei leia optimaalset lahendust.

Kõigepealt kõige vähem konfliktne intervall

Diagramm näitab meile, et kõige vähem konfliktne intervall on keskel vaid 2 konfliktiga. Pärast seda saame valida ainult kaks intervalli kõige lõpus konfliktidega 3. Kuid optimaalne lahendus on valida 4 intervalli kõige kõrgemal tasemel.

Varem Lõpp-aeg enne . See on lähenemine, mis annab meile sellele probleemile alati optimaalseima lahenduse. Saime varasematest lähenemisviisidest palju teadmisi ja jõudsime lõpuks selle lähenemiseni. Sorteerime intervallid vastavalt nende viimistlusaja kasvavale järjekorrale ja seejärel hakkame intervalle valima juba eos. Selguse huvides vaadake järgmist pseudokoodi.

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 

Millal kasutame ahneid algoritme

Ahned algoritmid võivad aidata teil leida lahendusi paljudele näiliselt rasketele probleemidele. Ainus probleem nendega on see, et võite tulla õige lahenduseni, kuid ei pruugi õnnestuda kontrollida, kas see on õige. Kõigil ahnetel probleemidel on ühine omadus, et kohalik optima võib lõpuks viia globaalsete miinimumideni, kaalumata juba kaalutud valikute kogumit.

Ahned algoritmid aitavad meil lahendada palju erinevaid probleeme, näiteks:

Lühima tee probleem:

Minimaalne laienduspuu probleem graafikus

Huffmani kodeerimisprobleem

K keskuste probleem