Recherche de chemin (recursivité et backtracking)
Soyez le premier à donner votre avis sur cette source.
Snippet vu 8 148 fois - Téléchargée 29 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.
Beignus sérieux à 1 eural !!
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
- X vide8s
- Backtracking c - Meilleures réponses
- Algo backtracking - Meilleures réponses
- Recherche de chemin optimum - Codes sources - Python (Math & Algorithmes)
- C / C++ / C++.NET : Rechercher le chemin optimale dans un graphe ( algorithme de dijkstra ) - CodeS - Guide
- ASM : Dll algorythme de recherche de chemin en a star, a*, fasm - CodeS SourceS - Guide
- Recherche du chemin complet d'un fichier ou d'une application - Codes sources - Flash (ActionScripts)
- Java : Algorithme de bellman, calcul des temps au plus tôt et recherche du chemin critique - - Guide
- Messages postés
-
540
- Date d'inscription
- vendredi 25 juin 2004
- Statut
- Membre
- Dernière intervention
- 1 octobre 2007
2Soit fait pas attention à ma question lol
_
| ____
|___| |
| _
|___| |
|
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
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 ;)
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.