BDD IA Web services Architecture Info. Ubi.

M1

TD Taquin par A*

Hypothèse : ajouter des heuristiques pour guider / accélerer la recherche de solutions.

Taquin initial :

1 2 3
4 6 8
7 5

Taquin but :

1 2 3
4 5 6
7 8 
                                +---+---+---+
                                | 1 | 2 | 3 |
                                +---+---+---+
                                | 4 | 6 | 8 |
                                +---+---+---+
                                | 7 | 5 |   |
                                +---+---+---+
                               /             \
                              /               \
                             /                 \
                +---+---+---+                  +---+---+---+
                | 1 | 2 | 3 |                  | 1 | 2 | 3 |
                +---+---+---+                  +---+---+---+
                | 4 | 6 | 8 |                  | 4 | 6 |   |
                +---+---+---+                  +---+---+---+
                | 7 |   | 5 |                  | 7 | 5 | 8 |
                +---+---+---+                  +---+---+---+
               /      |      \                /      |      \
              /       |       \              /       |       \
             /        |        \            /        |        \
+---+---+---+   +---+---+---+  +---+---+---+   +---+---+---+   +---+---+---+
| 1 | 2 | 3 |   | 1 | 2 | 3 |  | 1 | 2 | 3 |   | 1 | 2 |   |   | 1 | 2 | 3 |
+---+---+---+   +---+---+---+  +---+---+---+   +---+---+---+   +---+---+---+
| 4 | 6 | 8 |   | 4 |   | 8 |  | 4 | 6 | 8 |   | 4 | 6 | 3 |   | 4 |   | 6 |
+---+---+---+   +---+---+---+  +---+---+---+   +---+---+---+   +---+---+---+
|   | 7 | 5 |   | 7 | 6 | 5 |  | 7 | 5 |   |   | 7 | 5 | 8 |   | 7 | 5 | 8 |
+---+---+---+   +---+---+---+  +---+---+---+   +---+---+---+   +---+---+---+

Exemple, sur 24 lettres (5 × 5 - 1)

16 déplacements :