Taquin solver a*

Bonjour, j'ai presque fini de realiser un taquin solver en c. Je voudrai y rajouter des heuristiques pour gagner en rapidite et pourquoi pas gerer des grilles plus grande que 3x3.

J'ai utilise le deep first a* comme algo.

Voici un extrait avec la grille :

Citation:

---

0 3 4
5 6 8
1 2 7

---

Mon probleme est le suivant si jutilise un heuristique (manhattan dans l'exemple) je ne comprend pas comment je peux etre plus lent que mon ordre de recherche par default (haut bas gauche droite) :oops:
Voici le resultat avec mon shell sans le print de la solution pour gagner des lignes.

Citation:

---

~/Desktop/npuzzle(branch:heuristiques*) » ./n-puzzle -manhattan grid && ./n-puzzle grid
La grille est Solvable
number of move = 24
Time = 1.233524
Memory = 960 octets
La grille est Solvable
number of move = 24
Time = 0.643611
Memory = 960 octets

---

Voici mon debug pour la meme grille

Citation:

---

La grille est Solvable
weight manhattan = 14
ways[ 0].way = Botton .weight = 15
ways[ 1].way = right .weight = 15
ways[ 2].way = Top .weight = -2147483648
ways[ 3].way = left .weight = -2147483648
weight manhattan = 14
deep = 0
0 3 4
5 6 8
1 2 7


ways[ 0].way = right .weight = 16
ways[ 1].way = Botton .weight = 14
ways[ 2].way = Top .weight = -2147483648
ways[ 3].way = left .weight = -2147483648
weight manhattan = 15
deep = 1
5 3 4
0 6 8
1 2 7


ways[ 0].way = Top .weight = 17
ways[ 1].way = Botton .weight = 15
ways[ 2].way = right .weight = 15
ways[ 3].way = left .weight = -2147483648
weight manhattan = 16
deep = 2
5 3 4
6 0 8
1 2 7


ways[ 0].way = right .weight = 18
ways[ 1].way = left .weight = 16
ways[ 2].way = Top .weight = -2147483648
ways[ 3].way = Botton .weight = -2147483648
weight manhattan = 17
deep = 3
5 0 4
6 3 8
1 2 7


ways[ 0].way = Botton .weight = 19
ways[ 1].way = Top .weight = -2147483648
ways[ 2].way = left .weight = -2147483648
ways[ 3].way = right .weight = -2147483648
weight manhattan = 18
deep = 4
5 4 0
6 3 8
1 2 7

---

On voit tres clairement que l'ordre de parcours du graff n'est pas toujours le meme et que pour chaque tours la distance manhattan est bonne.
Avez vous une idee d'ou pourrai venir la raison de cette lenteur svp ?

Voici ma fonction principale

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

static t_func_move g_moves[] = { {FLAG_TOP, move_top}, {FLAG_BOTTOM, move_bottom}, {FLAG_LEFT, move_left}, {FLAG_RIGHT, move_right}, {FLAG_NONE, NULL} };   void solve_npuzzle(t_grid *grid, int loop, int const y_zero, int const x_zero, int const move, int right_coord, int weight) { unsigned int i; t_way_weight ways[MAX_WAY];   if (grid == NULL || loop > grid->max_deep || loop >= MAX_DEEP) return ; if (right_coord == grid->end) { #ifdef DEBUG printf("right_coord = %3d\n", right_coord); #endif grid->found = true; grid->max_deep = loop - 1; for (int k = 0; k < loop; k++) g_way_good[k] = g_way_move[k]; printf("number of move = %d\n", loop); return ; } if (get_order_ways(grid, ways, move, y_zero, x_zero, weight) != true) return ; #ifdef DEBUG printf("weight manhattan = %3d\n", weight); print_grid(grid, loop, move); #endif for (i = 0; g_moves[i].key != FLAG_NONE && grid->found != true; i++) if (ways[i].weight >= 0) if (g_moves[ways[i].index].f(grid, loop, y_zero, x_zero, move, right_coord, ways[i].weight) < 0) return ; }

---

cette fonction est recursive, car toutes les fonctions move appelle solve_npuzzle.

Je suis a votre disposition si vous voulez voir d'autre morceaux du code.

Merci :oops::lol: