Discussion :

[tougi]

Bonjour,

j'ai mis en place un algo utilisant notamment l'algo de parcours en profondeur.
le but de mon algo est de partir de la racine d'un arbre et de trouver un noeud.
Les noeuds sont des mots.

Exemple : maMéthode(motDepart,motArrivee);
-> retourne True ou False

Le seul problème c'est que l'arbre possède une volumétrie très grande.

Voici la méthode récursive que j'appelle :

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
 
 
private static List<String> listeMotParcouru = new ArrayList<String>();
 
private static ResultatWordnet existe(ResultatAlgo resultat){
 
	Arbre arbre = new Arbre(null);
 
	// on incrémente le compteur
	resultat.setCompteur(resultat.getCompteur()+1);
 
	// on parcoure tous les mots résultats
	for (String unMot : resultat.getListeMot()){
		// si on trouve le mot final on arrete
		if (unMot.equals(resultat.getMotFin())){
 
			return resultat;
 
		}else{
 
			// si le mot n'a pas déjà été parcouru
			if (!listeMotParcouru.contains(unMot)){
				// on ajoute le mot parcouru
				listeMotParcouru.add(unMot);
 
				resultat.setListeMot(arbre.getAllChild(unMot));
				// si la liste n'est pas nulle
				if (resultat.getListeMot()!=null){
					// on appelle de manière récursive la méthode
					resultat = existe(resultat);
 
				}
 
			}
 
		}
 
	}
 
	return resultat;
 
}

et voici la classe ResultatAlgo :

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
public class ResultatWordnet {
 
	private String[] ListeMot;
	private int compteur;
	private String motDebut;
	private String motFin;
	public String[] getListeMot() {
		return ListeMot;
	}
	public void setListeMot(String[] listeMot) {
		ListeMot = listeMot;
	}
	public int getCompteur() {
		return compteur;
	}
	public void setCompteur(int compteur) {
		this.compteur = compteur;
	}
	public String getMotDebut() {
		return motDebut;
	}
	public void setMotDebut(String motDebut) {
		this.motDebut = motDebut;
	}
	public String getMotFin() {
		return motFin;
	}
	public void setMotFin(String motFin) {
		this.motFin = motFin;
	}
 
}

Pour ce qui est de la classe arbre, je n'ai pas accès au code mais c'est une classe contenant des mots. A partir d'un mot on peut obtenir la liste de ses fils.


Auriez vous une idée pour éviter l'erreur java Heap Space. En effet, j'arrive à parcourir en gros 500 noeuds, il serait bien que j'arrive à en parcourir plus.

Merci pour votre aide.

[Logan Mauzaize]

Tu peux augmenter la taille de la Heap mais tôt ou tard le problème surviendra à nouveau.
Voir http://jmdoudoux.developpez.com/cour...tion_memoire-3

La meilleur chose à faire serait de stocker tes résultats dans un fichier ou une base de données où la mémoire est disponible en quantité beaucoup plus importantes.

[tougi]

Merci pour ta réponse,

J'ai augmenté la taille de mon Heap, je peux parcourir plus de noeud, mais comme tu dis j'obtiens une erreur plus tard.

A ton avis que dois je mettre dans un fichier : la liste contenant les mots parcourus ?

Autre question :

Qu'est ce qui est le moins couteux, chercher un mot dans un fichier ou chercher un mot dans une liste ?

Merci

[bulbo]

Ce qui est le moins couteux en mémoire c'est de changer ta récursivité en une méthode itérative.

Bonne chance ça peut être une belle gymnastique parfois à réaliser.

[Edit]
Et ce qui ne doit pas aider du tout la mémoire c'est ta liste de mot parcourus.

Après je ne vois pas trop bien ce que fait ton algo ou ce que représente ton arbre.. moi ça me parait étrange de couper des branches dans ta recherche si tu as déjà vu le mot ailleurs, mais ya peut-être une raison à ça.

[/Edit]

Bulbo

[tougi]

Désolé pour mon ignorance mais je ne sais pas du tout ce qu'est une méthode itérative et encore moins comment passer d'une méthode récursive à une méthode itérative.

Pourrais tu m'éclaircir les idées ?

Merci

[bulbo]

Itération: une boucle while par exemple qui va parcourir ton arbre noeud après noeud.

Récursion: une méthode qui explore un noeud et se rappelle elle-même.

Je ne peux guère être plus explicite ne comprenant guère ta problématique et la structure de ton arbre.

Bulbo

[Logan Mauzaize]

Pour commencer

• ta liste "listeMotParcouru" grandit toujours, dans le pire des cas elle contient tout ton arbre, et je ne saisis pas l'interêt de stocker ça.
• ton algo s'arrête uniquement quand il a tout parcouru, sans vérifier qu'un des appels récursifs à terminer le boulot.

A ton avis que dois je mettre dans un fichier : la liste contenant les mots parcourus ?

Ne sachant pas la structure de ton arbre (trié/balancé ? doublons ?), ni la finalité de l'algorithme difficile de répondre.
S'agit-il de trouver l'ensemble des chemins de ton arbre qui commence par le mot "motDepart" et termine par le mot "motArrivee" ?

Qu'est ce qui est le moins couteux, chercher un mot dans un fichier ou chercher un mot dans une liste ?

Un fichier est moins couteux en espace mais plus couteux en temps d'accès.
La RAM est plus couteuse en espace mais moins couteuse en temps d'accès.

C'est un principe général aux mémoires (cache, vive, morte, flash, etc.) soit elle fait gagner en espace, soit en temps d'accès.
Si une mémoire était moins coûteuse en espace et en temps d'accès qu'une autre, elle remplacerait l'autre ! (ex: DDR1 -> DDR2 -> DDR3)

[tougi]

Merci pour vos réponses

ta liste "listeMotParcouru" grandit toujours, dans le pire des cas elle contient tout ton arbre, et je ne saisis pas l'interêt de stocker ça.

Ma liste sert à connaître les noeuds déjà parcourus pour éviter de repasser par un mot déjà vu. En fait, je me suis basé sur l'algorithme de parcours en profondeur.
Oui elle grandit tous le temps.

ton algo s'arrête uniquement quand il a tout parcouru, sans vérifier qu'un des appels récursifs à terminer le boulot.

Que dois je faire pour stopper mon algo ? un break ?

Ne sachant pas la structure de ton arbre (trié/balancé ? doublons ?), ni la finalité de l'algorithme difficile de répondre.
S'agit-il de trouver l'ensemble des chemins de ton arbre qui commence par le mot "motDepart" et termine par le mot "motArrivee" ?

En fait, la finalité de mon algo est à partir d'un arbre contenant des mots ayant des relations entre eux de calculer le nombre d'étape entre deux mots.
Donc, cela ressemble à un arbre sauf que les fils n'ont pas forcément un unique père. Donc ce n'est pas un arbre du même style qu'un arbre de décision.

Exemple : on part du mot voiture et on savoir le nombre d'étape pour aller à autoroute.

une voiture a comme relation :

• vitre
• roue
  • camion
  • moto
• porte
• essuie glace
• route
  • rapide
    • autoroute
  • lente
    • chemin de terre
    • route de ville

Donc la méthode retourne 3.

[Logan Mauzaize]

Ma liste sert à connaître les noeuds déjà parcourus pour éviter de repasser par un mot déjà vu.

Tu es dans un arbre avec un parcours en profondeur, tu ne peux évaluer deux fois le même noeud.

Que dois je faire pour stopper mon algo ? un break ?

Après l'appel récursif il faut vérifier si tu as un résultat. Ajoute un attribut qui indique si tu as un résultat.

En fait, la finalité de mon algo est à partir d'un arbre contenant des mots ayant des relations entre eux de calculer le nombre d'étape entre deux mots.
Donc, cela ressemble à un arbre sauf que les fils n'ont pas forcément un unique père. Donc ce n'est pas un arbre du même style qu'un arbre de décision.

Ca s'appel donc un graphe, et tu cherches un plus court chemin entre deux noeuds de ton graphe. Tu peux trouver quelques détails ici http://fr.wikipedia.org/wiki/Probl%C...de_cheminement

Si t'es pas assez matheux pour digérer, reviens poser tes questions