Ahneita algoritmeja, jotka on selitetty esimerkeillä

Mikä on ahne algoritmi?

Olet ehkä kuullut monista algoritmisista suunnittelutekniikoista siivilöitessäsi joitain artikkeleita täällä. Jotkut niistä ovat:

  • Raaka voima
  • Jaa ja valloita
  • Ahne ohjelmointi
  • Dynaaminen ohjelmointi muutamia mainitakseni. Tässä artikkelissa opit, mikä on ahne algoritmi ja kuinka voit käyttää tätä tekniikkaa ratkaisemaan monia ohjelmointiongelmia, jotka muuten eivät näytä merkityksettömiltä.

Kuvittele, että olet menossa patikointiin ja tavoitteesi on saavuttaa korkein mahdollinen huippu. Sinulla on jo kartta ennen aloittamista, mutta kartalla on tuhansia mahdollisia polkuja. Olet liian laiska ja sinulla ei yksinkertaisesti ole aikaa arvioida niitä kaikkia. Kierrä kartta! Aloitit vaeltaa yksinkertaisella strategialla - ole ahne ja lyhytnäköinen. Ota vain polkuja, jotka kaltevat eniten ylöspäin. Tämä näyttää hyvältä retkeilystrategialta. Mutta onko se aina paras?

Kun matka on päättynyt ja koko kehosi on kipeä ja väsynyt, katsot vaelluskarttaa ensimmäistä kertaa. Herranjumala! Siellä on mutainen joki, jonka minun olisi pitänyt ylittää sen sijaan, että käveltäisimme ylöspäin. Tämä tarkoittaa, että ahne algoritmi valitsee parhaan välittömän valinnan eikä koskaan harkitse valintojaan uudelleen. Ratkaisun optimoinnin kannalta tämä tarkoittaa yksinkertaisesti sitä, että ahne ratkaisu yrittää löytää paikallisia optimaalisia ratkaisuja - joita voi olla monia - ja saattaa menettää maailmanlaajuisen optimaalisen ratkaisun.

Muodollinen määritelmä

Oletetaan, että sinulla on tavoitefunktio, joka on optimoitava (joko maksimoitava tai minimoitava) tietyssä pisteessä. Ahne algoritmi tekee ahneita valintoja jokaisessa vaiheessa varmistaakseen, että tavoitefunktio on optimoitu. Ahneilla algoritmeilla on vain yksi laukaus optimaalisen ratkaisun laskemiseksi niin, että se ei koskaan palaa takaisin ja kumoaa päätöksen.

Ahneilla algoritmeilla on joitain etuja ja haittoja:

  • On melko helppoa keksiä ahne algoritmi (tai jopa useita ahneita algoritmeja) ongelmaa varten. Ahneiden algoritmien ajoajan analysointi on yleensä paljon helpompaa kuin muille tekniikoille (kuten Jaa ja hallitse). Jaa ja hallitse -tekniikalle ei ole selvää, onko tekniikka nopea vai hidas. Tämä johtuu siitä, että jokaisella rekursiotasolla koko pienenee ja alaongelmien määrä kasvaa.
  • Vaikeinta on, että ahneiden algoritmien tekemiseksi sinun on tehtävä paljon enemmän työtä ymmärtääksesi virheitä. Jopa oikealla algoritmilla on vaikea todistaa, miksi se on oikea. Ahneiden algoritmien oikeellisuuden osoittaminen on enemmän taidetta kuin tiedettä. Siihen liittyy paljon luovuutta. Yleensä algoritmin keksiminen saattaa tuntua vähäpätöiseltä, mutta sen todistaminen oikeaksi on aivan erilainen ongelma.

Intervalliaikataulu

Sukelletaan mielenkiintoiseen ongelmaan, jonka voit kohdata melkein millä tahansa toimialalla tai kaikilla elämänaloilla. Jotkut ongelman esiintymät ovat seuraavat:

  • Sinulle annetaan N sarja luentoja yhdelle päivälle yliopistossa. Tietyn luennon aikataulu on muodoltaan (s aika, f aika), jossa s aika edustaa luennon alkamisaikaa ja vastaavasti f aika edustaa lopetusaikaa. Kun on annettu luettelo N luentoaikataulusta, meidän on valittava päivän aikana pidettävien luentojen enimmäismäärä siten, että   mikään luennoista ei mene päällekkäin eli jos luento Li ja Lj sisältyvät valintamme, j: n aloitusaika > = i: n päättymisaika tai päinvastoin .
  • Ystäväsi työskentelee leirineuvojana, ja hän vastaa leiriläisjoukkojen toiminnan järjestämisestä. Yksi hänen suunnitelmistaan ​​on seuraava minitriatloniharjoittelu: jokaisen kilpailijan on uitava 20 kierrosta uima-allasta, sitten pyöräiltävä 10 mailia, sitten suoritettava 3 mailia.
  • Suunnitelma on lähettää kilpailijat porrastetusti seuraavan säännön avulla: Kilpailijoiden on käytettävä uima-allasta yksi kerrallaan. Toisin sanoen ensin yksi kilpailija ui 20 kierrosta, nousee ulos ja alkaa pyöräillä.
  • Heti kun tämä ensimmäinen henkilö on poissa uima-altaasta, toinen kilpailija alkaa uida 20 kierrosta; heti kun hän on ulkona ja alkaa pyöräillä, kolmas kilpailija alkaa uida ja niin edelleen.
  • Jokaisella kilpailijalla on ennustettu uintiaika, arvioitu pyöräilyaika ja ennustettu ajoaika. Ystäväsi haluaa päättää triathlon-aikataulun: järjestys, jossa järjestetään kilpailijoiden lähtö.
  • Oletetaan, että aikataulun valmistumisaika on aikaisin aika, jolloin kaikki kilpailijat valmistuvat triatlonin kaikilla kolmella osalla, olettaen, että aikaennusteet ovat tarkat. Mikä on paras järjestys ihmisten lähettämiseen, jos halutaan koko kilpailun päättyvän mahdollisimman pian? Tarkemmin sanottuna anna tehokas algoritmi, joka tuottaa aikataulun, jonka valmistumisaika on mahdollisimman pieni

Luennon ajoitusongelma

Katsotaanpa tämän ongelman ratkaisemisen eri lähestymistapoja.

Aikaisin  aloitusaika ensin eli valitse aika, jolla on aikaisin aloitusaika. Katsokaa seuraavaa esimerkkiä, joka rikkoo tämän ratkaisun. Tämä ratkaisu epäonnistui, koska voi olla aika, joka alkaa hyvin aikaisin, mutta se on hyvin pitkä. Tämä tarkoittaa sitä, että seuraava strategia, jota voisimme kokeilla, olisi se, että tarkastelemme ensin pienempiä välejä.

Aikaisin aloitusaika ensin

Pienin intervalli ensin  eli päätät luennot niiden yleisen aikavälin mukaan, joka ei ole muuta kuin heidän   finish time - start time. Jälleen tämä ratkaisu ei ole oikea. Katso seuraava tapaus.

Lyhin aika ensin

Voit selvästi nähdä, että lyhin intervalliluento on keskellä, mutta se ei ole optimaalinen ratkaisu tässä. Tarkastellaan vielä toista ratkaisua tähän ongelmaan ja saadaan oivalluksia tästä ratkaisusta.

Pienin ristiriitainen intervalli ensin  eli sinun tulee tarkastella välejä, jotka aiheuttavat vähiten ristiriitoja. Jälleen kerran meillä on esimerkki, jossa tämä lähestymistapa ei löydä optimaalista ratkaisua.

Vähiten ristiriitainen intervalli ensin

Kaavio osoittaa meille, että vähiten ristiriitainen väli on keskellä oleva vain 2 ristiriitaa. Sen jälkeen voimme valita vain kaksi väliä lopusta konflikteineen 3. Mutta optimaalinen ratkaisu on valita 4 aikaväliä ylimmälle tasolle.

Aikaisin viimeistelyaika ensin . Tämä on lähestymistapa, joka antaa meille aina optimaalisen ratkaisun tähän ongelmaan. Saimme paljon oivalluksia aiemmista lähestymistavoista ja päädyimme lopulta tähän lähestymistapaan. Lajittelemme intervallit niiden lopetusajan kasvavan järjestyksen mukaan ja aloitamme sitten intervallien valitsemisen alusta alkaen. Katso seuraava näennäkoodi lisää selkeyttä.

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 

Milloin käytämme ahneita algoritmeja

Ahneiden algoritmien avulla voit löytää ratkaisuja moniin näennäisesti vaikeisiin ongelmiin. Ainoa ongelma heidän kanssaan on, että saatat löytää oikean ratkaisun, mutta et ehkä pysty tarkistamaan, onko se oikea. Kaikilla ahneilla ongelmilla on yhteinen ominaisuus, jonka paikallinen optima voi lopulta johtaa globaaleihin minimeihin harkitsematta jo harkittuja valintoja.

Ahneiden algoritmien avulla voimme ratkaista monia erilaisia ​​ongelmia, kuten:

Lyhin polkuongelma:

Pienin ulottuva puuongelma kaaviossa

Huffmanin koodausongelma

K-keskusten ongelma