Grådig algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 4. juli 2021; verifikation kræver 1 redigering .

En grådig algoritme er en algoritme, der består i at træffe lokalt optimale beslutninger på hvert trin, forudsat at den endelige løsning også viser sig at være optimal. Det er kendt, at hvis strukturen af problemet er givet af en matroide , så vil anvendelsen af den grådige algoritme give et globalt optimum.

Hvis den globale optimalitet af en algoritme næsten altid er tilfældet, foretrækkes den normalt frem for andre optimeringsteknikker såsom dynamisk programmering .

Betingelser for anvendelse

Der er ikke noget generelt kriterium for at vurdere anvendeligheden af en grådig algoritme til at løse et specifikt problem, men problemer, der løses af grådige algoritmer, har to funktioner: For det første er Greedy Choice-princippet anvendeligt på dem , og for det andet har de Optimality for subtasks ejendom .

The Greedy Choice-princippet

Det grådige valg-princip siges at gælde for et optimeringsproblem, hvis rækkefølgen af lokalt optimale valg giver en globalt optimal løsning. I et typisk tilfælde følger beviset for optimalitet følgende skema:

Det er bevist, at det grådige valg på det første trin ikke lukker vejen til den optimale løsning: For hver løsning er der en anden løsning, som er i overensstemmelse med det grådige valg og ikke er værre end den første.
Det er vist, at underproblemet, der opstår efter det grådige valg ved det første trin, ligner det oprindelige.
Begrundelsen ender med induktion .

Optimalitet til underopgaver

Et problem siges at have optimalitetsegenskaben for delproblemer til at udlede et resultat , hvis den optimale løsning på problemet indeholder de optimale løsninger for alle dets delproblemer. For eksempel, i problemet med valget af krav , kan man bemærke, at hvis er det optimale sæt af krav, der indeholder krav nummer 1, så er det optimale sæt af krav for et mindre sæt af krav , bestående af de krav, for hvilke . $EN$ $A'=A\setminus \left\{1\right\}$ $S'$ ${\displaystyle s_{i}\leqslant f_{1))$

Eksempler

Møntveksling

En opgave. Det monetære system i en bestemt stat består af mønter med en pålydende værdi på . Det er påkrævet at udstede beløbet med det mindst mulige antal mønter. $a_{1}=1<a_{2}<...<a_{n}$ $S$

Den grådige algoritme til at løse dette problem er som følger. Det størst mulige antal pålydende mønter tages : . På samme måde får vi, hvor mange mønter af en mindre pålydende værdi, der skal til mv. $a_n$ $x_{n}=\lgulv S/a_{n}\rgulv$

Til dette problem giver den grådige algoritme ikke altid den optimale løsning, men kun for nogle, kaldet kanoniske , monetære systemer, såsom dem, der bruges i USA (1, 5, 10, 25 cents). Ikke-kanoniske systemer har ikke denne egenskab. Så for eksempel mængden af 24 kopek med mønter på 1, 5 og 7 kopek. grådige algoritmeudvekslinger som denne: 7 kopek. - 3 stk., 1 kop. - 3 stk, mens den korrekte løsning er 7 kopek. - 2 stk., 5 kopek. - 2 stk. [en]

Valg af applikationer

Formulering nr. 1. Ansøgninger om at lede undervisning i et bestemt publikum gives. I hver applikation er begyndelsen og slutningen af lektionen angivet ( og for den -. applikation). I tilfælde af skæring af anmodninger kan kun én af dem opfyldes. Ansøgninger med tal og er fælles, hvis intervallerne og ikke skærer (det vil sige eller ). Opgaven med at vælge ansøgninger er at indsamle det maksimale antal ansøgninger, der er fælles med hinanden. $n$ $s_{i}$ $f_{i}$ $jeg$ $jeg$ $j$ $[s_{i},f_{i})$ $[s_{j},f_{j})$ ${\displaystyle f_{i}\leqslant s_{j))$ ${\displaystyle f_{j}\leqslant s_{i))$

Formulering nr. 2. På konferencen , for at afsætte mere tid til uformel kommunikation, blev forskellige sektioner smadret til forskellige målgrupper. En videnskabsmand med ekstremt brede interesser ønsker at deltage i flere foredrag i forskellige sektioner. Begyndelsen og slutningen af hver rapport er kendt. Bestem det maksimale antal rapporter, du kan deltage i. $s_{i}$ $f_{i}$

Her er en grådig algoritme, der løser dette problem. Samtidig antager vi, at ansøgningerne er ordnet i rækkefølge efter stigende sluttid. Hvis dette ikke er tilfældet, så kan du sortere dem i tide ; ordrer med samme sluttidspunkt placeres i tilfældig rækkefølge. $O(n\log n)$

Activity-Selector(s,f)

$n\venstrepil$ length[s]
$A\venstrepil\venstre\{1\højre\}$
$j\venstrepil 1$
for $i\venstrepil 2$ to $n$ do if $s_{i}\geq f_{j}$ then $A\venstrepil A\kop \{i\}$ $j\venstrepil i$
return A

Arrays af begyndelsen og slutningen af klasser føres til input af denne algoritme. Sættet A består af numrene på de valgte anmodninger, og j er nummeret på den sidste anmodning. Den grådige algoritme søger efter en rækkefølge, der ikke starter tidligere end slutningen af j -th, og inkluderer derefter den fundne rækkefølge i A , og j tildeler dens nummer. Således vælger vi hver gang den (endnu ikke startet) lektion, indtil slutningen af hvilken der er mindst tid tilbage.

Algoritmen fungerer til , det vil sige sortering plus sampling. Ved hvert trin vælges den bedste løsning. Lad os vise, at vi i sidste ende får det optimale. $O(n\log n+n)$

Bevis . Bemærk, at alle ordrer er sorteret i ikke-faldende sluttidspunkt. Ansøgning nummer 1 er naturligvis inkluderet i det optimale (hvis ikke, så erstatter vi den tidligste rækkefølge i det optimale med det, det vil ikke gøre det værre). Ved at smide alle applikationer ud, der modsiger den første, får vi det oprindelige problem med færre applikationer. Argumenterer vi ved induktion , når vi frem til den optimale løsning på samme måde.

Andre grådige algoritmer

Huffman-algoritme (adaptiv algoritme til optimal præfikskodning af alfabetet med minimal redundans).
Kruskals algoritme (søg efter et spændingstræ med minimumvægt i en graf).
Prims algoritme (søg efter et minimumvægtspændende træ i en forbundet graf).

En generalisering af grådige algoritmer er Rado-Edmonds algoritme .

Problemer hvor grådige algoritmer ikke giver en optimal løsning

For en række problemer, der tilhører NP-klassen , giver grådige algoritmer ikke en optimal løsning. Disse omfatter:

Ikke desto mindre giver grådige algoritmer i en række problemer gode omtrentlige løsninger.

Se også

Grådighed (regulære udtryk)
Kategori: Problemer løst af den grådige algoritme

Noter

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

Litteratur

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 16. Greedy Algorithms // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Links

Greedy Algorithms Videooptagelse af et foredrag på Computer Science Center

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG