Discussion :

[chakirlbr]

bonjour .
j'ai une petit erreur sur la récursivité tabou (j'ai trouver dans le forum ) , j'ai changer le 0 dans la fonction explore par un autre nombre ( entre 1_3) parce que il peut que le point d’arriver être sur la sommet 2 ou 3 .
mais il donne un erreur de Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5 .

Code Java :

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

1
2
3
4
5
public static void main(String[] args) {
        taboo a =new taboo();
        a.explore(1,1);
 
    }

la classe taboo :

Code Java :

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
 
public class taboo {
        // nombre de sommets dans le graphe
        int n=5;
         // matrice d'adjacence du graphe 
        int[][] adjacencymatrix = new int[][] {
	new int[] {1,1,1,0,0}, //    1
	new int[] {1,1,1,1,0}, //  / | \
	new int[] {1,1,1,1,0}, // 0  |  3 - 4
	new int[] {0,1,1,1,1}, //  \ | /
	new int[] {0,0,0,1,1}, //    2       
        };
        // stockage du chemin pendant l'exploration recursive
        int[] path = new int[n];
        // verrou pour la recherche taboo (tous initialisés à "false" par défaut)
        boolean[] taboo = new boolean[n];
        // sommets de départ/arrivé souhaités
        int source=0;
        int target=4; 
 
     void explore(int position, int depth) {
	path[depth]=position; 
 	// on est sur le sommet d'arrivé -> fini
	if (position==target) {
		// affiche la solution
		for(int i=0;i<=depth;i++) System.out.print(path[i]+" ");
		System.out.print("\n");
		return;
	}
	// sinon...
	taboo[position]=true; // on pose un caillou
	// on explore les chemins restants
	for(int i=0;i<n;i++) {
		if (adjacencymatrix[position][i]==0 || taboo[i]) continue;
		explore(i,depth+1);
	}
	taboo[position]=false; // on retire le caillou
}
}

le programme affichera les différents lignes à prendre et les stations où doit se faire le changement.

j'ai posé une image qui donne un exemple (les point sont des Station) :



et s'il vous plait peut il m'expliquer le tableau adjacencymatrix
merci d'avance .

[dourouc05]

et s'il vous plait peut il m'expliquer le tableau adjacencymatrix

Un petit coup de Wikipedia sur ce terme te donne directement une solution : http://en.wikipedia.org/wiki/Adjacency_matrix. Le premier point se résoudra alors relativement facilement avec un débogueur (voir les forums Java pour l'emploi de ce type d'outils).

[Flodelarab]

Bonjour,

n'aurais-tu pas confondu la classe et le constructeur ?