Apprendre Maple

[Erable]

Position du problème (si je ne suis pas assez clair, n’hésitez pas à demander des précisions) :

Soient L1, L2,…, Ln des listes, vides pour certaines, d’autres contenant au moins un chiffre allant de 1 à n. Ces listes représentent en fait des liaisons entre numéros. Par exemple, si L2 vaut [3,50], alors le chiffre 2 est relié à 3 et 50 (pour être plus précis, le chiffre 2 mène au 3 et au 50, mais ces derniers ne mènent sans doute pas au 2 ; par exemple on peut avoir L3 qui vaut [5,6]). Ces liaisons ne sont donc pas des relations d’équivalence (elles ne sont pas symétriques, ni réflexives d'ailleurs ni même transitives).

On cherche à connaître tous les chemins possibles partant du chiffre 1 (L1 est non vide).
Exemple du chemin 1-2-5-10-50 : il sera sous forme de liste, telle que L1_2_5_10_50 vaudra [1,2,5,10,50]. Il me semble que c’est une notation sympa puisqu’on peut lire directement le chemin sans afficher la liste et de toute façon il faut avoir des noms de listes différents pour chaque chemin.

On ignorera dans un premier temps les boucles (un chemin ne peut contenir deux fois le même chiffre), même si par la suite on sera en réalité plus souple (on n’aura pas le droit d’avoir dans la liste deux fois deux chiffres qui se suivent, par exemple il sera interdit d’avoir L6_2_3_5_6_2_3 (qui vaudra [2,3,5,6,2,3]) mais on pourra avoir L6_2_3_5_2_7 (qui vaudra [2,3,5,2,7]), en fait je veux prendre en compte les boucles, mais pas trop, enfin c’est un aspect secondaire du problème).
Un chemin est fini lorsque le dernier chiffre qu’il a été amené à contenir ne possède pas de liaisons (donc la liste correspondante est vide).
Tout chiffre appartient à au moins une liste (mais la liste du chiffre peut être vide).



Mon idée de l’algorithme :


Tant qu’il existe un chemin non terminé faire :
# cette boucle while sera finie car un chemin contiendra au plus n chiffres

Pour i variant de 1 à n, si L1[i]=1, créer la liste L1_i :=[1,i]

Pour j variant de 1 à n, si Li[j]=1, si j n’appartient pas à L1_i, créer L1_i_j:=[op(L1_i),j]

Pour k variant de 1 à n, si Lj[k]=1, si k n’appartient pas à L1_i_j, créer L1_i_j_k:=[op(L1_i_j),k]

Etc…



Le problème c’est qu’on doit avoir n noms de variables internes (i,j,k…) et que je ne vois pas du tout comment coder ça… Peut-être que je ne prends pas le problème par le bon bout…

Déjà si vous m’aidez pour ça, ce sera pas mal. Ensuite j’essaierai de prendre en compte les boucles (en disant qu’on n’a pas le droit de passer par deux mêmes chiffres successifs mais qu’on peut repasser par un même chiffre) mais je devrais y arriver tout seul.


Merci à tous

[ALS]

Bonjour,
le mieux serait de représenter vos différentes listes en formant un graphe orienté, de sommets 1,2,..n, un peu comme dans cet exemple: http://alamanya.free.fr/themes/dijkstra.htm , mais sans les distances.
A plus tard.

[Erable]

Oui, je connais l'algorithme de Dijkstra et ai pensé à faire une matrice d'adjacence (ça serait plus la classe), simplement je trouvais la méthode des listes plus simple... même si après je ne vois pas comment faire !
Bon je vais donc voir ça, ça devrait m'éclairer vu qu'il y a le code, en espérant qu'avec ça je trouve le moyen de conserver tous les chemins possibles.
Merci et bravo à celui qui a écrit tout ça !

[Erable]

Bon, j'ai réussi à transformer mes données en matrice d'adjacence.

J'ai essayé de trouver mon propres algorithme pour calculer les chemins possibles (sans repasser une fois par le même endroit, pour commencer), mais c'est assez dur. Quant à l'algorithme de Dijkstra, il faudrait trop adapter le code que j'ai du mal à comprendre (j'ai compris le principe).

En voguant sur Internet, j'ai trouvé qu'il y avait une technique, la recherche tabou, qui peut être pas mal même si j'ai trouvé peu d'explications dessus. J'ai trouvé aussi une idée assez sympa apparemment :

"Tu peux calculer les puissance successives de la matrice d'adjacence, afin de connaitre le nombre de chemins de longueur 'n' entre 2 sommets donnés.

Pour identifier précisement chaque chemin tu peux soit faire le calcul inverse, soit conserver les éléménts de la matrice qui ont servis aux calculs intermédiaires."

Sauf que... c'est très peu expliqué. D'autant plus que le carré de ma matrice d'adjacence, c'est une matrice avec que des infinis. Donc à moins que vous compreniez, vais essayer la technique tabou (même si il est interdit d'en parler ).

[Erable]

J'essaie la méthode tabou... sans succès:


> depart := 1; destination := 12;

> CheminsPossibles := proc (position, depth)
local path, i; path[depth] := position;

#on est sur le sommet d'arrivé -> fini
if position = destination then
for i to depth+1 do path[i]; ` `
end do
end if;

#sinon...
tabou[position] = true;

#on explore les chemins restants
for i to NombreParagraphes-1 do
if MatriceAdjacence[position, i] = 0 or tabou[i] then CheminsPossibles(i, depth+1)
end if
end do;

tabou[position] = false #on retire caillou

end proc;

> CheminsPossibles(depart, 1);
Error, (in CheminsPossibles) too many levels of recursion



Remarque: après copier-coller, il manque des points-virgules mais ils y sont (enfin des deux points ":").

[Erable]

Vu que cet algorithme risque de ne pas gérer beaucoup de points, j'essaie de trouver un autre moyen de trouver le nombre de chemins possibles. J'aimerais arriver à une inégalité, encadrer le nombre de chemins possibles par le nombre de points et/ou le nombre de liaisons.
Après avoir cru trouver quelque chose, je découvre que ça ne fonctionne pas...

[zozo]

Salut,
Déjà, dans tes affectations de variables, tu dois remplacer tous tes = par des :=
A+

[Erable]

Bien vu…

Bon j’ai initialisé les listes pour qu’elles aient la bonne taille mais même après ça, maple a l’air de trouver ça trop compliqué. Avec plus de points, je dis pas, mais 12…

[Erable]

C'est la faute à maple ou ma faute à moi?

[zozo]

Bonjour,
Pour qu'on puisse tester, il faudrait l'ensemble du code.
Il manquerait pas une portion du code, notamment la définition de la matrice d'adjacence?

[Erable]

Ok. Je crée la matrice d'adjacence à partir de listes. C'est pas très compliqué (si le point ou paragraphe, c'est la même chose) X est relié au point Y, alors le croisement entre la ligne X et la colonne porte un 1. Sinon, on a des symboles infinis ou 0 sur la diagonale.
Je crée d'abord les lignes, ensuite je crée la matrice. C'est un code qui marche, testez-le juste pour bien comprendre ce qu'est cette matrice.

[zozo]

J'ai testé en mettant path et tabou en global dans ta procédure, ça n'a pas l'air de changer gd chose.
Sorry.

[Erable]

Ce sont déjà des variables globales non? Elles sont définies au dehors de la procédure.
Non mais il doit y avoir du mauvais dans mon code; j'ai du mal à coder cet algorithme récursif.

[Erable]

No answers?