Ahne algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4.7.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Ahne algoritmi on algoritmi , joka koostuu paikallisesti optimaalisten päätösten tekemisestä kussakin vaiheessa olettaen, että myös lopullinen ratkaisu osoittautuu optimaaliseksi. Tiedetään, että jos tehtävän rakenne on annettu matroidilla , niin ahnealgoritmin soveltaminen antaa globaalin optimin.

Jos algoritmin yleinen optimaalisuus on lähes aina totta, se on yleensä parempi kuin muut optimointitekniikat, kuten dynaaminen ohjelmointi .

Soveltamisehdot

Ahneen algoritmin soveltuvuuden arvioimiselle tietyn ongelman ratkaisemiseen ei ole olemassa yleisiä kriteerejä, mutta ahneilla algoritmeilla ratkaistuilla ongelmilla on kaksi ominaisuutta: ensinnäkin niihin soveltuu Greedy Choice -periaate ja toiseksi niillä on Optimaalisuus osatehtäville. omaisuutta .

The Greedy Choice Principle

Ahneen valinnan periaatteen sanotaan pätevän optimointiongelmaan , jos paikallisesti optimaalisten valintojen sarja tuottaa globaalisti optimaalisen ratkaisun. Tyypillisessä tapauksessa optimiteetin todistaminen noudattaa seuraavaa kaaviota:

On todistettu, että ahne valinta ensimmäisessä vaiheessa ei sulje polkua optimaaliseen ratkaisuun: jokaiselle ratkaisulle on toinen ratkaisu, joka on yhdenmukainen ahneen valinnan kanssa eikä ole huonompi kuin ensimmäinen.
On osoitettu, että ensimmäisessä vaiheessa ahneen valinnan jälkeen syntyvä aliongelma on samanlainen kuin alkuperäinen.
Päättely päättyy induktioon .

Optimaalisuus osatehtäville

Ongelmalla sanotaan olevan optimaalisuusominaisuus aliongelmien johtamiseksi tulokseen , jos ongelman optimaalinen ratkaisu sisältää optimaaliset ratkaisut kaikille sen aliongelmille. Esimerkiksi patenttivaatimusten valintaongelmassa voidaan huomata, että jos on optimaalinen vaatimusjoukko, joka sisältää väitteen numero 1, niin on optimaalinen vaatimusjoukko pienemmälle vaatimusjoukolle , joka koostuu niistä vaatimuksista, joille . $A$ ${\displaystyle A'=A\setminus \left\{1\right\))$ $S'$ ${\displaystyle s_{i}\leqslant f_{1))$

Esimerkkejä

Kolikonvaihto

Tehtävä. Tietyn valtion rahajärjestelmä koostuu kolikoista, joiden nimellisarvo on . Määrä on laskettava liikkeeseen mahdollisimman pienellä määrällä kolikoita. $a_{1}=1<a_{2}<...<a_{n}$ $S$

Ahne algoritmi tämän ongelman ratkaisemiseksi on seuraava. Suurin mahdollinen määrä nimellisarvoisia kolikoita otetaan : . Samalla tavalla saamme kuinka monta pienemmän arvon kolikkoa tarvitaan jne. $a_n$ $x_{n}=\lfloor S/a_{n}\rfloor$

Tähän ongelmaan ahne algoritmi ei aina anna optimaalista ratkaisua, vaan vain joillekin, kanonisille rahajärjestelmille, kuten USA:ssa käytetyille (1, 5, 10, 25 senttiä). Ei-kanonisilla järjestelmillä ei ole tätä ominaisuutta. Joten esimerkiksi 24 kopikan määrä 1, 5 ja 7 kopikan kolikoilla. ahne algoritmi vaihtaa näin: 7 kopekkaa. - 3 kpl, 1 kop. - 3 kappaletta, kun taas oikea ratkaisu on 7 kopekkaa. - 2 kpl, 5 kopekkaa. - 2 kpl. [yksi]

Sovellusten valinta

Muotoilu nro 1. Hakemukset tunneiden johtamiseen tietylle yleisölle annetaan. Jokaisessa hakemuksessa on ilmoitettu oppitunnin alku ja loppu ( ja -: nnelle hakemukselle). Pyyntöjen risteyksen tapauksessa vain yksi niistä voidaan täyttää. Sovellukset numeroilla ja ovat yhteisiä, jos välit ja eivät leikkaa (eli tai ). Sovellusten valinnan tehtävänä on kerätä mahdollisimman monta toistensa kanssa yhdistettyjä hakemuksia. $n$ $si}$ $f_{i}$ $i$ $i$ $j$ $[s_{i},f_{i})$ $[s_{j},f_{j})$ ${\displaystyle f_{i}\leqslant s_{j))$ ${\displaystyle f_{j}\leqslant s_{i))$

Muotoilu nro 2. Konferenssissa , jotta epäviralliseen viestintään jäisi enemmän aikaa, eri osiot murskattiin eri yleisöille. Äärimmäisen laaja-alainen tiedemies haluaa osallistua useille luennoille, jotka pidetään eri osastoissa. Jokaisen raportin alku ja loppu tunnetaan. Määritä enimmäismäärä raportteja, joihin voit osallistua. $si}$ $f_{i}$

Tässä on ahne algoritmi, joka ratkaisee tämän ongelman. Samalla oletetaan, että sovellukset on järjestetty kasvavassa päättymisajan järjestyksessä. Jos näin ei ole, voit lajitella ne ajoissa ; tilaukset, joilla on sama päättymisaika, tehdään satunnaisessa järjestyksessä. $O(n\log n)$

Activity-Selector(s,f)

$n\vasen$ length[s]
$A\leftarrow\left\{1\right\}$
$j\leftarrow 1$
for $i\leftarrow 2$ to $n$ do if $s_{i}\geq f_{j}$ then $A\leftarrow A\cup \{i\}$ $j\leftarrow i$
return A

Luokkien alun ja lopun taulukot syötetään tämän algoritmin tuloon. Joukko A koostuu valittujen pyyntöjen numeroista ja j on viimeisen pyynnön numero. Ahne algoritmi etsii järjestystä, joka alkaa aikaisintaan j : nnen lopussa, sisällyttää sitten löydetyn järjestyksen A :een ja j antaa sen numeron. Näin ollen joka kerta valitsemme sen (ei vielä alkanut) oppitunnin, jonka loppuun on vähiten aikaa jäljellä.

Algoritmi toimii , eli lajittelu ja näytteenotto. Jokaisessa vaiheessa valitaan paras ratkaisu. Osoittakaamme, että lopulta saamme optimaalisen. $O(n\log n+n)$

Todiste . Huomaa, että kaikki tilaukset lajitellaan ei-laskevaan päättymisaikaan. Hakemus numero 1 sisältyy luonnollisesti optimiin (jos ei, niin korvaamme varhaisimman järjestyksen optimissa sillä, tämä ei pahenna sitä). Heittämällä pois kaikki sovellukset, jotka ovat ristiriidassa ensimmäisen kanssa, saamme alkuperäisen ongelman vähemmällä sovelluksella. Väittelemällä induktiolla pääsemme optimaaliseen ratkaisuun samalla tavalla.

Muut ahneet algoritmit

Huffman-algoritmi (adaptiivinen algoritmi aakkosten optimaaliseen etuliitekoodaukseen minimaalisella redundanssilla).
Kruskalin algoritmi (hae graafista minimipainoista virittävää puuta).
Primin algoritmi (etsi minimipainon virittävä puu yhdistetystä graafista).

Ahneiden algoritmien yleistys on Rado-Edmonds-algoritmi .

Ongelmat, joissa ahneet algoritmit eivät anna optimaalista ratkaisua

Useille NP-luokkaan kuuluville ongelmille ahneet algoritmit eivät tarjoa optimaalista ratkaisua. Nämä sisältävät:

matkustavan myyjän ongelma ;
kuvaaja minimaalinen väritysongelma ;
ongelma graafin jakamisesta osagraafiksi ;
suurimman klikkauksen valinnan ongelma ;
tehtävien ajoittaminen .

Siitä huolimatta useissa ongelmissa ahneet algoritmit antavat hyviä likimääräisiä ratkaisuja.

Katso myös

Ahneus (säännölliset lausekkeet)
Kategoria: Ahneella algoritmilla ratkaistuja ongelmia

Muistiinpanot

↑ X. Cai. Canonical Coin Systems for Change-Making Problems // Proceedings of Ninth International Conference on Hybrid Intelligent Systems. - 2009. - S. 499-504 . - doi : 10.1109/HIS.2009.103 . - arXiv : 0809.0400 .

Kirjallisuus

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Luku 16. Greedy Algorithms // Algorithms: Construction and Analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Linkit

Greedy Algorithms Videotallennus luennolla Tietojenkäsittelytiedekeskuksessa

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokittelu ongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-verkko Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG