Des conteneurs doivent être triées dans un entrepôt constitué de palettes permettant des déplacements longitudinaux et latéraux des objets qu’elles supportent.

Ici 8 produits doivent être triés (1, ..., 8).

En reprenant le principe de la résolution par heuristique de l’algorithme A* ;
donnez les états, leurs évaluation et le meilleurs choix à partir de la grille suivante jusqu’à la grille but.
Cette grille a été obtenue avec un coût de g(t) = 12.

Grille initiale

Grille But

Ceci reprend le principe du taquin.
Un mouvement du taquin consiste à faire glisser une case numérotée vers la case vide (X dans les tableaux ci-dessus), la case vide prend alors la place de la case déplacée.

Vous donnerez les différents états à partir de chaque état (il y a entre 2 et 4 états possible à partir d’un état donné), en commençant à l’état but et en choisissant à chaque étape l’état de coût f minimal.

Pour rappel, f(e) = g(e)+h(e) avec g = coût (nombre de mouvements ayant mené à l’état courant) et h(e) l’estimation du coût restant mener au but.

Ici, deux heuristiques seront à calculer :

• h1(e) = nombre de cases mal placées,
• h2(e) = somme des distances de Manhattan entre chaque case et sa place finale.
  La distance dm(p1,p2) de Manhattan entre deux points p1(x1, y1) et p2(x2, y2) est égale à
  dm=∣x2−x1∣ + ∣y2−y1∣
  Par exemple, dans la table initiale, la distance de Manhattan entre la case contenant 1 (en (1,1)) et la case contenant 8 (en (3,2)) est de ∣3−1∣ + ∣2−1∣ = 3

Vous trouverez sur ce lien un EXECUTABLE JAVA codant la résolution du Taquin pas A* et ces deux heuristiques présentées.

Aide

Remarque, il y a toujours au moins 2 états suivant possibles.
A partir de la grille initiale, il est possible d’obtenir les états suivants :

e1

e2