Discussion :

[Erable]

J'utilise le langage mapple (qui est facilement compréhensible, c'est un outil mathématique de programmation).

Soit G un graphe orienté qui contient éventuellement des boucles. On cherche, à partir d'un point donné de ce graphe (qu'on peut appeler l'origine, le point de départ...) le nombre de chemins possibles et par quels points passent ces chemins.

Exemple type de graphe:
http://img7.hostingpics.net/pics/572537Test_typeBIS.jpg

Un chemin doit forcément se terminer par un "cul de sac" ou un "point déjà obtenu"; on ignore les boucles.

Ici par exemple des chemins sont 1-7-8-5 ou 1-7-9-10-12.

Notez que dans dans mon algorithme les points sont appelés "paragraphes", donc le nombre de points est NombreParagraphes.

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
> with(linalg);  //On appelle le pack qui permet d'utiliser les fonctions sur les matrices
> L[1] := [3, 7]; L[2] := [6, 12]; L[3] := [4, 6, 11]; L[4] := [2, 12]; L[5] := []; L[6] := [4, 12]; L[7] := [8, 9]; L[8] := [10]; L[9] := [10]; L[10] := [5, 12]; L[11] := [4, 12]; L[12] := [];   //On entre les listes de liaisons: le paragraphe 1 est relié au 3 et au 7, etc
 
 
> NombreParagraphes := 12; //On entre le nombre de paragraphes (le nombre de points)
 
//On crée la matrice d'adjacence (faite de 0 sur la diagonale, de symbole infini quand il n'y a pas de liaison et de 1 quand il y en a), vous pouvez sauter ça
 
for i to NombreParagraphes do 
Ligne[i] := [infinity]; 
    for j from 2 to NombreParagraphes do 
    Ligne[i] := [op(Ligne[i]), infinity] end do 
end do; 
for i to NombreParagraphes do Ligne[i][i] := 0 
end do; 
for i to NombreParagraphes do 
    for j to nops(L[i]) do 
          if evalb(`in`(L[i][j], SetOf(integer))) then Ligne[i][L[i][j]] := 1 
          end if; 
      end do; 
end do; 
 
>MatriceAdjacence := matrix([Ligne[1]]); 
for i from 2 to NombreParagraphes do 
MatriceAdjacence := stackmatrix(MatriceAdjacence, Ligne[i]) 
end do; 
 
//On initialise les autres variables nécessaires pour l'agorithme
 
> depart := 1: destination := 12: path := [0]:  #On a déjà initialisé NombreParagraphes:=12;
 for j from 2 to NombreParagraphes do
path := [op(path), 0]:
 end do;
path;
tabou := [false];
for j from 2 to NombreParagraphes do
tabou := [op(tabou), false]:
end do;
tabou;
 
                    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[false, false, false, false, false, false, false, false, false, false, false, false]
 
 
//Voici l'algorithme récursif
 
> CheminsPossibles := proc (position, depth)
local i;
 
path[depth] := position;
 
if position = destination then
    for i to depth do path[i]; ` `
    end do;
end if;
 
tabou[position] := true;
 
for i to NombreParagraphes do
    if MatriceAdjacence[position, i] <> 1 or tabou[i] then                    CheminsPossibles(i, depth+1)
     end if;
end do;
 
tabou[position] := false;
 
 end proc;

Warning, `path` is implicitly declared local to procedure `CheminsPossibles`
Warning, `tabou` is implicitly declared local to procedure `CheminsPossibles`

Code :

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

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

Mon problème c'est ce message d'erreur... Est-ce qu'il y a un problème dans mon algorithme? ça m'étonnerait que mapple sature pour 12 points...

[Erable]

Notez que dans mapple, une liste commence à la case 1 et non à la case 0 comme en PHP par exemple. Donc Si L est une liste et L:=[2,3,5], L[0] n'a pas de sens. En revanche L[1]; affiche 2.

[Erable]

Je m'étais inspiré pour cet algorithme d'un trouvé sur le net, dans un autre langage. Le truc qui me troublait c'était pourquoi donner à une des variable le nom depth, je ne vois pas la signification...

[pseudocode]

Ton algo est sans doute une exploration récursive, la variable "depth" représente surement le niveau de la récursion, c'est à dire la longueur du chemin parcouru actuellement.