Pour ce TP, nous allons programmer un algorithme de backtracking pour aller chercher tous les morceaux de fromage du labyrinthe en un nombre de mouvements minimal.
Pour ce faire, nous allons utiliser une heuristique.
Heuristique
Programmer une heuristique choisissant parmi les voisins le plus proche.
Algorithme
En vous inspirant de votre programme répondant au problème du voyageur de commerce, programmez l’algorithme de backtracking.
Quoi faire ensuite ?
Allez chercher tous les morceaux de fromage grâce à un algorithme de backtracking.
Comparez le temps de calcul avec l’algorithme exhaustif et l’algorithme glouton.
Allez plus loin (par exemple en implémentant un algorithme de branch-and-bound) !