Ahne algoritmi - Greedy algorithm

Ahneat algoritmit määrittävät kolikoiden vähimmäismäärän muutoksen aikana. Nämä ovat vaiheita, joita useimmat ihmiset ottavat jäljitelläkseen ahneen algoritmin, joka edustaa 36 senttiä käyttäen vain kolikoita, joiden arvo on {1, 5, 10, 20}. Suurin arvoinen kolikko, joka on pienempi kuin jäljellä oleva velka, on paikallinen optimi. (Yleensä muutosongelma vaatii dynaamista ohjelmointia optimaalisen ratkaisun löytämiseksi; useimmat valuuttajärjestelmät, mukaan lukien euro ja Yhdysvaltain dollari, ovat kuitenkin erityistapauksia, joissa ahne strategia löytää optimaalisen ratkaisun.)

Ahne algoritmi on mikä tahansa algoritmi , joka seuraa ongelmanratkaisu heuristisen tehdä paikallisesti optimaalinen valinta kussakin vaiheessa. Monissa ongelmissa ahne strategia ei tuota optimaalista ratkaisua, mutta ahne heuristiikka voi tuottaa paikallisesti optimaalisia ratkaisuja, jotka lähentävät maailmanlaajuisesti optimaalista ratkaisua kohtuullisessa ajassa.

Esimerkiksi ahne strategia matkustavaan myyjäongelmaan (joka on erittäin monimutkainen laskennallisesti) on seuraava heuristinen: "Vieraile matkasi jokaisessa vaiheessa lähimmässä vieraamattomassa kaupungissa." Tämän heuristisen tarkoituksena ei ole löytää paras ratkaisu, mutta se päättyy kohtuullisessa määrin vaiheita; optimaalisen ratkaisun löytäminen tällaiseen monimutkaiseen ongelmaan vaatii tyypillisesti kohtuuttoman monta vaihetta. Matemaattisessa optimoinnissa ahneat algoritmit ratkaisevat optimaalisesti yhdistelmäongelmat, joilla on matroidien ominaisuuksia, ja antavat vakio-kerroin-likiarvot submodulaarisen rakenteen optimointitehtäville.

Erityispiirteet

Yleensä ahneilla algoritmeilla on viisi osaa:

1. Ehdokasjoukko, josta luodaan ratkaisu
2. Valintatoiminto, joka valitsee parhaan ehdokkaan, joka lisätään ratkaisuun
3. Toteutettavuusfunktio, jota käytetään määrittämään, voidaanko ehdokasta käyttää ratkaisun edistämiseen
4. Tavoitefunktio, joka antaa arvon ratkaisulle tai osittaiselle ratkaisulle, ja
5. Ratkaisutoiminto, joka ilmaisee, kun olemme löytäneet täydellisen ratkaisun

Ahneat algoritmit tuottavat hyviä ratkaisuja joihinkin matemaattisiin ongelmiin , mutta eivät muihin. Useimmilla ongelmilla, joilla he työskentelevät, on kaksi ominaisuutta:

Ahne valinta omaisuutta

Voimme tehdä sen valinnan, joka tällä hetkellä näyttää parhaalta, ja ratkaista myöhemmin syntyvät osaongelmat. Ahnean algoritmin tekemä valinta voi riippua tähän mennessä tehdyistä valinnoista, mutta ei tulevista valinnoista tai kaikista osaongelman ratkaisuista. Se tekee iteratiivisesti yhden ahneen valinnan toisensa jälkeen, pienentäen jokaisen annetun ongelman pienemmäksi. Toisin sanoen ahne algoritmi ei koskaan harkitse uudelleen valintojaan. Tämä on tärkein ero dynaamiseen ohjelmointiin , joka on tyhjentävä ja joka varmasti löytää ratkaisun. Jokaisen vaiheen jälkeen dynaaminen ohjelmointi tekee päätöksiä kaikkien edellisessä vaiheessa tehtyjen päätösten perusteella ja voi harkita uudelleen edellisen vaiheen algoritmista polkua ratkaisuun.

Optimaalinen rakenne

"Ongelmalla on optimaalinen alarakenne, jos optimaalinen ratkaisu ongelmaan sisältää optimaaliset ratkaisut osaongelmiin."

Epäonnistumisen tapaukset

Esimerkkejä siitä, kuinka ahne algoritmi ei pysty saavuttamaan optimaalista ratkaisua.

A: sta alkaen ahne algoritmi, joka yrittää löytää maksimin suurinta kaltevuutta seuraten, löytää paikallisen maksimin "m": stä, unohtamatta globaalia maksimia "M": ssä.

Suurimman summan saavuttamiseksi ahne algoritmi valitsee jokaisessa vaiheessa parhaan mahdollisen välittömän valinnan, joten se valitsee toisessa vaiheessa 12 sijasta 3 eikä saavuta parasta ratkaisua, joka sisältää 99.

Ahneat algoritmit eivät pysty tuottamaan optimaalista ratkaisua moniin muihin ongelmiin ja voivat jopa tuottaa ainutlaatuisen pahimman mahdollisen ratkaisun. Yksi esimerkki on edellä mainittu matkustava myyjäongelma : jokaiselle kaupunkimäärälle on määritetty etäisyydet niiden kaupunkien välillä, joille lähin naapuri heuristiikka tuottaa ainutlaatuisen pahimman mahdollisen kiertueen. Katso muita mahdollisia esimerkkejä kohdasta horisontin vaikutus .

Tyypit

Ahneita algoritmeja voidaan luonnehtia "lyhytnäköisiksi" ja myös "palautumattomiksi". Ne ovat ihanteellisia vain ongelmille, joilla on "optimaalinen alarakenne". Tästä huolimatta moniin yksinkertaisiin ongelmiin parhaiten soveltuvat algoritmit ovat ahneita. On kuitenkin tärkeää huomata, että ahne algoritmia voidaan käyttää valintaalgoritmina priorisoimaan haun vaihtoehdot tai haarautunut algoritmi. Ahnealla algoritmilla on muutamia muunnelmia:

• Puhtaat ahneat algoritmit
• Ortogonaaliset ahneat algoritmit
• Rento ahne algoritmit

Teoria

Ahneilla algoritmeilla on pitkä historia yhdistelmäoptimoinnista ja teoreettisesta tietojenkäsittelytieteestä . Ahneiden heuristiikkojen tiedetään tuottavan epäoptimaalisia tuloksia monista ongelmista, joten luonnollisia kysymyksiä ovat:

• Mihin ongelmiin ahneat algoritmit toimivat optimaalisesti?
• Mihin ongelmiin ahneat algoritmit takaavat suunnilleen optimaalisen ratkaisun?
• Mihin ongelmiin ahne algoritmi ei takaa optimaalista ratkaisua?

Näihin kysymyksiin on olemassa laaja kirjallisuus, joka vastaa yleisiin ongelmaluokkiin, kuten matroideihin , sekä erityisiin ongelmiin, kuten sarjaan .

Matroidit

Matroid on matemaattinen rakenne, joka yleistää käsitettä lineaarinen riippumattomuus välillä vektoriavaruuksia mielivaltaisiin sarjaa. Jos optimointitehtävässä on matroidin rakenne, asianmukainen ahne algoritmi ratkaisee sen optimaalisesti.

Submodulaariset toiminnot

Joukon osajoukoille määritettyä funktiota kutsutaan submodulaariseksi, jos jokaisella meillä on se . ${\ displaystyle f}$${\ displaystyle \ Omega}$${\ displaystyle S, T \ subseteq \ Omega}$${\ displaystyle f (S)+f (T) \ geq f (S \ cup T)+f (S \ cap T)}$

Oletetaan, että halutaan löytää joukko, joka maksimoi . Ahne algoritmi, joka rakentaa joukon lisäämällä vähitellen eniten kussakin vaiheessa kasvavaa elementtiä , tuottaa ulostulona vähintään joukon . Toisin sanoen ahne toimii yhtä hyvin kuin optimaalinen ratkaisu. ${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle (1-1/e) \ max _ {X \ subseteq \ Omega} f (X)}$${\ displaystyle (1-1/e) \ noin 0,63}$

Samankaltaiset takuut ovat todistettavissa, kun tuotokselle asetetaan lisärajoituksia, kuten kardinaalisuusrajoituksia, vaikka ahnean algoritmiin vaaditaan usein pieniä muutoksia. Katso yleiskatsaus.

Muita takuisiin liittyviä ongelmia

Muita ongelmia, joihin ahne algoritmi antaa vahvan takuun, mutta ei optimaalista ratkaisua, ovat

• Aseta kansi
• Steiner Tree ongelma
• Kuormituksen tasapainoittaminen
• Itsenäinen setti

Monilla näistä ongelmista on vastaavat alarajat; eli ahne algoritmi ei toimi pahimmassa tapauksessa paremmin kuin takuu.

Sovellukset

Ahneat algoritmit eivät yleensä (mutta ei aina) löydä maailmanlaajuisesti optimaalista ratkaisua, koska ne eivät yleensä toimi tyhjentävästi kaikessa datassa. He voivat sitoutua tiettyihin valintoihin liian aikaisin estäen heitä löytämään parhaan kokonaisratkaisun myöhemmin. Esimerkiksi kaikki tunnetut ahne väritys algoritmeja kaavio värjäys ongelma ja kaikki muut NP-täydellisiä ongelmat eivät aina löytää optimaalisia ratkaisuja. Siitä huolimatta ne ovat hyödyllisiä, koska ne keksivät nopeasti ja antavat usein hyviä likimääräisiä arvoja optimaaliseen.

Jos ahne algoritmi voidaan osoittaa tuottavan globaalin optimin tietylle ongelmaluokalle, siitä tulee tyypillisesti valintamenetelmä, koska se on nopeampi kuin muut optimointimenetelmät, kuten dynaaminen ohjelmointi . Esimerkkejä tällaisista ahneista algoritmeista ovat Kruskalin algoritmi ja Primin algoritmi vähimmäispituuspuiden löytämiseksi ja algoritmi optimaalisten Huffman -puiden löytämiseksi .

Ahneat algoritmit näkyvät myös verkon reitityksessä . Ahneella reitityksellä viesti välitetään naapurisolmuun, joka on "lähimpänä" kohdetta. Solmun sijainnin käsite (ja siten "läheisyys") voidaan määrittää sen fyysisen sijainnin perusteella, kuten ad hoc -verkkojen käyttämässä maantieteellisessä reitityksessä . Sijainti voi myös olla täysin keinotekoinen rakenne, kuten pienen maailman reitityksessä ja hajautetussa taulukossa .

Esimerkkejä

• Aktiivisuus valinta ongelma on tyypillistä tämän luokan ongelmia, jossa tavoitteena on valita maksimimäärä toimintoja, jotka eivät ole ristiriidassa keskenään.
• Vuonna Macintosh-tietokone pelin Crystal Quest tavoitteena on kerätä kiteitä, tavalla, joka on samanlainen kuin kauppamatkustajan ongelma . Pelissä on demotila, jossa peli käyttää ahneita algoritmeja jokaiseen kristalliin. Tekoälyä ei selitä esteitä, joten demotila usein päättyy nopeasti.
• Sovitus harjoittaminen on esimerkki ahne algoritmi sovelletaan signaalin approksimaatio.
• Ahne algoritmi löytää optimaalisen ratkaisun Malfatin ongelmaan löytää kolme irrotettua ympyrää tietyn kolmion sisältä, jotka maksimoivat ympyröiden kokonaispinta -alan; oletetaan, että sama ahne algoritmi on optimaalinen mille tahansa ympyrälle.
• Ahneella algoritmilla rakennetaan Huffman -puu Huffman -koodauksen aikana, jolloin se löytää optimaalisen ratkaisun.
• Vuonna päätöspuuta oppimista , ahne algoritmeja käytetään yleisesti, mutta ne eivät välttämättä löytää optimaalinen ratkaisu.
  • Yksi suosittu tällainen algoritmi on ID3 -algoritmi päätöspuun rakentamiseen.
• Dijkstran algoritmi ja siihen liittyvä A* -hakualgoritmi ovat todistettavasti optimaalisia ahneita algoritmeja kuvaajahakuun ja lyhyimmän polun löytämiseen .
  • * Haku on ehdollisesti optimaalinen, mikä edellyttää " hyväksyttävää heuristiikkaa ", joka ei yliarvioi reitin kustannuksia.
• Kruskalin algoritmi ja Primin algoritmi ovat ahneita algoritmeja tietyn yhdistetyn kuvaajan vähimmäispituuspuiden muodostamiseksi . He löytävät aina optimaalisen ratkaisun, joka ei välttämättä ole ainutlaatuinen yleensä.

Katso myös

Viitteet

Lähteet

Ulkoiset linkit

• "Ahne algoritmi" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Lahja, Noah. "Esimerkki ahneesta kolikosta" .