Sujet Demi-finale 2003 : Plan de metro

Bonjour je m'entraine sur les sujets de demi-finale , epreuve machine , avant l'epreuve reele (pas question de la foirée cette fois :D :D)

Je suis arrive à l'avant dernier niveau , et je me penche actuellement sur l'exo "Plan de metro", je suis arrivée sans difficulté jusqu'a ce niveau d'exo , mais sur ce niveau en question il y a un exo sans code source ni exemple de proposé , et un autre sur les anagrammes qui m'inspire pas trop, et avant de me lancer dans une croisade de recherche et autre prise de tête je voudrais être sur d'aller dans la bonne direction , et pas faire trop compliqué si une methode plus simple existe ...

Alors voila , le but etant de determiner la station la plus eloignée de la station de depart donnée , partant sur l'exemple donnée je me suis dit que le meilleur traitement est de faire un arbre , puis j'en suis arrivée a=à l'exploitation de liste chainée , pour le modeliser , ca serait quelque chose dans le genre (en C) :

struct station
{
int id;
int count;
station *next[1000];
}

Je m'explique , chaque element de ma liste contiendrai un identifiant entier , le numero de la station en question ,un entier count , correspondant au nombre de fils de mon arbres et un tableau de pointeur (ou chaque element pointe sur une structure station)

Dans la premiere phase de mon algo , je m'occuperai donc de lier toutes les stations données (en partant de la station de depart) , puis je me contentere de parcourir tous les chemins possible tout en comptant le nombre d'etape , le nombre d'etape le plus grand trouvé serait alors ma solution

Les questions que je me pose alors sont :

1 - Est-ce une bonne methode ? Dans le sens ou quand même ca me paré demesuré par rapport au exo du niveau precedant
2 - Vis a vis de mon arbre , est possible qu'il y est des situations ou le modeliser soit long voire infaisable (tourne en boucle sans s'arreter)

Voila j'ai fini (fiouu :D) , merci d'avance pour votre reponse

Si la station 1 est reliée aux stations 2 et 3, et que les stations 2 et 3 mènent toutes deux à la station 4, comment ferais-tu ton arbre ? Il faudrait dupliquer ton noeud 4.

De plus, même sans le problème des doublons, il n'est pas pratique de construire ton arbre. Quand tu dois ajouter une connexion, tu as besoin de parcourir ton arbre en entier pour retrouver ta station ? C'est un peu dommage.

Je n'ai pas fait cet exercice, personnellement, mais je pense que :
* accéder à n'importe quel noeud en temps constant peut être pratique ;
* il faut faire attention aux boucles (si on peut aller de 1 à 2, on peut aussi aller de 2 à 1) ;
* tu auras donc probablement besoin de marqueurs pour éviter de tourner en rond.

J'espère que ça va t'aider un peu.

P.S. : au niveau de la théorie, on parle ici de graphe, plutôt que d'arbre. Lire des cours sur les graphes peut aider, mais tu devrais normalement pouvoir te débrouiller sans.

C'est bien ce que je pensais , merci je devrai y arriver maintenant \^\^

Ta structure de données est correcte (c'est ce qu'on appelle une représentation de graphe en liste d'adjacences), mais ta méthode de parcours ne l'est pas. Il s'agit d'un simple parcours de graphe. Consulte n'importe quel bouquin d'algorithmique ou prends le corrigé de l'exo 3 du QCM de cette année comme base de réflexion. Il ne faut pas y changer grand chose pour arriver au résultat.

Merci pour les informations sinon une autre chose que j'aimerais savoir est une precision sur l'enoncé , pour être sur de pas être dans l'erreur , quand vous dite , la station la plus eloigné ... autrement dit la station eloigné par le plus grand nombre de station , il faut pas prendre en compte les detour donc , car admettons :

A relié a B et B relié a C et D , C et D etant aussi reliées, on prend la station D comme station de depart
La station la plus eloigné est donc la station A , mais doit on prendre en compte le parcours D C B A ou D B A ?

C'est la station la plus éloignée par le trajet le plus court, si j'ose dire. C'est-à-dire que dans ton exemple, le parcours serait D B A.

Je n'ai pas participé à la rédaction de cet exo (j'étais candidat à l'époque) mais je pense qu'il s'agit de la station la plus éloignée par le chemin le plus court. I.e. pour tout couple de stations (a,b), celui où le plus court chemin de a à b est le plus long.

Cool merci beaucoup \^\^

Bon alors apres different essai et recherche / apprentissage de certain algo / objet , j'ai recommencé depuis le debut , je fais un bfs qui marchent parfaitement , cependant je ne passe que les deux premiers tests ,au troisieme mon programme renvoi 3 alors que la sortie attrendu est 4 ... voici le code :

 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

int StationsIntermediaires(int tab[1000][2], int couples, int depart)
{
 int best=0,i;
 int mark[1001];
 for (i=0;i<1001;i++)
  mark[i] = 0;

 queue <int> station; // Fife FIFO pour BFS
 int tempNode;
 station.push(depart); // placement du noeud de depart dans la file

 while (!station.empty())
 {
  tempNode = station.front();
  station.pop();
  // Detection des stations adjacentes :
  for (i=0;i<couples;i++)
  {
    if(tab[i][0] == tempNode && mark[tab[i][1]] == 0)
    {
      station.push(tab[i][1]);    
      mark[tab[i][1]] = mark[tab[i][0]]+1;       
    } 
  }
 }

 for (i=0;i<1001;i++)
 {
   if(mark[i] > best)
    best = mark[i];
 }

 return best-1;
}

Je ne comprend pas ... aurais-ce un rapport avec le best - 1 que je renvoi (pour ne pas compter la station d'arrive :/)

Cette ligne là est fausse :
mark[tab[i][1]] = mark[tab[i][0]]+1;

Je te laisse deviner pourquoi (fait des dessins et fait tourner ton algo sur des exemples).

D'autre part, l'implémentation est un peu inefficace (même si pour les contraintes de ce problème, ça peut passer, je n'ai pas regardé). En effet, pour connaitre les stations voisines de tempNode, tu parcours toute la liste des couples de stations de métro. Je te conseille de mettre tout ça dans un vector adjacents[1001], où adjacents[tempNode] contient tous les voisins de tempNode.

Donc appliquer Dijkstra et chercher la plus grande distances des "plus courts chemins"....

@viny: ton code entre dans une récursion infinie dans cet exemple.

Bon alors j'ai decidé de me remettre dessus , avec un algo de type BFS , l'exemple marche bien , j'ai crée quelques cas speciaux ou ca marche également , mais impossible de passer le test 3 , j'ai un decalage de 1 par rapport à la sorti attendu : j'ai 3 au lieu de 4, incomprehensible , voici mon code , http://pastebin.com/ma565d0f

Plesae help ca me tue de pas y arriver XD

Je ne comprends pas trop ton histoire de adjCount. Tu ferais mieux de stocker tes distances à l'origine dans ta pile, avec le numéro du sommet.