I denna handledning lär du dig vad en girig algoritm är. Du hittar också ett exempel på ett girigt tillvägagångssätt.
En girig algoritm är ett tillvägagångssätt för att lösa ett problem genom att välja det bästa alternativet som finns tillgängligt just nu, utan att oroa sig för det framtida resultat det skulle ge. Med andra ord, de lokalt bästa valen syftar till att producera globalt bästa resultat.
Denna algoritm är kanske inte det bästa alternativet för alla problem. Det kan i vissa fall ge fel resultat.
Denna algoritm går aldrig tillbaka för att vända beslutet. Denna algoritm fungerar uppifrån och ner.
Den största fördelen med denna algoritm är:
- Algoritmen är lättare att beskriva .
- Denna algoritm kan fungera bättre än andra algoritmer (men inte i alla fall).
Möjlig lösning
En genomförbar lösning är den som ger den optimala lösningen på problemet.
Girig algoritm
- Till att börja med är lösningen (som innehåller svar) tom.
- Vid varje steg läggs ett objekt till i lösningsuppsättningen.
- Om lösningsuppsättningen är möjlig behålls den aktuella artikeln.
- Annars avvisas artikeln och övervägs aldrig igen.
Exempel - girig strategi
Problem: Du måste ändra en summa med minsta möjliga antal mynt. Belopp: $ 28 Tillgängliga mynt: $ 5 mynt $ 2 mynt $ 1 mynt
Lösning:
- Skapa en tom lösningsuppsättning = ().
- mynt = (5, 2, 1)
- summa = 0
- Medan summan ≠ 28 gör följande.
- Välj ett mynt C från mynt så att summan + C <28.
- Om C + sum> 28, returnera ingen lösning.
- Annars, summa = summa + C.
- Lägg till C i lösningsuppsättningen.
Fram till de första 5 iterationerna innehåller lösningssatsen 5 $ 5 mynt. Efter det får vi 1 $ 2 mynt och slutligen 1 $ 1 mynt.
Giriga algoritmapplikationer
- Urvalssortering
- Ryggsäck Problem
- Minsta spännande träd
- Enkel källa Problem med kortaste vägen
- Problem med jobbplanering
- Prim's Minimal Spanning Tree Algorithm
- Kruskals minimala spännande trädalgoritm
- Dijkstras minimala spännande trädalgoritm
- Huffman-kodning
- Ford-Fulkerson algoritm
