Mohó algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 4-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A mohó algoritmus egy olyan algoritmus, amely minden szakaszban helyileg optimális döntéseket hoz, feltételezve, hogy a végső megoldás is optimálisnak bizonyul. Ismeretes, hogy ha a feladat szerkezetét egy matroid adja meg , akkor a mohó algoritmus alkalmazása globális optimumot ad.

Ha egy algoritmus globális optimalitása szinte mindig fennáll, akkor általában előnyben részesítik más optimalizálási technikákkal, például a dinamikus programozással szemben .

Alkalmazási feltételek

A mohó algoritmusok konkrét probléma megoldására való alkalmazhatóságának értékelésére nincs általános kritérium, azonban a mohó algoritmusok által megoldott problémáknak két jellemzője van: egyrészt alkalmazható rájuk a Mohó választási elv , másrészt az Optimalitás részfeladatokhoz. ingatlan .

A kapzsi választás elve

A mohó választási elvről azt mondják, hogy akkor érvényesül egy optimalizálási probléma , ha a lokálisan optimális választások sorozata globálisan optimális megoldást ad. Tipikus esetben az optimalitás bizonyítása a következő sémát követi:

Bebizonyosodott, hogy a mohó választás az első lépésnél nem zárja el az utat az optimális megoldás felé: minden megoldáshoz létezik egy másik, a mohó választással összhangban lévő, az elsőnél nem rosszabb megoldás.
Megmutatjuk, hogy az első lépésben a mohó választás után fellépő részprobléma hasonló az eredetihez.
Az érvelés indukcióval ér véget .

Optimalitás részfeladatokhoz

Egy feladatról azt mondjuk, hogy rendelkezik az eredmény levezetéséhez szükséges részproblémák optimálissági tulajdonságával, ha a probléma optimális megoldása tartalmazza az összes részprobléma optimális megoldását. Például az igénypontok kiválasztásának problémájában észrevehető, hogy ha az 1. számú igénypontot tartalmazó optimális igényponthalmaz, akkor az optimális igényponthalmaz egy kisebb igényponthalmazhoz , amely azokból az állításokból áll, amelyekre . $A$ ${\displaystyle A'=A\setminus \left\{1\right\))$ $S'$ ${\displaystyle s_{i}\leqslant f_{1))$

Példák

Érmecsere

Egy feladat. Egy adott állam pénzrendszere a címletű érmékből áll . Az összeget a lehető legkisebb érmével kell kibocsátani. $a_{1}=1<a_{2}<...<a_{n}$ $S$

A probléma megoldásának mohó algoritmusa a következő. A lehető legtöbb címletű érmét veszik fel : . Ugyanígy megkapjuk, hogy hány kisebb címletű érmére van szükség stb. $a_n$ $x_{n}=\lfloor S/a_{n}\rfloor$

Erre a problémára a mohó algoritmus nem mindig adja meg az optimális megoldást, hanem csak néhány, úgynevezett kanonikus monetáris rendszerre, mint amilyen az USA-ban használatos (1, 5, 10, 25 cent). A nem kanonikus rendszerek nem rendelkeznek ezzel a tulajdonsággal. Így például a 24 kopejka összeg 1, 5 és 7 kopekás érmékkel. mohó algoritmus cserék így: 7 kopejka. - 3 db, 1 kop. - 3 db, míg a helyes megoldás 7 kopejka. - 2 db, 5 kopejka. - 2 db. [egy]

Alkalmazások kiválasztása

1. számú megfogalmazás. Jelentkezéseket adunk egy meghatározott közönség körében órák levezetésére. Minden alkalmazásban fel van tüntetve a lecke eleje és vége ( és a -edik alkalmazásnál). A kérések metszéspontja esetén csak az egyik teljesíthető. A és számokkal rendelkező alkalmazások közösek, ha a és intervallumok nem metszik egymást (vagyis vagy ). A pályázatok kiválasztásának feladata, hogy összegyűjtse a maximális számú, egymással egyesített pályázatot. $n$ $s_{i}$ $f_{i}$ $én$ $én$ $j$ $[s_{i},f_{i})$ $[s_{j},f_{j})$ ${\displaystyle f_{i}\leqslant s_{j))$ ${\displaystyle f_{j}\leqslant s_{i))$

2. megfogalmazás. A konferencián annak érdekében, hogy több időt fordítsanak az informális kommunikációra, különböző szekciókat zúztak szét a különböző közönségekhez. Egy rendkívül széles érdeklődési körrel rendelkező tudós több, különböző szekciókban tartott előadáson szeretne részt venni. Minden jelentés eleje és vége ismert. Határozza meg, hogy hány jelentést vehet igénybe. $s_{i}$ $f_{i}$

Itt van egy mohó algoritmus, amely megoldja ezt a problémát. Ugyanakkor feltételezzük, hogy az alkalmazások sorrendje növekvő befejezési idő szerint történik. Ha nem ez a helyzet, akkor időben rendezheti őket ; az azonos befejezési idejű rendelések véletlenszerű sorrendben kerülnek feladásra. $O(n\log n)$

Activity-Selector(s,f)

$n\balra$ 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

Az osztályok eleje és vége tömbje ennek az algoritmusnak a bemenetére kerül. Az A halmaz a kiválasztott kérések számaiból áll, j pedig az utolsó kérés száma. A mohó algoritmus olyan sorrendet keres, amely legkorábban j -edik végén kezdődik, majd a talált sorrendet tartalmazza A -ban, és j hozzárendeli a számát. Így minden alkalommal azt a (még el nem indult) órát választjuk, aminek a végéig a legkevesebb idő van hátra.

Az algoritmus a , azaz a rendezés és a mintavételezés esetén működik. Minden lépésnél kiválasztják a legjobb megoldást. Mutassuk meg, hogy végül az optimumot kapjuk. $O(n\log n+n)$

Bizonyíték . Ne feledje, hogy minden rendelés nem csökkenő befejezési idő szerint rendeződik. Az 1-es számú pályázat nyilván benne van az optimumban (ha nem, akkor az optimumban lévő legkorábbi sorrendet pótoljuk vele, ettől nem lesz rosszabb). Az elsőnek ellentmondó összes alkalmazást kidobva kevesebb alkalmazással kapjuk meg az eredeti problémát. Az indukcióval érvelve hasonló módon jutunk el az optimális megoldáshoz.

Egyéb mohó algoritmusok

Huffman algoritmus (adaptív algoritmus az ábécé optimális előtagkódolásához minimális redundanciával).
Kruskal-algoritmus (minimális súlyú feszítőfa keresése gráfban).
Prim algoritmusa (minimális súlyú átívelő fa keresése egy összefüggő gráfban).

A mohó algoritmusok általánosítása a Rado-Edmonds algoritmus .

Problémák, ahol a mohó algoritmusok nem adnak optimális megoldást

Számos, az NP osztályba tartozó problémára a mohó algoritmusok nem adnak optimális megoldást. Ezek tartalmazzák:

Ennek ellenére számos problémára a mohó algoritmusok jó közelítő megoldásokat adnak.

Lásd még

Kapzsiság (reguláris kifejezések)
Kategória: A mohó algoritmus által megoldott problémák

Jegyzetek

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

Irodalom

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 16. fejezet. Mohó algoritmusok // Algorithms: Construction and Analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .

Linkek

Torkos algoritmusok Videófelvétel a Számítástechnikai Központban tartott előadásról

Gépi tanulás és adatbányászat
Feladatok	Osztályozási feladat Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellegyüttesek Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-háló Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG