Grådig algoritme - Greedy algorithm

Grådige algoritmer bestemmer det mindste antal mønter, der skal gives, mens der foretages ændringer. Dette er de trin, de fleste mennesker ville tage for at efterligne en grådig algoritme til at repræsentere 36 cent, der kun bruger mønter med værdier {1, 5, 10, 20}. Mønten med den højeste værdi, mindre end den tilbageværende ændring, der er gældende, er det lokale optimum. (Generelt kræver ændringsproblemet dynamisk programmering for at finde en optimal løsning; dog er de fleste valutasystemer, herunder euro og amerikanske dollar, særlige tilfælde, hvor den grådige strategi finder en optimal løsning.)

En grådig algoritme er enhver algoritme, der følger den problemløsende heuristik for at træffe det lokalt optimale valg på hvert trin. I mange problemer giver en grådig strategi ikke en optimal løsning, men en grådig heurist kan give lokalt optimale løsninger, der tilnærmer sig en globalt optimal løsning på rimelig tid.

For eksempel er en grådig strategi for det rejsende sælgers problem (som er af høj beregningskompleksitet) følgende heuristisk: "På hvert trin i rejsen skal du besøge den nærmeste ubesøgte by." Denne heurist har ikke til hensigt at finde den bedste løsning, men den afsluttes i et rimeligt antal trin; at finde en optimal løsning på et så komplekst problem kræver typisk urimeligt mange trin. Ved matematisk optimering løser grådige algoritmer optimalt kombinatoriske problemer med egenskaberne af matroider og giver konstant-faktor tilnærmelser til optimeringsproblemer med den submodulære struktur.

Specifikationer

Generelt har grådige algoritmer fem komponenter:

1. Et kandidatsæt, hvorfra der skabes en løsning
2. En udvælgelsesfunktion, der vælger den bedste kandidat, der skal føjes til løsningen
3. En gennemførlighedsfunktion, der bruges til at afgøre, om en kandidat kan bruges til at bidrage til en løsning
4. En objektiv funktion, som tildeler en løsning eller en delvis løsning en værdi og
5. En løsningsfunktion, som angiver, hvornår vi har opdaget en komplet løsning

Grådige algoritmer producerer gode løsninger på nogle matematiske problemer , men ikke på andre. De fleste problemer, de arbejder for, vil have to egenskaber:

Grådigt valg ejendom

Vi kan træffe det valg, der synes bedst i øjeblikket og derefter løse de delproblemer, der opstår senere. Valget foretaget af en grådig algoritme kan afhænge af de valg, der er truffet indtil nu, men ikke af fremtidige valg eller alle løsningerne på delproblemet. Det gør iterativt det ene grådige valg efter det andet og reducerer hvert givet problem til et mindre. Med andre ord genovervejer en grådig algoritme aldrig sine valg. Dette er den største forskel fra dynamisk programmering , som er udtømmende og garanteret finder løsningen. Efter hvert trin træffer dynamisk programmering beslutninger baseret på alle de beslutninger, der blev truffet i det foregående trin, og kan genoverveje det foregående stadies algoritmiske vej til løsningen.

Optimal understruktur

"Et problem udviser optimal understruktur, hvis en optimal løsning på problemet indeholder optimale løsninger på delproblemerne."

Tilfælde af fiasko

Eksempler på, hvordan en grådig algoritme ikke lykkes med at opnå den optimale løsning.

Fra A vil en grådig algoritme, der forsøger at finde maksimum ved at følge den største hældning, finde det lokale maksimum ved "m", uvidende om det globale maksimum ved "M".

For at nå den største sum vil den grådige algoritme ved hvert trin vælge, hvad der synes at være det optimale øjeblikkelige valg, så den vælger 12 i stedet for 3 på det andet trin og når ikke den bedste løsning, som indeholder 99.

Grådige algoritmer formår ikke at producere den optimale løsning til mange andre problemer og kan endda producere den unikke værst mulige løsning. Et eksempel er ovennævnte rejsende sælgers problem : For hvert antal byer er der en tildeling af afstande mellem byerne, for hvilke den nærmeste nabo-heuristik producerer den unikke værst tænkelige tur. For andre mulige eksempler, se horisonteffekt .

Typer

Grådige algoritmer kan karakteriseres som værende 'kortsynede' og også som 'ikke-genoprettelige. De er kun ideelle til problemer, der har en 'optimal understruktur'. På trods af dette er de bedst egnede algoritmer grådige for mange enkle problemer. Det er imidlertid vigtigt at bemærke, at den grådige algoritme kan bruges som en selektionsalgoritme til at prioritere muligheder inden for en søgning eller gren-og-bunden algoritme. Der er et par variationer af den grådige algoritme:

• Ren grådige algoritmer
• Ortogonale grådige algoritmer
• Afslappede grådige algoritmer

Teori

Grådige algoritmer har en lang historie med studier inden for kombinatorisk optimering og teoretisk datalogi . Grådige heuristikker vides at producere suboptimale resultater på mange problemer, og derfor er naturlige spørgsmål:

• For hvilke problemer udfører grådige algoritmer optimalt?
• For hvilke problemer garanterer grådige algoritmer en cirka optimal løsning?
• For hvilke problemer garanterer den grådige algoritme ikke en optimal løsning?

Der findes en stor mængde litteratur, der besvarer disse spørgsmål om generelle klasser af problemer, f.eks. Matroids , samt for specifikke problemer, f.eks. Dækning .

Matroider

En matroid er en matematisk struktur, der generaliserer forestillingen om lineær uafhængighed fra vektorrum til vilkårlige sæt. Hvis et optimeringsproblem har strukturen som en matroid, vil den passende grådige algoritme løse det optimalt.

Submodulære funktioner

En funktion, der er defineret på delsæt af et sæt , kaldes submodulær, hvis vi for hver det har det . ${\ displaystyle f}$${\ displaystyle \ Omega}$${\ displaystyle S, T \ subseteq \ Omega}$${\ displaystyle f (S)+f (T) \ geq f (S \ cup T)+f (S \ cap T)}$

Antag, at man vil finde et sæt, der maksimerer . Den grådige algoritme, som opbygger et sæt ved gradvist at tilføje det element, der øger mest ved hvert trin, producerer som output et sæt, der er mindst . Det vil sige, at grådige præsterer inden for en konstant faktor på lige så god som den optimale løsning. ${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle (1-1/e) \ max _ {X \ subseteq \ Omega} f (X)}$${\ displaystyle (1-1/e) \ ca. 0,63}$

Lignende garantier kan bevises, når yderligere begrænsninger, såsom kardinalitetsbegrænsninger, pålægges outputtet, selvom der ofte kræves små variationer på den grådige algoritme. Se en oversigt.

Andre problemer med garantier

Andre problemer, som den grådige algoritme giver en stærk garanti for, men ikke en optimal løsning, omfatter

• Sæt dæksel
• Det Steiner træ problem
• Belastningsbalancering
• Uafhængigt sæt

Mange af disse problemer har matchende lavere grænser; dvs. den grådige algoritme klarer sig ikke i værste fald bedre end garantien.

Ansøgninger

Grådige algoritmer formår typisk (men ikke altid) at finde den globalt optimale løsning, fordi de normalt ikke fungerer udtømmende på alle data. De kan forpligte sig til visse valg for tidligt og forhindre dem i at finde den bedste overordnede løsning senere. For eksempel finder alle kendte grådige farvelgoritmer til graffarvningsproblemet og alle andre NP-komplette problemer ikke konsekvent optimale løsninger. Ikke desto mindre er de nyttige, fordi de er hurtige til at finde på og ofte giver gode tilnærmelser til det optimale.

Hvis en grådig algoritme kan bevises at give det globale optimalt for en given problemklasse, bliver det typisk den valgte metode, fordi den er hurtigere end andre optimeringsmetoder som dynamisk programmering . Eksempler på sådanne grådige algoritmer er Kruskals algoritme og Prims algoritme til at finde minimumstræningstræer og algoritmen til at finde optimale Huffman -træer .

Grådige algoritmer vises i netværket routing så godt. Ved hjælp af grådig routing videresendes en besked til naboknuden, der er "tættest" på destinationen. Forestillingen om en nodes placering (og dermed "nærhed") kan bestemmes af dens fysiske placering, som i geografisk routing, der bruges af ad hoc -netværk . Placering kan også være en fuldstændig kunstig konstruktion som i lille verden routing og distribueret hashtabel .

Eksempler

• Den aktivitet udvælgelse Problemet er karakteristisk for denne klasse af problemer, hvor målet er at vælge det maksimale antal aktiviteter, der ikke kolliderer med hinanden.
• I Macintosh-computer spil Crystal Quest målet er at indsamle krystaller, på en måde, der svarer til den traveling salesman problem . Spillet har en demotilstand, hvor spillet bruger en grådig algoritme til at gå til enhver krystal. Den kunstige intelligens tager ikke højde for forhindringer, så demo -tilstanden slutter ofte hurtigt.
• Den matchende forfølgelse er et eksempel på en grådig algoritme, der anvendes på signalnærmer.
• En grådig algoritme finder den optimale løsning på Malfattis problem med at finde tre usammenhængende cirkler inden for en given trekant, der maksimerer det samlede areal af cirklerne; det formodes, at den samme grådige algoritme er optimal til et vilkårligt antal cirkler.
• En grådig algoritme bruges til at konstruere et Huffman -træ under Huffman -kodning, hvor det finder en optimal løsning.
• I indlæring af beslutningstræ bruges almindeligtvis grådige algoritmer, men de er ikke garanteret at finde den optimale løsning.
  • En populær sådan algoritme er ID3 -algoritmen til beslutningstræbygning.
• Dijkstra's algoritme og den tilhørende A* -søgningsalgoritme er verificerbart optimale grådige algoritmer til grafsøgning og korteste stifinding .
  • En* søgning er betinget optimal, hvilket kræver en " tilladt heuristik ", der ikke vil overvurdere stiomkostninger.
• Kruskals algoritme og Prim's algoritme er grådige algoritmer til konstruktion af minimumspændende træer i en given tilsluttet graf . De finder altid en optimal løsning, som generelt set ikke er unik.

Se også

Referencer

Kilder

eksterne links

• "Grådig algoritme" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Gave, Noah. "Python -grådigt mønteksempel" .