Recherche de chemin (recursivité et backtracking)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 7 878 fois - Téléchargée 28 fois

Contenu du snippet

Ce programme essaie de résoudre un petit problème assez simple. Un tableau est composé de MAX*MAX nombres, 0 si la case est vide, 8 s'il y a de l'eau (la ou le vaisseau ne peut passer) et 1 pour localiser le vaisseau.
Ce dernier commence en position 0,0 et doit rejoindre par tout les moyens la ligne MAX-1.

Source / Exemple :


#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX 10

int or[MAX*MAX];

void remplir_tab(int tab[][MAX])
{
	int i,j,temp;
	srand(time(0));
	for(i=0;i<MAX;i++)
		for(j=0;j<MAX;j++)
		{
			temp=(int)((rand()/(double)RAND_MAX)*11);
			if(temp<4)
				tab[i][j]=8;
			else
				tab[i][j]=0;

			
		}
	tab[0][0]=1;
	return;
}

void affiche_tab(int tab[][MAX])
{
	int i, j;
	for(i=0;i<MAX;i++)
	{
		for(j=0;j<MAX;j++)
			printf("%d ",tab[i][j]);
		printf("\n");
	}
	return;
}

int ok(int tab[][MAX],int x, int y)
{
	if(tab[x][y]==0&&x>=0&&x<MAX&&y>=0&&y<MAX)
		return 1;
	else
		return 0;
}

void coup(int tab[][MAX],int x,int y, int n) /* n= : 0 bas, 1 haut, 2 droit, 3 gauche */
{
	tab[x][y]=1;
	affiche_tab(tab);
	printf("\n%d %d %d\n",x,y,n);
	tab[x][y]=0;
	getchar();
	if(x==MAX-1)
		exit(1);
	else
	{
		if(n==0)
		{
			if(ok(tab,x+1,y))
				coup(tab,x+1,y,0); 
			if(ok(tab,x,y+1))
				coup(tab,x,y+1,2);
			if(ok(tab,x,y-1))
				coup(tab,x,y-1,3);
		}
		else if(n==1)
		{
			if(ok(tab,x,y+1))	/*DROIT*/
				coup(tab,x,y+1,2);

			if(ok(tab,x,y-1))	/*GAUCHE*/
				coup(tab,x,y-1,3);

			if(ok(tab,x-1,y))	/*HAUT*/
				coup(tab,x-1,y,1);
		}
		else if(n==2)
		{
			if(ok(tab,x+1,y))	/*BAS*/
				coup(tab,x+1,y,0); 
			if(ok(tab,x,y+1))	/*DROIT*/
				coup(tab,x,y+1,2);
			if(ok(tab,x-1,y))	/*HAUT*/
				coup(tab,x-1,y,1);
			
		}
		else
		{
			if(ok(tab,x+1,y))	/*BAS*/
				coup(tab,x+1,y,0);
			if(ok(tab,x,y-1))	/*GAUCHE*/
				coup(tab,x,y-1,3);
			if(ok(tab,x-1,y))	/*HAUT*/
				coup(tab,x-1,y,1);
			
		}
			
	}
		

}

int main()
{
	int tab[MAX][MAX],fini=0; /* 0:case vide 8:eau 1:vaisseau */
	remplir_tab(tab);

	coup(tab,0,0,0);

	return 0;
}

Conclusion :


Beignus sérieux à 1 eural !!

A voir également

Ajouter un commentaire

Commentaires

cs_Joky
Messages postés
1787
Date d'inscription
lundi 22 novembre 2004
Statut
Membre
Dernière intervention
31 janvier 2009
2
Ah décidemment ;)
J'suis entrain de faire ce genre de truc ;)
Enfin vous verrez quand j'aurais fini ;)
Ziman
Messages postés
245
Date d'inscription
dimanche 27 avril 2003
Statut
Membre
Dernière intervention
26 septembre 2008

Salut,

Tu as réussi à développer quelque chose d'une manière que je n'ai pas su réaliser. J'ai été confronté à ce problème un moment et j'ai pensé à le faire avec de la récursivité et... comme je trouve que cette approche est un peu floue et bien j'ai rennoncé à cette manière qui semblait la plus logique et j'ai pensé à un autre algorithme. Il vaut ce qu'il vaut, il n'est sans doute pas meilleur que le tiens, mais je vais en donner l'idée pour ceux qui aurait comme moi, du mal avec la recursivité.

En fait, mon algorithme recopie le tableau initial dans un autre tableau (ca ce n'est pas obligatoire si dans le premier tableau il n'y a que deux choix différent : chemin libre, chemin non libre). Si ce n'est pas le cas il recopie le tableau en simplifiant de cette manière, autrement dit si l'élément est un arbre une pierre ou autre chose qui bloque le passage il met 0 sinon il met 1. On se retrouve avec un tableau binaire. Ensuite je considère que les chemins possibles partent d'un point et ne peux que descendre vers 3 des points situés en dessous (celui directement en dessous, et ceux à gauche et à droite de celui directement en dessous).

Il parcourt alors tout le tableau et pour chaque élément il regarde si au moins un des 3 éléments de passage est libre, si c'est le cas il ne fait rien, si ce n'est pas le cas il transforme l'élement en 0 car cela voudra dire que le passage est impossible par ce point. On vérifie tout les lignes sauf la dernière, ce n'est pas utile. Le parcours se fait de bas en haut.

Une fois ce passage terminé, alors il suffit de prendre un point de départ et à chaque fois on choisit un de ces points en dessous, il est alors sur et certain que si un chemin existe ce point en fera partie.

Maintenant, je n'ai pas regardé à fond ton code, donc je ne sais pas si ton algorithme est capable de remonter dans le tableau pour faire un détour à fin d'arriver au sommet. Le mien ne l'est pas ;)
manta7
Messages postés
105
Date d'inscription
samedi 25 janvier 2003
Statut
Membre
Dernière intervention
13 décembre 2008

Salut, j'ai bien compris ce que tu as essayé de faire et ce n'est pas mal du tout. Quand a ta question de savoir si mon algo est capable de remonter, je réponds oui, c'esr le systeme du backtracking, si par exemple le dernier coup joué est a droite il va tester en haut, en bas et a gauche puis va remonter (c'est a dire revenir a l'appel de la fonction ) et réaliser un chemin différent. Voila a+ ;)
Ziman
Messages postés
245
Date d'inscription
dimanche 27 avril 2003
Statut
Membre
Dernière intervention
26 septembre 2008

J'ai bine compris ce que tu veux dire, mais je ne sais pas si c'est exactement ce que je voulais dire lol, exemple :

_
| ____
|___| |
| _
|___| |
|

Ton algorithme pourrait il suivre ce chemin ? c'est à dire remonter pour trouver le chemin. Tu as peut etre répondu à ma question ici plus haut mais comme faut toujours tout me répeter 2 fois, je serai fixé ainsi lol
Ziman
Messages postés
245
Date d'inscription
dimanche 27 avril 2003
Statut
Membre
Dernière intervention
26 septembre 2008

Oui bon enfin mon chemin n'est pas rendu comme je l'avais fait lol

Soit fait pas attention à ma question lol

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.