1. Est-ce que h1 et h2 sont admissibles.
On calcule d’abord h*, le vrai cout (donne dans le tableau). On verifie qu’on a toujours h1(n)
≤h*(n) pour tout n mais h2(C) > h*(C), donc h1 admissible mais pas h2
2. Est-ce que h1 domine h2 ou h2 domine h1 ? Justifiez.
Ni l’un ni l’autre. D’apres le cours, on ne peut parler de domination que si les deux heuristiques
sont adminissibles. Ou alors, on a h1(B) > h2(B) et h2(C) > h1(C).
3. Est-ce que h3 = max(h1, h2) est admissible ?
Non. h3(C) > h*(C)
4. Appliquez la recherche gloutonne en utilisant h2.
On peut donner un arbre ou la liste des noeuds. Ici:
(A,10)
(C,8)(D,11)
(B,2)(H,4)(F,6)(A,10)(D,11)
(I,0)(G,3)(H,4)(F,6)(E,9)(A,10)(D,11)
Et on s’arrˆete avec I et le chemin A,C,B,I
5. Appliquez la recherche A∗ en utilisant h1. Donnez la suite des noeuds d´evelopp´es.
On indique pour chaque noeud sa valeur f = g + h:
(A,10=0+10)
(C,10=5+5)(D,15=5+10)
(F,10=5+2+3)(H,11=5+3+3)(B,13=5+3+5)(D,15)(A,20=5+5+10)(D,21=5+6+10)
(H,11)(G,13=5+2+3+3)(B,13)(C,14=5+2+2+5)(B,15=5+2+3+5)(D,15)(A,20)(D,21)
(I,12=5+3+4)(G,13)(B,13)(C,14)(B,15)(D,15)(C,16=5+3+3+5)(A,20)(D,21)
Et on s’arrête avec I et le chemin A,C,H,I.
6. Appliquez la recherche A∗ en utilisant h2. Donnez la suite des noeuds développés.
On pourrait dire qu’on ne peut pas faire A* puisque h2 n’est pas admissible (car A∗ est d
´efinie
avec des heuristiques adminissible), ou alors on donne:
(A,10=0+10)
(C,13=5+8)(D,16=5+11)
(B,10=5+3+2)(H,12=5+3+4),(F,13=5+2+6)(D,16)(A,20=5+5+10)(D,22=5+6+11)
(H,12),(I,13=5+3+5+0)(F,13)(G,15=5+3+4+3)(D,16)(F,17=5+3+3+6)(C,19=5+3+3+8)(A,20)
(E,22=5+3+5+9)(D,22)
(I,12=5+3+4),(I,13)(F,13)(G,15)(C,16=5+3+3+5)(D,16)(F,17)(C,19)(A,20)(E,22)(D,22)
Et on s’arrˆete avec I et le chemin A,C,H,I.
7. Appliquez la recherche A* en utilisant h3. Donnez la suite des noeuds developpes.
On pourrait dire qu’on ne peut pas faire A* puisque h3 n’est pas admissible (car A* est d´efinie
avec des heuristiques adminissible), ou alors on donne:
(A,10=0+10)
(C,13=5+8)(D,16=5+11)
(H,12=5+3+4)(F,13=5+2+6)(B,13=5+3+5)(D,16)(A,20=5+5+10)(D,21=5+6+10)
(I,12=5+3+4+0)(F,13)(B,13)(D,16)(C,19=5+3+3+8)(A,20)(D,21)
Et on s’arrete avec I et le chemin A,C,H,I.
8. Montrez que pour deux heuristiques admissibles h1 et h2, h3 = max(h1, h2) est admissible.
h1 et h2 admissible implique pour tout noeud n h1(n) ≤ h∗(n) et h2(n) ≤ h∗(n). Donc pour tout
noeud n on a max(h1(n), h2(n)) ≤ h∗(n) donc max(h1, h2) est admissible.
9. Si vous avez le choix entre trois heuristiques admissibles h1, h2 et h3 = max(h1, h2) laquelle
choisissez-vous ? Justifiez brievement.
h3 puisque elle estime le mieux la vraie distance h∗.
1- α-β coupe les deux 10, le 11, et le troisième fils de la racine. Résultat:14
2- α-β coupe le deuxième fils de chaque nœud min, et le troisième le cas échéant. Résultat:16
3. Premier résultat: la vraie valeur est ≥14. Deuxième résultat: la vraie valeur est ≤16.
4. Il faut que a≤x≤b. Ce qui pose un problème car on ne connait pas x, qui est la valeur cherchée. Il
faut donc trouver un compromis entre des alpha/beta très grands qui n'élaguent pas beaucoup et des
alpha-beta mal définis qui engendrent une imprécision mais coupent plus de branches. ! heuristiques
a la A* (cf SSS*).
1. Le résultat est-il optimal en choisissant l’objet le plus cher parmi ceux qui peuvent tenir dans
le sac, puis le plus cher parmi ceux qui peuvent encore tenir . . . Expliquez par un exemple.
Correction: Le résultat n'est pas optimal, considérons l'exemple où on a : n=5, W=10, v(8,6,5,3,1)
w=(10,4,6,5,3); dans ce cas on optera pour l'objet n° 1 ayant une valeur=8 alors que la sol optimale
est de prendre le 2eme et le 3eme pour une valeur=11
2. Écrivez un algorithme glouton qui résout ce problème.
Correction.
D'abord il faut trier le vecteur v et w par ordre de v décroissant
Puis, on prendra les objets dans l’ordre tant qu’ils rentrent dans le sac :
Procédure Butin (Entrée v,w: tableau [1..n] réel; W: Entier; Sortie I: Entier, T: Réel); Début Var P :
Réel; Trier (v,w);
I:=0 ; P:=0 ; T:=0 Tant que i<n et P+w[i+1]<W
Faire P=P+w[i+1]; T=T+v[i+1]; i:=i+1; Fait;
/* Les objets dans le sac à dos sont de 1..i leur valeur est T */
Fin;
Procédure Trier (Entrée/Sortie v,w: tableau [1..n] réel);
Début Var i,j,m : Entier; Pour i:=1 à n-1 Faire m:=i;
Pour j:=1 à n Faire Si v[m]>v[j] Alors m:=j; Fait
Si i<>m Alors Permuter (v[i],v[m]); Permuter (w[i],w[m]); Fsi; Fait; Fin;
----------------------------------------------------------------------
Pour i=2 à n faire O(n) k:=i-1 ; O(1) x:=T[i] O(1)
Tantque T[k]>x Faire O(n) T[k+1]:=T[k] ; O(1)
k:=k-1 O(1) FTq T[k+1]:=x FPour
O(n2)
Exo2
i n;
S 0;
Tant que (i > 0) faire
j 2*i ;
Tant que (j > 1) faire
S S+(j-i)* (S+1) ;
j j-1 ;
Fin TQ;
i i div 2 ;
Fin TQ;
La boucle interne (TQ j > 1) fait 2*i itérations.
Pour i=n la boucle interne fait (2n - 1) itérations,
Pour i=n/2, elle fait (n -1) itérations,
puis n/2 - 1,
n/4 - 1,
n/8 -1,
:
2-1.
Donc le nombre total d'itérations est : 2n-1 + n-1 + n/2 - 1 +n/22 - 1 + n/23 - 1 + ... + 2-1 = 4n - log2n
donc en O(n).
Le sac a dos du cambrioleur
1. Le résultat est-il optimal en choisissant l’objet le plus cher parmi ceux qui peuvent tenir dans le
sac, puis le plus cher parmi ceux qui peuvent encore tenir . . . Expliquez par un exemple.
Correction: Le résultat n'est pas optimal, considérons l'exemple où on a : n=5, W=10, v(8,6,5,3,1)
w=(10,4,6,5,3); dans ce cas on optera pour l'objet n° 1 ayant une valeur=8 alors que la sol optimale
est de prendre le 2eme et le 3eme pour une valeur=11
2. Écrivez un algorithme glouton qui résout ce problème.
Correction.
D'abord il faut trier le vecteur v et w par ordre de v décroissant
Puis, on prendra les objets dans l’ordre tant qu’ils rentrent dans le sac :
Procédure Butin (Entrée v,w: tableau [1..n] réel; W: Entier; Sortie I: Entier, T: Réel);
Début
Var P : Réel;
Trier (v,w);
I:=0 ; P:=0 ; T:=0
Tant que i<n et P+w[i+1]<W
Faire P=P+w[i+1];
T=T+v[i+1];
i:=i+1;
Fait;
/* Les objets dans le sac à dos sont de 1..i leur valeur est T */
Fin;
Procédure Trier (Entrée/Sortie v,w: tableau [1..n] réel);
Début
Var i,j,m : Entier;
Pour i:=1 à n-1
Faire m:=i;
Pour j:=1 à n
Faire Si v[m]>v[j]
Alors m:=j; Fait
Si i<>m Alors Permuter (v[i],v[m]); Permuter (w[i],w[m]); Fsi;
Fait;
Fin;
