theorie des graphes/plus long chemin

Question

Bonjour à tous, J'ai un tp à faire sur un labyrinthe apparemment "très classique" mais malgré ça j'ai beauuucoup de mal à le faire. Mon problème n°1: J'ai méme pas compris cette question: Inonder le labyrinthe en parcourant tous les chemins du labyrinthe mon probléme n°2: Je ne sais pas du tout comment on fait pour trouver le plus long chemin enfin je sais qu'il faut utiliser un parcours DFS mais j'arrive pas à l'appliquer. Merci à tous ceux qui voudront m'aider.

nhervagault · Answer

Salut,

Pour innonder ton labyrinthe 
il faut que tu fasses un parcours qui a partir de l'entrée de ton labyrinthe passe par toutes les cases atteignables de ton labirynthe.

Un parcours recursif est l'ideal tu parcours chaque chemin tant que tu n'es pas blqoué ou arrive à la fin.

Pour le chemin le plus long
tu retiens le chemin le plus long (0 à l'init)

et dés que tu arrives à la fin tu compares avec la valeur initiale si > alors tu changes la valeur stockée et sinon tu recommence
si tu es en cul de sac tu reprends le chemin suivant dans le parcours
l'algo d'innodation te permettta de parcourir tout le labyrinthe

il suffit de modifier le DFS pour compter le nombre de cases entre le debut et la fin de ton laby

Aide pour le DFS
http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur

cs_imanouu · Answer

Merci pour la 1ere question j'ai enfin réussi à la faire.Mais pr ce qui est du plus court chemin u encore le plus long je tombe a chaque fois sur un résultat bizarre "DEUX CASES QUI NE SONT PAS VOISINES" ce qui est bien sur archi faux!!! Et je vois pas où est le probléme

nhervagault · Answer

Ton initilisation est-elle correcte?

Regardes avec un labyrinthe plus petit?
Trace les numeros de cases par ou tu passes si c'est possible

Mais je ne peux aider?

cs_imanouu · Answer

justement le avec lequel je travaille est déja petit.Je peux si tu veux bien te l' envoyer par mail et y jeter un coup d'oeil stp en plus c'est à rendre aprés demain et j'ai fait tt mon possible je déséspére
 et  Merci beauuuucoup

coucou747 · Answer

salut

envoie ton code ici, ca ira plus vite.


innonder son laby, ce n'est pas qqch de vraiment recursif : il s'agit d'un parcours en profondeur : ca se fait avec une file first in first out.

tu mets la case de depart dans la file.
tant qu'il y a une case dans la file, faire :
   si on avait pas deja parcourru cette case, faire :
      mettre dans la file les cases qui touchent la case courante.
   fin si
fin tant que

en faisant ca, nos goutes d'eau (qui parcourent en meme temps tout les chemins) vont toutes a la meme vitesse.

cs_imanouu · Answer

Travail à compléter<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /??>





voici exactement en quoi ca consiste:
aidez moi s'il vous plait parce que je dois le rendre  demain et je m'en sors pas toute seule j'ai à peine fait la 1ere question!!!




 








Question 2.1







Soit le labyrinthe suivant extrait du fichier minizoo.laby :           
+-+-+-+-+





|I  |   |





+-+ +-+-+





| |   | |





+ + + +-+





| | | | |





+-+ + +-+





|      O|





+-+-+-+-+





Représentez l’
espace d’états
 de son graphe non orienté. En déduire toutes ses composantes connexes. Puis donnez la représentation mémoire de sa matrice port.






 








Question 2.2







En vous servant des classes fournies, définissez et implémentez en C++ une méthode dans la classe Chemins qui recherche et affiche toutes les composantes connexes du labyrinthe.






 








Question 2.3







On souhaite faire trois parcours de chemins d’un sommet de départ au sommet de sortie : 







1-     


Inonder le labyrinthe en parcourant tous les chemins du labyrinthe, 







2-     


Chercher le plus court chemin en parcourant le labyrinthe en largeur (BFS) avec une file d’attente : voir les méthodes enfiler et defiler de la classe ListeNoeuds.







3-     


Chercher le plus long chemin en parcourant le labyrinthe en profondeur (DFS) avec une pile : voir la méthode empiler de la classe ListeNoeuds,

nhervagault · Answer

STOP 

On n'est pas la pour faire les programmes en entier ;-)

Voila une source qui peut aider

http://www.cppfrance.com/codes/COMPOSENTE-CONNEXES-GRAPHE_47392.aspx

coucou747 · Answer

salut

on a pas pour habitude de faire les tps des gens a leur place.

si tu nous disait precisement sur quoi tu bloques, que tu nous montrait ton code, et l'erreur qui te pose probleme, on pourrait peut-etre t'aider, mais certainement pas te le faire a ta place.

cs_imanouu · Answer

oui je sais!!!!! Mais je demande juste des indications pas plus et en plus j'ai déja essayé de le faire!!!

Mon probléme c'est quand je fais la file et je combine les résultats de l'affichage je trouve un résultat IMPOSSIBLE à moins qu'il saute!!!ce qui n'est pas possible.
Donc si quelqu'un voit où est le probléme je lui serai reconnaissante!!

Merci pour ceux qui voudront bien m'aider.
Une débutante en programmation déséspérée.

coucou747 · Answer

ca fait deux fois que je te demande de nous envoyer ton code... si on ne le voit pas, on ne peut pas voir ce qui ne va pas dans ton code.

cs_imanouu · Answer

ok voici mon code: (c'est en C++)

dans ListeNoeuds.cpp

#include "ListeNoeuds.h"




// Implémentation du constructeurListeNoeuds::ListeNoeuds () { tete queue NULL ; taille = 0 ; marque = false ; }


// Implémentation des méthodes
int ListeNoeuds::getTaille () { return taille ; }


Noeud *ListeNoeuds::getTete() { return tete ; }


Noeud *ListeNoeuds::getQueue() { return queue ; }


bool ListeNoeuds::getMarque() { return marque ; }


void ListeNoeuds::setMarque(bool pmarque) { marque = pmarque ; }


bool ListeNoeuds::estVide () { return taille==0 ; }


void ListeNoeuds::empiler(Sommet *ps) {
    Noeud *nouveau = NULL ;
    nouveau = new Noeud(ps); // appel du constructeur de Noeud
    nouveau->setNext(tete);
    tete = nouveau;
    taille++ ;
}


void ListeNoeuds::enfiler (Sommet *ps) {
 Noeud *nouveau = NULL ;
 nouveau = new Noeud (ps) ; // appel du constructeur de Noeud
 if (estVide()==true)  tete queue nouveau ;
 else {
  queue->setNext (nouveau) ;
  queue = nouveau;
 }
 taille++ ;
}


Sommet *ListeNoeuds::defiler () { // on suppose que la file n’est pas vide
 Noeud *temp  = tete ;
 Sommet *s = temp->s ;
 if (tete==queue)  tete queue NULL ;
 else
  tete = tete->getNext () ;
 delete (temp) ; // appel du destructeur de Noeud
 taille-- ;
 return s ;
}

dans ListeNoeuds.h

#ifndef FILENOEUDS
#define FILENOEUDS


#include "Noeud.h"
#include 


using namespace std;


class ListeNoeuds
{
private:
 int taille ; // nombre de noeuds
 Noeud *tete, *queue ; // objets dynamiques sur le premier et dernier noeud
 bool marque ; // marquage de l’ancre lors d'un parcours de chemin


public:
      // constructeur par défaut
 ListeNoeuds ();


 // prototypes des méthodes
 int getTaille () ; // accesseur en lecture de taille
 Noeud *getTete(); // accesseur en lecture de tete
 Noeud *getQueue(); // accesseur en lecture de queue
 bool getMarque(); // fonction booléenne qui vérifie si l'ancre est marquée
      void setMarque(bool pmarque);// Procédure qui met à true ou false la marque de l'ancre
      bool estVide (); // fonction booléenne qui vérifie si la liste est vide ou non
 void empiler(Sommet *ps); // empiler un sommet en tete de la liste
 void enfiler (Sommet *ps); // enfiler un sommet en queue de la liste
 Sommet *defiler (); // defiler un sommet de la tete de la liste
};


#endif


merci beauuucoup de bien vouloir m'aider!!

coucou747 · Answer

c'est un code pour une liste chainee ca, ca te fait une pile et une file, mais ca n'a rien a voir avec ton tp...

cs_imanouu · Answer

oui mais là je dois faire une file pour déterminer le plus court chemin!!

cs_imanouu · Answer

pour trouver le plus court chemin voici l'algorithme que j'utilise:

  1.Mettre le noeus de départ ds la file
  2.retirer le noeud du début de la file pour l'examiner
  3.Mettre tous les voisins non examinés dans la file
  4.Si la file n'est pas vide reprendre l'étape2

J'aimerai s'il vous plait savoir si on a genre deux élements est ce qu'on prend les voisins non encore marqués de tous les autres éléments avant ou seulement ceux de l'élément accessible.

Merci de bien vouloir me répondre.

Theorie des graphes/plus long chemin

14 réponses

Votre réponse