Greedy algoritme

Een greedy algoritme is een wiskundig proces dat eenvoudige, gemakkelijk uit te voeren oplossingen zoekt voor complexe problemen met meerdere stappen door te beslissen welke volgende stap het meest voor de hand liggende voordeel zal opleveren.

Zulke algoritmen worden greedy genoemd omdat, hoewel de optimale oplossing voor elke kleinere instantie een onmiddellijke output zal opleveren, het algoritme het grotere probleem als geheel niet in overweging neemt. Als een beslissing eenmaal is genomen, wordt deze nooit meer heroverwogen.

Greedy algoritmen werken door recursief een verzameling objecten te construeren uit de kleinst mogelijke samenstellende delen. Recursie is een benadering van het oplossen van problemen, waarbij de oplossing van een bepaald probleem afhangt van oplossingen van kleinere instanties van hetzelfde probleem. Het voordeel van een greedy-algoritme is dat de oplossingen voor kleinere probleemgevallen eenvoudig en gemakkelijk te begrijpen kunnen zijn. Het nadeel is dat het heel goed mogelijk is dat de meest optimale kortetermijnoplossingen tot het slechtst mogelijke langetermijnresultaat leiden.

Greedy algoritmen worden vaak gebruikt in mobiele ad-hoc netwerken om pakketten efficiënt te routeren met het kleinst mogelijke aantal hops en de kortst mogelijke vertraging. Ze worden ook gebruikt bij machine learning, business intelligence (BI), kunstmatige intelligentie (AI) en programmeren.

Zie ook: KISS-principe, Ockham's scheermes