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 :

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)
Voici le resultat avec mon shell sans le print de la solution pour gagner des lignes.
~/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
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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