Récréations algorithmiques

Considérons les deux problèmes suivants : 'Étant donnée une carte routière, quel est le plus court chemin entre deux villes (disons, Paris et Toulouse) ?', 'Un voyageur de commerce doit visiter une et une seule fois certaines villes fixées, puis revenir à son point de départ. Quel est l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ?'

Ces deux problèmes sont des problèmes d'optimisation combinatoire : il s'agit de trouver le meilleur chemin (ou tour) étant donné un nombre fini (mais très grand) de chemins (ou de tours). Cependant, il existe un algorithme efficace qui résout le premier problème (ce problème est dit facile), alors que l'on ne sait pas résoudre efficacement le deuxième problème (ce problème fait partie de la classe des problèmes difficiles).

Le but de cet atelier est de présenter, par des exemples, des problèmes d'optimisation combinatoire (faciles et difficiles), et de montrer pour certains de ces problèmes les algorithmes (méthodes de résolution automatique) les résolvant.