Discussion :

[Loceka]

Bonjour,

Je dispose d'un tableau de case à 2 dimensions (n*n) dont chaque case peut, ou non, acceder à chacune de ses voisines. En supposant une case de départ spécifiée, je voudrais déterminer tous les "chemins" possibles à partir de cette case.

Pour "stocker" ces chemins je pensais faire un arbre ou un tableau de chemins (les 2 possibilités m'intéressent, mais l'arbre serait optimal).

Je sens que c'est très obscur alors voilà un exemple :

Soit le tableau 4*4 de dont les cases sont notées de A à P.
On se donne comme case initiale la case G.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
+-----+-----+-----+-----+    +-----+-----+-----+-----+
|     |     |     |     |    |     |     |     |     |
|  A  |  B 1|1 C 1|1 D  |    |  A  |  B-----C-----D  |
|  1  |  1  |  1  |     |    |  |  |  |  |  |  |     |
+-----+-----+-----+-----+    +--|--+--|--+--|--+-----+
|  1  |  1  |  1  |     |    |  |  |  |  |  |  |     |
|  E 1|1 F  |  G 1|1 H  |    |  E-----F  |  G-----H  |
|     |     |  1  |  1  |    |     |     |  |  |  |  |
+-----+-----+-----+-----+ => +-----+-----+--|--+--|--+
|     |     |  1  |  1  |    |     |     |  |  |  |  |
|  I 1|1 J 1|1 K  |  L  |    |  I-----J-----K  |  L  |
|     |  1  |     |     |    |     |  |  |     |     |
+-----+-----+-----+-----+    +-----+--|--+-----+-----+
|     |  1  |     |     |    |     |  |  |     |     |
|  M 1|1 N  |  O  |  P  |    |  M-----N  |  O  |  P  |
|     |     |     |     |    |     |     |     |     |
+-----+-----+-----+-----+    +-----+-----+-----+-----+

En supposant connue une "operation" ( l'operation "=" par exemple) permettant de savoir si une case est accessible (en fonction de son nom OU de sa direction) à partir de la case actuelle, je voudrais pouvoir créer un arbre ou un tableau listant les "plus longs" chemins possibles.

Le tableau des chemins de l'exemple précédent serait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
[ [G, C, B, F, E, A] ;
  [G, C, D] ;
  [G, K, J, N, M] ;
  [G, K, J, I] ;
  [G, H, L] ]

Pour l'arbre je pense qu'il est aussi simple à "voir".

Ce que je n'arrive pas à faire, c'est trouver un algo qui permette de construire ce tableau/arbre à partir de la case donnée.

Donc si vous voyez comment faire, toute idée est la bienvenue.

PS : le but de ce tableau/arbre est d'être lu uniquement. Après construction il n'y aura ni ajout ni suppression d'élément.

Merci d'avance,
Loceka.

[xxiemeciel]

Salut,

Ca ressemble fortement a un labyrinthe en fais, et ton arbre sera plutot un graphe puisque tu peut revenir sur la meme case par plusieurs chemin suivant les direction possible ou non. (suppose par exemple que le chemin de K vers L soit possible sur ton schema)

Donc essaye de chercher dans les algorithmes de parcours de graphe
- Parcours en largeur
- Parcours en profondeur

et tu devrais trouver ce dont tu as besoin.

XXiemeciel

[Loceka]

Merci bien.

En effet, c'est bien similaire à un labyrinthe mais je ne peux pas repasser 2 fois sur la même case. Donc si j'avais un lien K-L le chemin "[G, H, L]" disparaîtrait au profit de "[G, K, L, H]", si l'on respecte l'ordre de mon algo actuel qui regarde dans l'ordre les directions Haut puis Bas puis Gauche puis Droite.

J'ai oublié de préciser ces cas limites pour simplifier le problème mais dans mon programme je peux me passer de créer 2 chemins distincts s'ils forment une boucle, un seul suffit. D'autant que les arbres (si on sait les créer ) sont bien plus exploitables que les graphes.

[xxiemeciel]

Dans ce cas le plus simple a mon avis c'est de considerer chaque case adjacente comme des noeud fils de ton noeud courant dans ton arbre.

en gros tu pars de G tu regardes les case adjacente (C,H,K)

donc tu as ton noeud courant (G) et trois fils (C,H,K)

tu relances l'algo en recursif sur les fils (fais attention a ne pas prendre en compte le noeud parent dans les fils c'est a dire G ne sera pas un fils de C,H ou K).

la fonction ne fais rien si le seul voisin est le noeud parent.

et voila ton arbre est cree

XXiemeciel

[Loceka]

Jusque là on est d'accord.

Le problème c'est : comment construire une telle fonction, ou plutot : dans quoi ranger les éléments ?

Si par exemple je fais un algo récursif qui crée un tableau d'élements pour chaque noeud, j'aboutirai à quelque chose du style :

[ [ [ [..];[ [...];[...] ];[...] ] ] ]

C'est aussi intraitable par la suite que c'est illisible ici.

Je peux aussi ajouter les éléments un par un dans un tableau mais dans ce cas je ne vois pas comment le relire (comment savoir si tel élément a 0, 1, 2, 3 ou 4 fils ?)

Un autre solution, itérative, serait de créer un tableau 2D de [père, fils] (ex : [ [G, C, K, H] ; [H, L] ; [L] ; [...] ] ) mais il y'aurait beaucoup de redondance, il serait coûteux à construire et ne serait pas optimal pour l'exploitation.

Ce qu'il y'a c'est que je n'ai vraiment aucune idée de comment construire (ou stocker pour être exact) un arbre "propre". En gros je suis un peu à court d'idée.

Merci de t'intéresser au problème.

[xxiemeciel]

je ne comprend pas, une fois ton arbre cree tu as juste a lire chacune de tes branche pour voir tout les chemins possible.

tu dois te creer une structure d'arbre, c'est a dire une classe qui contient un element et qui a des references sur ces fils.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
                     G
                     |
        -------------------------
       |             |            |
       H             C            K
       |             |            |
       L           -------        J
                  |       | 
                  B       D

peut etre ce lien pourra t'aider :
http://recursivite.developpez.com/


XXiemeciel

[Loceka]

j'avais pas pensé à créer une classe pour faire ça, je pense que je devrais mieux réussir maintenant !

Merci pour le lien, c'est tout à fait instructif, surtout pour ce que je dois faire, d'autant que je pensais éviter autant que possible la récursivité (mais apparement c'est la meilleure, voire la seule, solution).

Encore merci,
Loceka.