L’algorithme glouton désigne une stratégie universelle dont l’objectif est de « gagner le plus possible à chaque étape de l’algorithme », sans jamais se soucier des conséquences des choix effectués. Autrement dit, un algorithme glouton fait toujours le choix qui lui semble le meilleur sur le moment, en espérant que la solution globale soit la meilleure.
La méthode gloutonne a donné lieu à des algorithmes réputés comme l’algorithme de Kruskal ou encore l’algorithme de Dijkstra, qui fournissent des solutions optimales.
Toutefois, nous retiendrons qu’une stratégie gloutonne aussi simple soit-elle ne fournit pas toujours une solution optimale (ce n’est pas la meilleure solution possible qui est trouvée). Mais elle y arrive dans de nombreux cas !
Énoncé « découverte » d’un algo glouton
