Innehållsförteckning:
Definition - Vad betyder Greedy Algoritm?
En girig algoritm är en algoritmisk strategi som gör det bästa optimala valet i varje litet stadium med målet att detta så småningom leder till en globalt optimal lösning. Detta innebär att algoritmen väljer den bästa lösningen för tillfället utan hänsyn till konsekvenser. Den väljer den bästa omedelbara utgången, men tar inte hänsyn till den stora bilden, därför anses den vara girig.
Techopedia förklarar Greedy Algoritm
En girig algoritm fungerar genom att välja det bästa möjliga svaret i varje steg och sedan gå vidare till nästa steg tills det når slutet, utan hänsyn till den totala lösningen. Det hoppas bara att vägen den tar är den globalt optimala, men som bevisat gång på gång kommer denna metod inte ofta med en globalt optimal lösning. Det är faktiskt fullt möjligt att de mest optimala kortsiktiga lösningarna leder till värsta möjliga globala resultat.
Tänk på det som att ta mycket genvägar i en tillverkningsverksamhet: på kort sikt sparas stora mängder i tillverkningskostnaderna, men detta leder så småningom till nedgången eftersom kvaliteten komprometteras, vilket resulterar i produktens avkastning och låg försäljning när kunder blir bekanta med "Billig" produkt. Men detta är inte alltid fallet, det finns många applikationer där den giriga algoritmen fungerar bäst för att hitta eller tillnärma den globalt optimala lösningen, till exempel att konstruera ett Huffman-träd eller ett beslutsinlärningsträd.
Till exempel: Ta vägen med den största summan totalt sett. En girig algoritm skulle ta den blå vägen, till följd av kortsiktighet, snarare än den orange vägen, som ger den största summan.
Komponenter:
- En kandidatuppsättning data som behöver en lösning
- En urvalsfunktion som väljer den bästa bidragaren till den slutliga lösningen
- En genomförbarhetsfunktion som hjälper urvalsfunktionen genom att bestämma om en kandidat kan vara en bidragsgivare till lösningen
- En objektiv funktion som tilldelar ett värde till en partiell lösning
- En lösningsfunktion som indikerar att den optimala lösningen har upptäckts
