Recherches locales, notion de voisinage, critère d'arrêt de la recherche locale, problème de couverture de sommets, problème du voyageur de commerce, problème SAT.
Cherche la meilleure solution dans un ensemble de solutions candidates. La recherche locale consiste à passer d'une solution à une autre solution proche dans l'espace des solutions candidates (l'espace de recherche) jusqu'à ce qu'une solution considérée comme optimale soit trouvée, ou que le temps imparti soit dépassé.
