Parcourir une matrice de distances/adjacence

[TheReveller]

Bonjour,

Y a-t-il des mathématiciens qui se sont arrêté sur des techniques afin de parcourir une matrice en une boucle fermée ?

Je m'explique. Disons qu'on a les points A, B et C. On veut parcourir tous les duos possibles (considérant l'asymétrie [A-B différent de B-A]). Les duos à parcourir sont donc :

AB
AC
BA
BC
CA
CB

Comment connecter tous ces duos en une boucle fermée ?

Solution : ABACBCA, bref [AB][BA][AC][CB][BC][CA].

En visualisant la matrice, j'ai trouvé intuitivement une technique qui est probablement plutôt simple à implémenter et qui semble fonctionner à coût sûr.



J'aimerais savoir s'il vous connaissez d'autres techniques, si vous avez d'autres suggestions ou si vous avez plus d'informations au sujet de mon problème.

Merci.

[fatal_error]

slt,

tu crèes une matrice M composé des noeuds n1=AB; n2=BA,n3=AC, ...
et tu écris les relations entre n1,n2,...

Ensuite t'élèves M puissances 6 et tu conserves les chemins.
Tu regardes les elem sur la diago, ils représentent les cycles.
Pour chacun des elem, si tes 6 noeuds sont présents sur le chemin, alors tu as ta boucle fermée

[TheReveller]

Merci de l'astuce, mais je cherche à déterminer le parcours à effectuer pour passer par tous les duos sans repasser deux fois par la même case, comme j'ai noté dans mes images à la main. L'ordre 1 à 20 pour la première matrice et l'ordre 1 à 54 pour la seconde.

Par exemple, dans la première matrice 5x5 avec 5 points uniques, il y a 20 distances à déterminer.

Un parcours possible qui permet de faire tous les chemins possibles de la matrice 5x5 une seule fois serait par exemple ABACADAEBCBDBECDCEDEA, comme je l'ai indiqué sur l'image. Je ne sais pas s'il y a d'autres approchent ou d'autres permutations possibles. Évidemment, puisque nous sommes en boucle fermée, la solution que je suggère peut subir des glissements (rotations).

[fatal_error]

Merci de l'astuce, mais je cherche à déterminer le parcours à effectuer pour passer par tous les duos sans repasser deux fois par la même case

tu repasses pas deux fois. Si t'as un chemin de longueur 6 et que tes 6 noeuds sont présents, tu n'as pas deux fois le même noeud dans le chemin.

Si ca te fait chier de vérifier ca à la fin, à chaque produit de matrice, tu mets la diagonale avec des chemins nuls. Lorsque tu auras ta matrice puissance 6, tu sauras que tu as exclusivement une boucle fermée sans cycle interne pour tes chemins dans la diago

[TheReveller]

Hum, peut-être alors que je ne comprends pas bien.

Pour une matrice 5x5 de positions uniques, ma matrice d'adjacence est

0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Et cette matrice élevée puissance 5 donne

204 205 205 205 205
205 204 205 205 205
205 205 204 205 205
205 205 205 204 205
205 205 205 205 204

Je ne dois pas bien comprendre l'astuce pour déterminer le chemin, désolé.

[fatal_error]

faut pas stocker des nombres mais des chemins.
Si n1 est en relation avec n2, tu stockes le chemin n1n2

en vrai, chaque case de la matrice contient une liste de chemins (dont les extremités sont les mêmes)
il faut donc prendre un produit cartésien tes deux cases en relation pour avoir la totalité des chemins résultant pour la dite case.