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

[tougi]

Le problème c'est que je ne pense pas que je puisse utiliser l'algorithme de Dijkistra sachant que j'ai plus de 10 000 noeuds, j'aurais une matrice trop grande.

Vois tu un algorithme à utiliser ?

Merci d'avance

[Logan Mauzaize]

Un moyen optimiser (en consommation mémoire) serait "d'arbriser" ton graphe (je le suppose non orienté) de sorte qu'il n'y ait pas de cycle. Ca revient à entièrement orienter le graphe.

La méthode que j'utilise pour calculer un PCC (je suppose que tes arrêtes n'ont pas de poids)

1. partir d'un ensemble de noeuds => "VISITÉS"
2. calculer/déterminer l'ensemble des noeuds voisins => "VOISINS"
3. nettoyer "VOISINS" pour supprimer les noeuds qui appartiennent à "VISITÉS" => "VOISINS_NON_VISITÉS" (non nécessaire dans le cadre d'un graphe sans cycle)
4. Tester les "VOISINS_NON_VISITES" (ici cela consiste à tester si la valeur associée correspond à la chaîne recherchée)
5. Si le test échoue, ajouter "VOISINS_NON_VISTÉS" dans "VISITÉS" et repartir à l'étape (2)

[tougi]

Merci Nemek, j'ai pris cette méthode.

Ce que j'aimerais bien savoir c'est qu'est ce qui est le mieux, je code en java, et la liste des noeuds "visités" est très conséquente.

A ton avis dois je stocker cette liste dans un fichier ou dans une liste ? ou autre ?

Merci

[Logan Mauzaize]

Tu remarqueras également que la recherche en "profondeur" n'est plus utilisée car contraire au principe du "plus court".

Si le volume de données est trop grand tu ne peux effectivement le garder en mémoire.

Un fichier indexé serait l'idéal avec comme clé l'identifiant d'un nœud et en valeur le nœud précédent (si tu as besoin de reconstruire un chemin).
Une base de données relationnelle est un bon exemple de fichier indexé ^_^

Mais si tu n'arrives pas à avoir en mémoire les variables de l'algorithme, je m'étonne que tu arrives à avoir en mémoire ton graphe complet.

Ensuite, le problème de l'algorithme c'est qu'il suppose que tes valeurs de départ et d'arrivée et un chemin entre eux existent. Sinon tout le graphe est parcouru. Si ton graphe n'a pas de propriété spéciale on ne peut faire mieux.

[tougi]

En fait, je vais faire des tests et fixer une variable d'arret, je sais que je peux aller à une profondeur de 10 000 noeuds environ donc mon algo s'arrete si j'atteins cette limite.

1) Autre question :

Quand j'applique la récursivité :

maMéthode(unNoeud){
on incrémente un compteur
Pour tous les noeuds fils{

si le noeud n'est pas visité{
on visite le noeud(Noeudfils)
et on applique la méthode maMéthode(Noeudfils)
}

}

Lorsque j'applique cela à la racine de mon graphe (ou arbre) mon algo va parcourir en premier tous les premiers noeuds jusqu'à atteindre un noeud qui n'a pas de fils (une feuille).
Il va ensuite remonter au niveau du graphe pour voir les noeuds qu'il n'a pas encore visité.
Est ce correct ?

2) Je vais expliquer comment marche mon algo.
En gros, mon algo trouve une première solution à une profondeur X.
Il continue à chercher d'autres solutions pour une profondeur < X.
De ce fait je peux obtenir toutes les solutions et je garde celle qui est la plus petite.

Merci pour vos réponses

[Logan Mauzaize]

En fait, je vais faire des tests et fixer une variable d'arret, je sais que je peux aller à une profondeur de 10 000 noeuds environ donc mon algo s'arrete si j'atteins cette limite.

C'est une solution un peu drastique ... Dans ce cas, il vaut mieux limiter le graphe que l'algorithme.

1) Autre question :

Quand j'applique la récursivité :

maMéthode(unNoeud){
on incrémente un compteur
Pour tous les noeuds fils{

si le noeud n'est pas visité{
on visite le noeud(Noeudfils)
et on applique la méthode maMéthode(Noeudfils)
}

}

Lorsque j'applique cela à la racine de mon graphe (ou arbre) mon algo va parcourir en premier tous les premiers noeuds jusqu'à atteindre un noeud qui n'a pas de fils (une feuille).
Il va ensuite remonter au niveau du graphe pour voir les noeuds qu'il n'a pas encore visité.
Est ce correct ?

C'est le principe du parcours en profondeur d'abord. Mais pas optimal dans le cadre d'une recherche d'un plus court chemin.

2) Je vais expliquer comment marche mon algo.
En gros, mon algo trouve une première solution à une profondeur X.
Il continue à chercher d'autres solutions pour une profondeur < X.
De ce fait je peux obtenir toutes les solutions et je garde celle qui est la plus petite.

Très mauvaise idée ... c'est comme si tu cherchais l'adresse de quelqu'un et que tu prenais tous les botins du monde
De plus ce sera moins optimale que ma solution.
Enfin cela ne te donnera pas le plus court chemin dans le cadre d'un graphe avec cycle.
Exemple de graphe non orienté avec cycle :
A - B
A - C
B - C

[tougi]

Merci à toi Nemek, j'ai utilisé ta méthode et ça à l'air de bien marcher.

Je reviendrais sur le forum si j'ai de nouveaux problèmes.

[Logan Mauzaize]

Ta marqué ton message en résolu mais pas le sujet (appui sur )

[tougi]

Désolé, je viens de modifier cela.

Merci encore pour votre aide