Den giriga metoden är en av strategierna som Divide and conquer som används för att lösa problemen. Denna metod används för att lösa optimeringsproblem. Ett optimeringsproblem är ett problem som kräver antingen maximala eller minimala resultat. Låt oss förstå genom några termer.
Den giriga metoden är den enklaste och raka metoden. Det är inte en algoritm, men det är en teknik. Huvudfunktionen för detta tillvägagångssätt är att beslutet fattas på grundval av den information som för närvarande finns tillgänglig. Oavsett vad den aktuella informationen är, fattas beslutet utan att oroa sig för effekten av det aktuella beslutet i framtiden.
järv vs grävling
Denna teknik används i grunden för att bestämma den möjliga lösningen som kan eller kanske inte är optimal. Den genomförbara lösningen är en delmängd som uppfyller de givna kriterierna. Den optimala lösningen är den lösning som är den bästa och mest fördelaktiga lösningen i delmängden. I fallet med genomförbar, om mer än en lösning uppfyller de givna kriterierna, kommer dessa lösningar att betraktas som genomförbara, medan den optimala lösningen är den bästa lösningen bland alla lösningar.
Egenskaper hos Greedy-metoden
Följande är egenskaperna hos en girig metod:
- För att konstruera lösningen på ett optimalt sätt skapar denna algoritm två uppsättningar där en uppsättning innehåller alla valda föremål, och en annan uppsättning innehåller de avvisade föremålen.
- En girig algoritm gör bra lokala val i hopp om att lösningen ska vara antingen genomförbar eller optimal.
Komponenter i girig algoritm
Komponenterna som kan användas i den giriga algoritmen är:
snö vs is
Tillämpningar av Greedy Algorithm
- Den används för att hitta den kortaste vägen.
- Den används för att hitta det minsta spännträdet med hjälp av prim:s algoritm eller Kruskals algoritm.
- Det används i en jobbsekvensering med en deadline.
- Denna algoritm används också för att lösa problemet med fraktionerad ryggsäck.
Pseudokod för 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; } } Ovanstående är den giriga algoritmen. Inledningsvis tilldelas lösningen nollvärde. Vi passerar arrayen och antalet element i den giriga algoritmen. Inne i for-slingan väljer vi elementet ett efter ett och kontrollerar om lösningen är genomförbar eller inte. Om lösningen är genomförbar, så utför vi facket.
Låt oss förstå genom ett exempel.
Anta att det finns ett problem 'P'. Jag vill resa från A till B enligt nedan:
P : A → B
Problemet är att vi måste resa denna resa från A till B. Det finns olika lösningar för att gå från A till B. Vi kan åka från A till B genom att gå, bil, cykla, tåg, flygplan , etc. Det finns en begränsning i resan att vi måste resa denna resa inom 12 timmar. Om jag åker tåg eller flyg bara då, kan jag täcka denna sträcka inom 12 timmar. Det finns många lösningar på detta problem men det finns bara två lösningar som uppfyller begränsningen.
Om vi säger att vi måste täcka resan till lägsta kostnad. Detta innebär att vi måste resa denna sträcka så lite som möjligt, så detta problem är känt som ett minimeringsproblem. Hittills har vi två genomförbara lösningar, det vill säga en med tåg och en annan med flyg. Eftersom att resa med tåg kommer att leda till lägsta kostnad så är det en optimal lösning. En optimal lösning är också den genomförbara lösningen, men ger det bästa resultatet så att lösningen är den optimala lösningen med minimal kostnad. Det skulle bara finnas en optimal lösning.
Problemet som kräver antingen minimalt eller maximalt resultat då det problemet är känt som ett optimeringsproblem. Girig metod är en av strategierna som används för att lösa optimeringsproblemen.
maven förråd
Nackdelar med att använda girig algoritm
Girig algoritm fattar beslut baserat på den information som finns tillgänglig i varje fas utan att ta hänsyn till det bredare problemet. Så det kan finnas en möjlighet att den giriga lösningen inte ger den bästa lösningen för varje problem.
Den följer det lokala optimala valet i varje steg med avsikt att hitta det globala optimala. Låt oss förstå genom ett exempel.
Tänk på grafen som ges nedan:
Vi måste resa från källan till destinationen till lägsta kostnad. Eftersom vi har tre möjliga lösningar med kostnadsvägar som 10, 20 och 5. 5 är den lägsta kostnadsvägen så det är den optimala lösningen. Detta är det lokala optimum, och på så sätt hittar vi det lokala optimum i varje steg för att beräkna den globala optimala lösningen.
oxe vs tjur