Innholdsfortegnelse:
Definisjon - Hva betyr grådig algoritme?
En grådig algoritme er en algoritmisk strategi som gjør det beste, optimale valget i hvert lite trinn med målet om dette til slutt fører til en globalt optimal løsning. Dette betyr at algoritmen plukker den beste løsningen for øyeblikket uten å ta hensyn til konsekvenser. Den velger den beste umiddelbare produksjonen, men vurderer ikke det store bildet, og det anses derfor som grådig.
Techopedia forklarer Greedy Algorithm
En grådig algoritme fungerer ved å velge best mulig svar i hvert trinn og deretter gå videre til neste trinn til den når slutten, uten å ta hensyn til den generelle løsningen. Det håper bare at banen den tar er den globalt optimale, men som bevist gang på gang, kommer ikke denne metoden ofte med en globalt optimal løsning. Det er faktisk fullt mulig at de mest optimale kortsiktige løsningene fører til et dårligst mulig globalt resultat.
Tenk på det som å ta mange snarveier i en produksjonsvirksomhet: på kort sikt spares store beløp i produksjonskostnadene, men dette fører til slutt til undergang siden kvaliteten blir kompromittert, noe som resulterer i avkastning og lite salg når kundene blir kjent med "Billig" produkt. Men dette er ikke alltid tilfelle, det er mange bruksområder der den grådige algoritmen fungerer best for å finne eller tilnærme den globalt optimale løsningen, for eksempel ved å konstruere et Huffman-tre eller et beslutningsinnlærings-tre.
For eksempel: Ta banen med den største summen totalt sett. En grådig algoritme ville ta den blå banen, som et resultat av kortsiktighet, i stedet for den oransje banen, som gir den største summen.
komponenter:
- Et kandidatsett med data som trenger en løsning
- En valgfunksjon som velger den beste bidragsyteren til den endelige løsningen
- En mulighetsfunksjon som hjelper valgfunksjonen ved å bestemme om en kandidat kan være en bidragsyter til løsningen
- En objektiv funksjon som tildeler en verdi til en delvis løsning
- En løsningsfunksjon som indikerer at den optimale løsningen er blitt oppdaget
