Algorithmes gloutons

En programmation, pour résoudre un problème, diverses techniques sont évidemment possibles. En première approche, et considérant la puissance de nos machines qui n’a de cesse de croître, il est tentant de calculer toutes les solutions pour choisir la meilleure.

Cette technique dite par **force brute**, c’est-à-dire en testant tous les cas possibles peut-être utilisée mais ce type de résolution peut aussi présenter un problème d’efficacité voire de mise en oeuvre.

La technique glouton (*greedy* en anglais) propose une alternative:

Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local dans l’espoir d’obtenir un résultat optimum global

Cette technique s’utilise pour résoudre des problèmes d’optimisation comme le rendu de monnaie ou le voyageur de commerce. Certains problèmes rencontrés dans l’industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l’optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte électronique le plus vite possible ?