Optimisation combinatoire
Pour résoudre de tels problèmes,
nous utilisons principalement deux sources d'inspiration : l'intelligence
artificielle et la recherche opérationnelle.
Techniques issues de l'intelligence artificielle
Ces algorithmes sont des heuristiques adaptées
à l'exploration/élaguage d'arbres et/ou. Ils sont reliés
à des techniques de programmation par contraintes. Citons les algorithmes
du minmax ou alpha-beta.
Techniques issues de la recherche opérationnelle
Dans les cas les plus simples, ces algorithmes
aboutissent à des solutions exactes (par exemple, les algorithmes
de recherche de chemin optimal dans un graphe) en un temps polynomial.
Dans le cas de problèmes NP-complets, les algorithmes exacts sont
de classe exponentielle ; on cherche donc des schémas d'approximation
en temps polynomial. Citons les problèmes de coloriage de graphe
et de recherche de stabilité d'un graphe.