Dans ce cours, nous franchissons un pas en considérant à présent un labyrinthe contenant plusieurs morceaux de fromage. L’objectif est à présent de tous les ramasser en un minimum de déplacements. Nous présentons donc le problème du voyageur de commerce (dont vous avez déjà entendu parler ici), qui servira à modéliser cet objectif, et détaillons un algorithme pour le résoudre.
Nous montrons que ce problème est particulièrement difficile à résoudre, c’est à dire que tout algorithme pouvant y apporter une solution a au moins une certaine complexité. Pour cela, nous introduisons la notion de classes de complexité, et en présentons les plus standards.