Sous l’hypothèse que P ≠ NP (voir article P est-il égal à NP ?), pour certains problèmes d’optimisation, il n’existe malheureusement pas d’algorithmes efficaces de résolution. Pourtant, comme souvent en mathématiques, leur formulation est parfois si simple que l’on n’imagine pas leur difficulté sous-jacente. Prenons par exemple le célèbre problème du voyageur de commerce : étant donné un ensemble de villes, quel trajet de distance minimale permet de visiter toutes les villes et de revenir au point de départ ? Malgré sa simplicité, il n’existe pourtant aucun algorithme permettant de résoudre efficacement ce problème : même le meilleur d’entre eux mettra un temps qui augmente exponentiellement avec le nombre de villes. Que faire lorsque l’on veut résoudre un problème « de grande taille » (de type de ceux rencontrés en pratique) en un temps « acceptable » (de l’ordre de quelques minutes) ?
Les heuristiques… -----------------
La première solution est l’utilisation d’heuristiques (du grec heuriskein, qui signifie « trouver »). Le but d’une heuristique est de trouver une solution respectant les contraintes du problème, et « de bonne qualité » selon le critère d’optimisation considéré. La solution ne sera pas forcément optimale, mais une heuristique efficace tente de trouver une solution de bonne qualité suivant le temps de résolution imparti.
Par exemple, pour le problème du voyageur de commerce, l’heuristique du plus proche voisin est simple : on sélectionne la prochaine ville à visiter telle que la distance entre la ville courante et la prochaine ville soit minimale, et ce, jusqu’à avoir visité toutes les villes. On revient ensuite à la première ville visitée pour obtenir un trajet (ou tour). Cette heuristique est rapide, mais donne en pratique d’assez mauvais résultats : rien ne garantit en effet que la dernière ville visitée sera « proche » de la première ville, ce qui peut donner un trajet final long et pénalisant.