recuit simulé

Une définition du Jargon Français.
Aller à : Navigation, rechercher

locution nominale, masculin.  [algorithmie]. Nom d'un algorithme classique permettant d'obtenir rapidement une valeur approchée d'une solution d'un problème NP-complet (par exemple celui du voyageur de commerce).

L'idée est que si on a un problème contenant beaucoup de conditions et qu'on a une idée de la meilleure solution, on prend une solution au hasard, puis on teste toutes les conditions. À chaque fois qu'une condition n'est pas respectée, on modifie légèrement la solution pour qu'elle la respecte, puis on reteste toutes les conditions jusqu'à ce que ce soit bon (ou qu'on ait dépassé le temps imparti). L'expérience montre qu'on tend ainsi très rapidement vers un minimum local proche de la meilleure solution.