Sissejuhatus ahne algoritmi
Probleemide lahendamiseks kasutatav strateegia. Ahne algoritmi peetakse üheks lähenemisviisiks, mida kasutatakse probleemide lahendamisel. See probleemilahendav ketser hõlmab valiku tegemist, mis tundub sel hetkel parim. Seda lähenemisviisi saab kõige paremini kasutada optimeerimisprobleemide lahendamiseks. Optimeerimisprobleeme võib määratleda probleemidena, mis nõuavad minimaalset või maksimaalset tulemust. Greedy algoritm on kõige lihtsam ja arusaadavam lähenemisviis, mida saab kasutada optimaalse lahenduse saavutamiseks.
Mis on ahne algoritm?
Ahne algoritm on algoritmiline strateegia, mida kasutatakse parima valikulise valiku tegemiseks väga väikeses etapis, väljundina lõpuks globaalselt optimaalne lahendus. See algoritm valib parima lahenduse, mis on sel hetkel teostatav, ilma tagajärgi arvestamata. Ahne meetod ütleb, et probleem tuleks lahendada etappide kaupa, kus iga sisend loetakse arvestatavaks, kuna see sisend on teostatav. Kuna see lähenemisviis keskendub ainult vahetule tulemusele, arvestamata suuremat pilti, peetakse seda ahneks.
Põhikontseptsiooni määratlemine
Siiani teame, mis on ahne algoritm ja miks seda nii nimetatakse. Allpool toodud näpunäited aitavad ahnealgoritmist paremini aru saada. Nüüdseks on olnud väga selge, et ahne algoritm töötab ainult siis, kui on probleem; sellest hoolimata on see lähenemisviis kohaldatav ainult siis, kui meil on sellele probleemile seatud tingimus või piirang.
Probleemide liigid
- Probleemi minimeerimine: probleemile lahenduse leidmine on lihtne, kui kõik tingimused on täidetud. Kui see probleem nõuab minimaalset tulemust, nimetatakse seda siis minimeerimise probleemiks.
- Maksimeerimise probleem: maksimaalset tulemust nõudvat probleemi nimetatakse maksimeerimise probleemiks.
- Optimeerimisprobleem: Probleemi nimetatakse optimeerimisprobleemiks, kui see nõuab minimaalset või maksimaalset tulemust.
Lahenduste tüübid
- Teostatav lahendus: probleemi ilmnemisel on meil sellele probleemile palju usutavaid lahendusi. Võttes arvesse sellele probleemile seatud tingimust, valime siiski lahendused, mis vastavad antud tingimusele. Selliseid lahendusi, mis aitavad meil saada antud tingimustele vastavaid tulemusi, nimetatakse teostatavaks lahenduseks .
- Optimaalne lahendus: lahendust nimetatakse optimaalseks, kui see on juba teostatav ja saavutab probleemi eesmärgi; parim tulemus. See eesmärk võiks olla minimaalne või maksimaalne tulemus. Siinkohal tuleb tähele panna, et igal probleemil on ainult üks optimaalne lahendus.
Järgmine näide aitab teil ahne meetodist hõlpsasti aru saada. Ütle, et keegi soovib osta parimat autot, mis turul saadaval. Üks selle auto valimise meetoditest on kõigi turul olevate autode analüüsimine. Nüüd, kuna see on aeganõudev, valitakse auto nende konkreetsete kaubamärkide hulgast, millesse nad on huvitatud investeerima. Kui seda veelgi liigitada, võiksime jälle valida soovitud mudelid, võttes arvesse selle omadusi. Seetõttu on siin kasutatud lähenemisviis ahne, kuna see lahendus oli teie jaoks optimaalne lahendus, arvestades kõiki tegureid, mis olid teile soodsad.
Ahne algoritmi põhikomponendid
Nüüd, kui meil on sellest mehhanismist parem ülevaade, uurime ahne algoritmi põhikomponente, mis eristab seda muudest protsessidest:
- Kandidaadikomplekt: sellest komplektist luuakse vastus.
- Valiku funktsioon: see valib parima kandidaadi, kes lahendusesse kaasatakse.
- Teostatavusfunktsioon: Selles jaotises arvutatakse, kas kandidaati saab kasutada lahendusesse panustamiseks.
- Objektiivne funktsioon: see määrab väärtuse terviklikule või osalisele lahendusele.
- Lahenduse funktsioon: seda kasutatakse, et näidata, kas õige lahendus on täidetud.
Kus ahne algoritm töötab kõige paremini?
Ahne algoritmi saab rakendada allpool nimetatud probleemidele.
- Greedy lähenemisviisi saab kasutada minimaalse ulatusega puugraafiku leidmiseks Primi või Kruskali algoritmi abil
- Lühima tee leidmine kahe tipu vahel on veel üks probleem, mille saab lahendada ahne algoritmi abil. Dijkstra algoritmi rakendamine koos ahne algoritmiga annab teile optimaalse lahenduse.
- Huffmani kodeerimine
Eelised
Suurim eelis, mis Greedy algoritmil teiste ees on, on see, et seda on lihtne rakendada ja enamikul juhtudel väga tõhus.
Puudused
Ahne algoritm ehitab põhimõtteliselt lahenduse osahaaval ja valides järgmise osa nii, et see annaks praegusele probleemile parima lahenduse kohe. Seetõttu ei võeta praeguse otsuse tagajärgi arvesse ega muretseta. Kunagi varem tehtud valikuid ümber mõeldes ei õnnestu ahne algoritmil optimaalset lahendust luua, ehkki see annab peaaegu optimaalse lahenduse . Seljakotiprobleem ja rändmüüja probleem on näited probleemidest, kus ahne algoritm ei suuda optimaalset lahendust leida.
- Seljakotiprobleem : kõige tuntum nimega seljakoti probleem on igapäevane probleem, millega silmitsi seisavad paljud inimesed. Ütleme, et meil on üksused komplekti ja igaühel on erinev kaal ja väärtus (kasum) konteinerisse täidetuna või see tuleks koguda nii, et kogukaal oleks väiksem või võrdne konteineri omaga, kui kogukasum oleks maksimaalne .
Järeldus
Ahne algoritm on kõige parem rakendada siis, kui vajatakse lahendust reaalajas ja ligikaudsed vastused on piisavalt head. On selge, et ahne algoritm vähendab aega, tagades samal ajal optimaalse lahenduse leidmise, seega on seda paremini kasutatav olukorras, kus on vaja vähem aega. Pärast selle artikli lugemist võib olla aimu ahnete algoritmide kohta. Lisaks selgitatakse selles postituses, miks seda peetakse parimaks raamistikuks, mis vastab peaaegu kõigile programmeerimise väljakutsetele, aidates teil otsustada antud ajahetkel optimaalseima lahenduse.
Kareda külje pealt tuleb ahne algoritmi teooria rakendamiseks siiski rohkem vaeva näha, et õigeid teemasid teada saada. Ehkki see on teaduslik kontseptsioon, millel on loogika, on sellel ka loomingulisus.
Soovitatavad artiklid
See on olnud teemaks Mis on ahne algoritm. Siin arutasime ahne algoritmi tuumkontseptsiooni, komponente, eeliseid ja puudusi. Lisateavet leiate ka meie muudest soovitatud artiklitest -
- Algoritm programmeerimisel
- Mis on Perl?
- Sissejuhatus algoritmi
- Mis on Agile Sprint?