Scribd
Importer
824 vues3 pages

Algorithmes de Recherche Heuristique: Intelligence Artificielle - TD 2

Le document présente trois exercices sur les algorithmes de recherche heuristique comme A*. L'exercice 1 décrit une fonction de successeur, heuristique et but pour A*. L'exercice 2 applique A* à un problème de voyage en Roumanie. L'exercice 3 concerne un problème de plus court chemin sur une carte avec différentes heuristiques.

Transféré par

Ameni Boughanmi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
824 vues3 pages

Algorithmes de Recherche Heuristique: Intelligence Artificielle - TD 2

Le document présente trois exercices sur les algorithmes de recherche heuristique comme A*. L'exercice 1 décrit une fonction de successeur, heuristique et but pour A*. L'exercice 2 applique A* à un problème de voyage en Roumanie. L'exercice 3 concerne un problème de plus court chemin sur une carte avec différentes heuristiques.

Transféré par

Ameni Boughanmi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

ISSATM 2 S.

Intelligence Artificielle – TD 2
ALGORITHMES DE RECHERCHE HEURISTIQUE

Exercice 1 :

Le tableau suivant défini les fonctions successeurs succ, heuristique h et but goal. La fonction
successeur succ(s) retourne un ensemble de paires {(s1, c1), …, (sn, cn)} tel que s est un état
donné, si est un état successeur, et ci est le coût pour passer de l’état s à si. La fonction h(s)
retourne est estimation de la distance entre un état s et un état satisfaisant au but.

a) Donnez une trace d’exécution de l’algorithme A* en utilisant les fonctions définies


précédemment et en considérant l’état initial s0. Pour chaque état dans les listes open
et closed, donnez ses valeurs f et g.

b) La fonction heuristique h est-elle admissible? Justifiez.


c) Si la fonction but était modifiée tel que B(s6)=Faux, que se passera-t-il? Donnez le maximum
d’observations que vous pouvez trouver.

Exercice 2 :

Appliquez l’algorithme A* au problème du voyage en Roumanie en appliquant l’heuristique de


la distance à vol d’oiseau. Vous supposerez que vous voulez voyager de Lugoj à Bucharest.
Pour chaque nœud, vous donnerez les valeurs de f , g et h. Si un même état apparaît dans deux
nœuds différents, avec deux valeurs de f différentes, on conserve seulement celui avec la
meilleure (la plus petite) valeur de f.

B.SELLAMI 1 2021/2022
ISSATM 2 S.I

Exercice 3 :

Considérez la carte suivante. L’objectif est de trouver le chemin le plus court de A vers I. On
donne également trois heuristiques, h1, h2 et h3.

B.SELLAMI 2 2021/2022
ISSATM 2 S.I

1) Appliquer la recherche gloutonne en utilisant h3. Donner la suite des noeuds


développés.
2) Appliquer la recherche A* en utilisant h1. Donner la suite des noeuds développés.
3) Appliquer la recherche A* en utilisant h3. Donner la suite des noeuds développés.
4) Appliquer la recherche A* en utilisant h4. Donner la suite des noeuds développés.
5) Si vous avez le choix entre trois heuristiques admissibles h1, h2 et h3 = max(h1,h2)
laquelle choisissez-vous ? Justifier.

B.SELLAMI 3 2021/2022

Vous aimerez peut-être aussi