pb avec un labyrinthe

Question

je suis sur un projet de labyrinthe et j'ai bloqué pour l' algorithme du plus court chemin (entre un pt qq du labyrinthe et la cible au milieu).
le labyrinthe est une matrice carrée et voici comment est ennoncé le sujet:

Les cases sont numérotées de 0 à N= t²-1 ou t est la taille du labyrinthe(mat carrée).Pour mémoriser un chemin, on utilise un tableay C de N élémentsou C[i] désigne la case prédecesseur de i ds le plus court chemin. Par définition si une case i n'est pas dans le chemin on a C[i]=-1 et si une case est la première du chemin on a C[i]=i.
exemple->>labyrinthe a 16 cases

   0 1 2 3
0 1 1
1    1 C
2
3

Les cases sont numérotées de 0 à 15. Et le tableay C qui code ce chemin est tel que C[6]=5; C[5]=1; C[1]=0; C[0]=0;
C[2]=C[3]=C[4]=C[7]=...=C[15]=-1;
l'agorithme est tel que:
Il s'agit d'explorer le laby en largeur,cet algo est tel que il utilise un structure de file.

1. pour toute case i,initialiser C[i] à -1 et le marquage à faux.
2. Initialiser C[a]=a et marquer a.
3. ajouter a à la file F (initialement vide).
4. Répéter
      (a) récupérer la case k dans F et l'enlever de F.
      (b) pour toute case l accessible depuis k et  non marquée 
           i. marquer l
          ii. ajouter l à la file
         iii.mise à jour du chemin: C[l] =k.
5. tant que B n'est pas marquée et F n'est pas vide.

A la fin de l'algo le tableau C décrit le plus court chemin.En partant de la case b, on peut remonter le long du chemin jusqu'à rencontrer la case de départ a et ainsi compter le nbre de coups.Si à la fin de l'algo la case b n'est pas marquée c'est qu'il n'existe pas de plus court chemin.
La file F sera décrite par un objet de classe file.La file sera codée par un tableau d'entier (les cases) ainsi qu'un indice de début (tête) et un indice de fin(queue).
Une file est un ensemble géré selon le principe FIFO (premier entré premier sorti) .La classe file aura une méthode ajouer qui permet d'ajouter un élément en queue de file, une méthode enlever qui permet de récupérer l'elt en tête de la file et l'enlever de la file ainsi qu'une méthode estvide.

si qq connait cet algorithme ou si il arrive a trouver la solution
alors il est fort car moi j'ai rien pigé.

cs_GoldenEye · Answer

-------------------------------
 Réponse au message :	Cherche Djikstra sur google	  
-------------------------------

> je suis sur un projet de labyrinthe et j'ai bloqué pour l' algorithme du plus court chemin (entre un pt qq du labyrinthe et la cible au milieu).
> le labyrinthe est une matrice carrée et voici comment est ennoncé le sujet:
> 
> Les cases sont numérotées de 0 à N= t²-1 ou t est la taille du labyrinthe(mat carrée).Pour mémoriser un chemin, on utilise un tableay C de N élémentsou C[i] désigne la case prédecesseur de i ds le plus court chemin. Par définition si une case i n'est pas dans le chemin on a C[i]=-1 et si une case est la première du chemin on a C[i]=i.
> exemple->>labyrinthe a 16 cases
> 
>    0 1 2 3
> 0 1 1
> 1    1 C
> 2
> 3
> 
> Les cases sont numérotées de 0 à 15. Et le tableay C qui code ce chemin est tel que C[6]=5; C[5]=1; C[1]=0; C[0]=0;
> C[2]=C[3]=C[4]=C[7]=...=C[15]=-1;
> l'agorithme est tel que:
> Il s'agit d'explorer le laby en largeur,cet algo est tel que il utilise un structure de file.
> 
> 1. pour toute case i,initialiser C[i] à -1 et le marquage à faux.
> 2. Initialiser C[a]=a et marquer a.
> 3. ajouter a à la file F (initialement vide).
> 4. Répéter
>       (a) récupérer la case k dans F et l'enlever de F.
>       (b) pour toute case l accessible depuis k et  non marquée 
>            i. marquer l
>           ii. ajouter l à la file
>          iii.mise à jour du chemin: C[l] =k.
> 5. tant que B n'est pas marquée et F n'est pas vide.
> 
> A la fin de l'algo le tableau C décrit le plus court chemin.En partant de la case b, on peut remonter le long du chemin jusqu'à rencontrer la case de départ a et ainsi compter le nbre de coups.Si à la fin de l'algo la case b n'est pas marquée c'est qu'il n'existe pas de plus court chemin.
> La file F sera décrite par un objet de classe file.La file sera codée par un tableau d'entier (les cases) ainsi qu'un indice de début (tête) et un indice de fin(queue).
> Une file est un ensemble géré selon le principe FIFO (premier entré premier sorti) .La classe file aura une méthode ajouer qui permet d'ajouter un élément en queue de file, une méthode enlever qui permet de récupérer l'elt en tête de la file et l'enlever de la file ainsi qu'une méthode estvide.
> 
> 
> si qq connait cet algorithme ou si il arrive a trouver la solution
> alors il est fort car moi j'ai rien pigé.

skinia · Answer

-------------------------------
 Réponse au message :           désolé mais j'ai rien capté a Djikstra c'est peut etre un peu poussé pour mon niveau.
je veux juste le plus court chemin dans un labyrinthe.
ya bien un ptit algorithme qui traine qqpart?
  
-------------------------------

> 
> 
> 
> 
> -------------------------------
>  Réponse au message :	Cherche Djikstra sur google	  
> -------------------------------
> 
> > je suis sur un projet de labyrinthe et j'ai bloqué pour l' algorithme du plus court chemin (entre un pt qq du labyrinthe et la cible au milieu).
> > le labyrinthe est une matrice carrée et voici comment est ennoncé le sujet:
> > 
> > Les cases sont numérotées de 0 à N= t²-1 ou t est la taille du labyrinthe(mat carrée).Pour mémoriser un chemin, on utilise un tableay C de N élémentsou C[i] désigne la case prédecesseur de i ds le plus court chemin. Par définition si une case i n'est pas dans le chemin on a C[i]=-1 et si une case est la première du chemin on a C[i]=i.
> > exemple->>labyrinthe a 16 cases
> > 
> >    0 1 2 3
> > 0 1 1
> > 1    1 C
> > 2
> > 3
> > 
> > Les cases sont numérotées de 0 à 15. Et le tableay C qui code ce chemin est tel que C[6]=5; C[5]=1; C[1]=0; C[0]=0;
> > C[2]=C[3]=C[4]=C[7]=...=C[15]=-1;
> > l'agorithme est tel que:
> > Il s'agit d'explorer le laby en largeur,cet algo est tel que il utilise un structure de file.
> > 
> > 1. pour toute case i,initialiser C[i] à -1 et le marquage à faux.
> > 2. Initialiser C[a]=a et marquer a.
> > 3. ajouter a à la file F (initialement vide).
> > 4. Répéter
> >       (a) récupérer la case k dans F et l'enlever de F.
> >       (b) pour toute case l accessible depuis k et  non marquée 
> >            i. marquer l
> >           ii. ajouter l à la file
> >          iii.mise à jour du chemin: C[l] =k.
> > 5. tant que B n'est pas marquée et F n'est pas vide.
> > 
> > A la fin de l'algo le tableau C décrit le plus court chemin.En partant de la case b, on peut remonter le long du chemin jusqu'à rencontrer la case de départ a et ainsi compter le nbre de coups.Si à la fin de l'algo la case b n'est pas marquée c'est qu'il n'existe pas de plus court chemin.
> > La file F sera décrite par un objet de classe file.La file sera codée par un tableau d'entier (les cases) ainsi qu'un indice de début (tête) et un indice de fin(queue).
> > Une file est un ensemble géré selon le principe FIFO (premier entré premier sorti) .La classe file aura une méthode ajouer qui permet d'ajouter un élément en queue de file, une méthode enlever qui permet de récupérer l'elt en tête de la file et l'enlever de la file ainsi qu'une méthode estvide.
> > 
> > 
> > si qq connait cet algorithme ou si il arrive a trouver la solution
> > alors il est fort car moi j'ai rien pigé.
>

arthroz · Answer

ca sent l'iupien =)

cs_paupau · Answer

paupau

je cherche un programme en pascal sur un labyrinthe.. 
pauline.vdb@libertysurf.fr

tks... very much

Pb avec un labyrinthe

4 réponses

Votre réponse

Discussions similaires