Algorithme Scout (IA)

Version imprimable

Bonjour, j'ai une petite question sur l'algorithme Scout.

J'ai compris le principe d'évaluation des noeuds mais je ne comprend pas bien dans quel cas on effectue la procédure Test avec > plutôt qu'avec ≥ ?
Le cours que j'ai sous les yeux me ferait pencher pour l'utilisation de > lorsque le noeud que l'on entre dans Test est un noeud MAX et ≥ si c'est un noeud MIN mais bon.... Vu le nombre d'exemple que j'ai réussi à trouver, j'ai pas vraiment de moyen pour vérifier....
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Procedure Test(n,v,c) // n est le noeud à évaluer // v la valeur seuil du noeud // c le prédicat de comparaison à savoir > ou ≥ si n est un noeud terminal alors retourner c(h(n),v); si n est Max alors soit S = {s1 ... si} la liste des fils de n; pour j allant de 1 à i faire si Test(sj,v,c) alors retourner vrai; retourner faux; sinon soit S = {s1 ... si} la liste des fils de n; pour j allant de 1 à i faire si ¬Test(sj,v,c) alors retourner faux; retourner vrai;
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 Procedure Eval(n) // n est le noeud à évaluer si n est un noeud terminal alors retourner h(n); soit S = {s1 ... si} la liste des fils de n; soit v = Eval((s1)); pour j allant de 2 à i faire si sj est Max alors si Test(sj,v,>) alors v ← Eval(sj); sinon si ¬Test(sj,v,≥) alors v ← Eval(sj); retourner v;
Merci d'avance à ceux qui seront capable de m'expliquer un peu la différence ;)

20/06/2007, 16h12
syldras

par exemple:
Si (a > b) alors .... //a doit etre obligatoirement plus grand que b pour pouvoir entrer dans ton Si.

Si (a ≥ b)alors.... // ≥ s'ecrit aussi >= cela vaut dire que a doit etre superieur ou egal a b pour pouvoir entrer dans ton Si.

j'espere que cela pourra t'aider

Bah jusqu'ici l'implémentation que j'en ai fait donne ça :

Code:

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
import java.util.*;
class scout
{
 
 
	public static boolean Test(noeud n, int v, String c)
	{
		LinkedList s;
		noeud m;
		boolean res=false;
		if (n.listeid.size() == 0)
			System.out.println("Noeud "+n.id+" : "+n.val+""+c+""+v);
		if (n.type == "MAX")
		{
		  s=n.listeid;
		  ListIterator it = s.listIterator();
		  for (int i=1;i<s.size();i++)
			{
			 m = (noeud)it.next();
			 if (Test(m,v,c))
				res= true;
			 else
				res= false;
			}
		}
		else
		{
		  s=n.listeid;
		  ListIterator it = s.listIterator();
		  for (int i=1;i<s.size();i++)
			{
			 m = (noeud)it.next();
			 if (!(Test(m,v,c)))
				res= false;
			 else
				res= true; 
			}
		}
		return res;
	}
 
	public static int Eval(noeud n)
	{
		LinkedList s;
		noeud m;
		int v;
		if (n.listeid.size() == 0)
		{System.out.println("Noeud "+n.id+" : "+n.val);	return n.val;}
		s=n.listeid;
		ListIterator it = s.listIterator();
		m = (noeud)it.next();
		v = Eval(m);
		for (int i=1;i<s.size();i++)
			{
			 m = (noeud)it.next();
			 if (m.type == "MAX")
				{
				if (Test(m,v,">"))
				v = Eval(m);
				}
			else
				{
				if (!(Test(m,v,"=>")))
				v = Eval(m);
				}
			}
		return v;			
	}
 
	public static noeud inputnoeud(int n,int nbne,String typen)
	{
		int num,val,nbf;
		String type;
		LinkedList l = new LinkedList();
		System.out.println("Noeud "+nbne);
		num = nbne;
		if (typen=="MAX")
			type="MIN";
		else
			type="MAX";
		System.out.println("Type du noeud "+type);
		System.out.println("Valeur du noeud");
		val = Clavier.lireInt();
		System.out.println("Nombre de fils ?");
		nbf = Clavier.lireInt();
		if (nbf != 0)
			{
			num = num*10;
			for(int i=1;i<nbf+1;i++)
				{
				num = num+1;
				l.add(inputnoeud(nbf,num,type));
				}
			}
		noeud f = new  noeud(num,type,val,l);
		return f;
	}
 
	public static void main (String args[]) 
	{
 
		System.out.println("Racine de l'arbre");
		System.out.println("Nombre de fils");
		int nb,nbf;
		nb = Clavier.lireInt();
 
		LinkedList lc = new LinkedList();
		for(int j=1;j<nb+1;j++)
			{
			lc.add(inputnoeud(1,j,"MAX"));
 
			}
 
 
		noeud r = new noeud(0,"MAX",0,lc);
 
		System.out.println("Resultat Finale : "+Eval(r));
	}
}

avec pour mes noeuds :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;
class noeud
{
	public int id,val;
	public String type;
	public LinkedList listeid;
 
	public noeud() {}
 
	public noeud(int id, String type, int val, LinkedList listeid)
	{
	this.id = id;
	this.type = type;
	this.val = val;
	this.listeid = listeid;
	}
}

Mais on peut pas dire que les résultats soient vraiment concluant... Je dois avoir zapper un trucs et j'arrive pas à trouver d'où ça vient.

Résultat sur un arbre de ce genre

http://devilbilly.free.fr/scout.png

Le résultat sera 60 au lieu de 50..... et bon, mon implémentation de l'algo visite le noeud 23 ce qu'il ne devrait pas faire normalement...

Normalement, je devrais passer par f1,f2,f211,f22
puis directement à f3,f31,f311,f32,f33
puis repasser à nouveau dans f3,f31,f311,f312,f32,f33 pour terminer avec un r qui vaux 50

Bon, je crois que je commence à avoir une idée de là où ça vient, à mon avis voilà la portion de code en cause :
Code:

1 2 3 4 5 6 7 public static boolean Test(noeud n, int v, String c) { LinkedList s; noeud m; boolean res=false; if (n.listeid.size() == 0) System.out.println("Noeud "+n.id+" : "+n.val+""+c+""+v);
Je vais approfondir ça ce soir voir ce que ça donne...

21/06/2007, 08h36
syldras

En faite en quoi consiste ton code que doit-il faire?
Explique moi a quoi servira ton code.
21/06/2007, 10h44
Devilbilly

:oops: désolé, je suis tellement dedans en ce moment....
L'algorithme Scout fait parti des quelques algo utilisé en IA pour parcourir un arbre et en remonter la plus grand valeur à travers des noeud min/max
Dans le même style tu as l'algo alpha béta, A*, SSS*...
Cacun à ses avantages et ses inconvénients, en l'occurence Scout est à peu près aussi performant que alpha béta sauf dans un cas où il le domine, si l'arbre est profond et à peu de branchement.
Dans l'algo alpha béta avec coupe alpa béta par exemple, l'algo passe la branche la plus à droite, remonte d'abord la valeur du noeud terminal le plus à gauche puis fait des comparaison et change de valeur en fonction des noeuds traversés (MIN/MAX), on peut en plus lui rajouter une technique d'élagage (ou coupe alpha/béta) qui va te permettre de ne pas visité toutes les branches.
L'algo Scout visite d'abord la branche la plus à gauche, stock la valeur du noeud dans v, puis compare v avec les autres noeuds via la procedure Test.
Si le noeud que l'on doit tester est un noeud MAX, alors on test avec > et chaque noeud fils répondra, de manière récursive vrai ou faux si la valeur de chaque noeud fils est sup à v.
Si tous les noeuds fils répondent VRAI, c'est qu'il y a un noeud v" qui est supérieur à v, et par conséquent on repart dans la même branche à la recherche de v", puis on stock v" à la place de v
Pour un noeud MIN, Test utilise ≥ et va attendre une réponse fausse de la part de ses fils, donc si l'un de ses fils renvoie faux au Test, c'est que le noeud MIN examiner va recevoir une valeur inférieur à v, par conséquent ça ne nous interesse plus et on passe au noeud suivant.

voilà le parcours de l'arbre, c peut être plus simple à comprendre comme ça

http://devilbilly.free.fr/scoutsuite.png

En noir c'est le premier passage:
Donc en résumé ça donne :
v = Eval(f1)
v = 10
On test alors f2 qui lui même va vouloir tester :
{f21, f22, f23}
f21 va tester f211 qui renvoie donc 20, 20 > 10
on test f22, 5 > 10 est faux, par conséquent on passe direct à f3 sans même s'occuper de f23.
on va continuer de la même manière pour f3 sauf que pour f3, toutes les valeurs sont fx sont sup à 10, donc on va retester la branche pour trouver quelle valeur est recherché pour le noeud f3 (donc une valeur MIN)
en Résultat on devra donc trouver un r = 50

Voilà, désolé si je suis pas très clair mais bon....
21/06/2007, 11h52
syldras

pourquoi devrait tu trouvé 50
D'apres ton dessin la valeur minimal dans f3 est 40
donc r devrait etre egal a 40
21/06/2007, 12h04
Devilbilly

Oui mais le noeud f31 est un noeud MAX, donc il va récupérer la plus grande valeur entre f311 et f312 qui eux sont des MIN
dès lors f31 à pour valeur 60.
Par la suite, comme f3 est un noeud MIN, il va choisir parmis les 3 noeuds MAX f31, f32, f33 lequel des 3 est le plus petit, f32 étant le plus petit, f3 prend comme valeur 50
r étant un noeud MAX, i lrécupère donc la valeur la plus grand parmis f1,f2 et f3 c'est à dire 50.
21/06/2007, 13h33
syldras

montre moi la parti du code ou tu fé la recherche de ton min

Bah en fait mon problème de base et réglé, j'ai un pote qui m'a expliqué quand on se servait de > et de ≥ et la je suis en pleine révision.
L'algo en lui même est tiré d'un bouquin d'IA que j'ai essayé d'implémenter en java pour m'aider, mais finalement je dois avoir une erreur lors de me return, doit y avoir un booléen qui est à true au lieu d'être à false ou vice versa.

En ce qui concerne l'évaluation des noeuds min :
Code:

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 public static int Eval(noeud n) { LinkedList s; noeud m; int v; if (n.listeid.size() == 0) {System.out.println("Noeud "+n.id+" : "+n.val); return n.val;} s=n.listeid; ListIterator it = s.listIterator(); m = (noeud)it.next(); v = Eval(m); for (int i=1;i<s.size();i++) { m = (noeud)it.next(); if (m.type == "MAX") { if (Test(m,v,">")) v = Eval(m); } else { if (!(Test(m,v,"=>"))) v = Eval(m); } } return v; }
C la portion de code en rouge qui évalue les noeuds fils de r, donc le problème vient de mon implémentation de la procédure Test à priori.
Mais bon, là je laisse tomber pour cette semaine, je reverrai ça la semaine prochaine une fois mes exams passé, parce que j'ai pas que mon IA à bosser :mrgreen:
Dès que j'aurai trouvé d'où ça vient je mettrai le code corrigé ;) on sait jamais, ça peut toujours être utile à quelqu'un...