Den grådige metoden er en av strategiene som Divide and conquer som brukes for å løse problemene. Denne metoden brukes til å løse optimaliseringsproblemer. Et optimaliseringsproblem er et problem som krever enten maksimale eller minimale resultater. La oss forstå gjennom noen begreper.
Greedy-metoden er den enkleste og greie tilnærmingen. Det er ikke en algoritme, men det er en teknikk. Hovedfunksjonen til denne tilnærmingen er at beslutningen tas på grunnlag av den for øyeblikket tilgjengelige informasjonen. Uansett hva gjeldende informasjon er tilstede, tas beslutningen uten å bekymre deg for effekten av gjeldende beslutning i fremtiden.
javascript søvn
Denne teknikken brukes i utgangspunktet for å bestemme den mulige løsningen som kan være optimal eller ikke. Den gjennomførbare løsningen er en delmengde som tilfredsstiller de gitte kriteriene. Den optimale løsningen er den løsningen som er den beste og mest gunstige løsningen i undergruppen. I tilfelle av gjennomførbar, hvis mer enn én løsning tilfredsstiller de gitte kriteriene, vil disse løsningene bli vurdert som gjennomførbare, mens den optimale løsningen er den beste løsningen blant alle løsningene.
Kjennetegn på Greedy-metoden
Følgende er egenskapene til en grådig metode:
- For å konstruere løsningen på en optimal måte, lager denne algoritmen to sett der ett sett inneholder alle de valgte elementene, og et annet sett inneholder de avviste elementene.
- En grådig algoritme gjør gode lokale valg i håp om at løsningen enten skal være gjennomførbar eller optimal.
Komponenter av Greedy Algorithm
Komponentene som kan brukes i den grådige algoritmen er:
et objekt i java
Anvendelser av Greedy Algorithm
- Den brukes til å finne den korteste veien.
- Den brukes til å finne minimumsspenningstreet ved å bruke prim-algoritmen eller Kruskal-algoritmen.
- Den brukes i en jobbrekkefølge med en deadline.
- Denne algoritmen brukes også til å løse brøksekkproblemet.
Pseudokode for Greedy Algorithm
Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } Ovennevnte er den grådige algoritmen. Til å begynne med tildeles løsningen null verdi. Vi passerer matrisen og antallet elementer i den grådige algoritmen. Inne i for-løkken velger vi elementet en etter en og sjekker om løsningen er gjennomførbar eller ikke. Hvis løsningen er gjennomførbar, så utfører vi fagforeningen.
La oss forstå gjennom et eksempel.
Anta at det er et problem 'P'. Jeg ønsker å reise fra A til B vist som nedenfor:
P : A → B
Problemet er at vi må reise denne reisen fra A til B. Det finnes ulike løsninger for å gå fra A til B. Vi kan gå fra A til B innen kl. gå, bil, sykkel, tog, fly , osv. Det er en begrensning i reisen at vi må reise denne reisen innen 12 timer. Bare hvis jeg går med tog eller fly, kan jeg dekke denne distansen innen 12 timer. Det er mange løsninger på dette problemet, men det er bare to løsninger som tilfredsstiller begrensningen.
Hvis vi sier at vi må dekke reisen til minimumskostnad. Dette betyr at vi må reise denne avstanden minst mulig, så dette problemet er kjent som et minimeringsproblem. Til nå har vi to gjennomførbare løsninger, det vil si en med tog og en annen med fly. Siden å reise med tog vil føre til minimumskostnaden, så er det en optimal løsning. En optimal løsning er også den gjennomførbare løsningen, men gir det beste resultatet slik at løsningen er den optimale løsningen med lavest mulig kostnad. Det ville bare være én optimal løsning.
Problemet som krever enten minimums- eller maksimumsresultat, da dette problemet er kjent som et optimaliseringsproblem. Grådig metode er en av strategiene som brukes for å løse optimaliseringsproblemene.
python-konstruktør
Ulemper ved å bruke Greedy algoritme
Grådig algoritme tar beslutninger basert på informasjonen som er tilgjengelig i hver fase uten å vurdere det bredere problemet. Så det kan være en mulighet for at den grådige løsningen ikke gir den beste løsningen for hvert problem.
Den følger det lokale optimale valget på hvert trinn med den hensikt å finne det globale optimum. La oss forstå gjennom et eksempel.
Tenk på grafen som er gitt nedenfor:
Vi må reise fra kilden til destinasjonen til en minimumskostnad. Siden vi har tre gjennomførbare løsninger med kostnadsbaner som 10, 20 og 5. 5 er minimumskostnadsbanen, så det er den optimale løsningen. Dette er det lokale optimum, og på denne måten finner vi det lokale optimum på hvert trinn for å beregne den globale optimale løsningen.
arrayliste metoder