Introduktion til grådig algoritme
En strategi, der bruges til at løse problemer. Grådig algoritme betragtes som en af de metoder, der bruges til at løse problemer. Denne problemløsende kætter går med til at tage et valg, der synes bedst i det øjeblik. Denne tilgang bruges bedst til at løse optimeringsproblemer. Optimeringsproblemer kan defineres som problemer, der kræver enten minimale eller maksimale resultater. En grådig algoritme er en enkel og mest enkel tilgang, der kan bruges til at opnå en optimal løsning.
Hvad er grådig algoritme?
Grådig algoritme er en algoritmisk strategi, der bruges til at tage det bedste valgfri valg på et meget lille trin, mens det til sidst udsendes en globalt optimal løsning. Denne algoritme vælger den bedste løsning, der er mulig på det tidspunkt uden hensyntagen til nogen konsekvenser. Grådig metode siger, at problemet skal løses i trin, hvor hvert enkelt input betragtes, da dette input er muligt. Da denne tilgang kun fokuserer på et øjeblikkeligt resultat uden hensyntagen til det større billede, betragtes det som grådigt.
Definition af kernekonceptet
Indtil nu ved vi, hvad en grådig algoritme er, og hvorfor kaldes den sådan. Nedenstående pegepunkter får dig til at forstå den grådige algoritme på en bedre måde. På nuværende tidspunkt har det været meget tydeligt, at den grådige algoritme kun fungerer, når der er et problem; Ikke desto mindre er denne tilgang kun anvendelig, hvis vi har en betingelse eller begrænsning for dette problem.
Typer af problemer
- Minimeringsproblem: Det er let at få en løsning på et problem, da alle betingelserne er opfyldt. Når dette problem kræver et minimumsresultat, kaldes det imidlertid et minimeringsproblem.
- Maksimeringsproblem: Et problem, der kræver det maksimale resultat, kaldes maksimeringsproblemet.
- Optimeringsproblem: Et problem kaldes optimeringsproblem, når det kræver enten minimale eller maksimale resultater.
Typer af løsninger
- Gennemførbar løsning: Nu når et problem opstår, har vi mange plausible løsninger på dette problem. Alligevel tager vi i betragtning af betingelsen, der er angivet til dette problem, løsninger, der opfylder den givne betingelse. Sådanne løsninger, der hjælper os med at få resultater, der opfylder den givne betingelse, kaldes en gennemførlig løsning .
- Optimal løsning: En løsning kaldes optimal, når den allerede er gennemførlig og når målet med problemet. det bedste resultat. Dette mål kan enten være et minimum eller maksimalt resultat. Pointen her, der skal bemærkes, er, at ethvert problem kun har en optimal løsning.
Følgende eksempel får dig til at forstå den grådige metode let. Sig, man ønsker at købe den bedste bil, der findes på markedet. En af metoderne til at vælge denne bil er ved at analysere alle biler på markedet. Nu er det en tidskrævende at gøre det let, man vælger en bil fra de specifikke mærker, som de er interesseret i at investere i. Ved at kategorisere dette yderligere, ville man igen vælge de ønskede modeller, der ser på dens funktioner. Derfor er den tilgang, der bruges her, grådig, da denne løsning var den optimale løsning for dig, mens du overvejede alle faktorer, der var gunstige for dig.
Kernekomponenter i en grådig algoritme
Når vi nu har en bedre forståelse af denne mekanisme, lad os undersøge kernekomponenterne i en grådig algoritme, der adskiller den fra andre processer:
- Kandidatsæt: Der oprettes et svar fra dette sæt.
- Udvælgelsesfunktion: Den vælger den bedste kandidat, der skal inkluderes i løsningen.
- Feasibility-funktion: Dette afsnit beregner, om en kandidat kan bruges til at bidrage til løsningen.
- En objektiv funktion: Den tildeler en værdi til en komplet eller en delvis løsning.
- En opløsningsfunktion: Dette bruges til at indikere, om en korrekt løsning er opfyldt.
Hvor fungerer den grådige algoritme bedst?
Grådig algoritme kan anvendes til nedenstående problemer.
- Den grådige tilgang kan bruges til at finde den minimale spændende trægraf ved hjælp af Prim's eller Kruskals algoritme
- At finde den korteste sti mellem to hjørner er endnu et problem, der kan løses ved hjælp af en grådig algoritme. Anvendelse af Dijkstra's algoritme sammen med den grådige algoritme giver dig en optimal løsning.
- Huffman-kodning
Fordele
Den største fordel, som den grådige algoritme har i forhold til andre, er, at den er let at implementere og meget effektiv i de fleste tilfælde.
Ulemper
Grådig algoritme bygger dybest set en løsning del for del og vælger den næste del på en sådan måde, at den giver den bedste løsning på det aktuelle problem øjeblikkeligt. Som et resultat er der ingen hensyn til eller bekymring for konsekvenserne af den aktuelle beslutning, der er truffet. Aldrig genovervejet de valg, der er taget tidligere, undlader Greedy Algorithm at producere en optimal løsning, skønt den giver en næsten optimal løsning . Rygsækproblem og rejsende sælgerproblem er eksempler på problemer, hvor den grådige algoritme ikke klarer at producere en optimal løsning.
- Rygsækproblem: Mest kendt under navnet rygsækproblematik er et dagligdags problem, som mange mennesker står overfor. Sig, vi har sæt af varer, og hver har forskellig vægt og værdi (fortjeneste), der skal udfyldes i en container eller skal indsamles på en sådan måde, at den samlede vægt er mindre end eller lig med beholderen, mens den samlede fortjeneste maksimeres .
Konklusion
Grådig algoritme er bedst anvendelig, når man har brug for en løsning i realtid og omtrentlige svar er “godt nok”. Det er klart, at en grådig algoritme minimerer tiden, mens den sikrer, at der produceres en optimal løsning, hvorfor det er mere anvendeligt at bruge i en situation, hvor der kræves mindre tid. Efter at have læst denne artikel kan man have en god idé om grådige algoritmer. Derudover forklarer dette indlæg, hvorfor det betragtes som de bedste rammer, der besvarer næsten alle programmeringsudfordringer sammen med at hjælpe dig med at beslutte den mest optimale løsning på et givet tidspunkt.
Dog på den hårde side, for at anvende teorien om grådig algoritme, skal man arbejde hårdere for at kende de rigtige problemer. Selvom det er et videnskabeligt koncept, der har logik, har det også en essens af kreativitet.
Anbefalede artikler
Dette har været en guide til Hvad er en grådig algoritme. Her diskuterede vi grundlæggende koncept, komponenter, fordel og ulempe ved grådig algoritme. Du kan også gennemgå vores andre foreslåede artikler for at lære mere -
- Algoritme i programmering
- Hvad er Perl?
- Introduktion til algoritme
- Hvad er Agile Sprint?