Scribd Logo
Importer

Bienvenue sur Scribd !

  • 21 vues

    TD2 Ai

    Transféré par

    Meryem Kachani
    Ce document présente trois exercices portant sur la résolution de problèmes par recherche. Le premier exercice demande d'appliquer différentes stratégies de recherche sur un graphe donné. Le deuxième exercice propose d'analyser un graphe d'états et d'appliquer les algorithmes A* et de recherche en largeur/profondeur. Le troisième exercice définit un problème de manipulation de pions et demande de construire le graphe d'états associé puis d'appliquer les algorithmes de recherche gloutonne et A*.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    TD2 Ai

    Transféré par

    Meryem Kachani
    21 vues2 pages
    Ce document présente trois exercices portant sur la résolution de problèmes par recherche. Le premier exercice demande d'appliquer différentes stratégies de recherche sur un graphe donné. Le deuxième exercice propose d'analyser un graphe d'états et d'appliquer les algorithmes A* et de recherche en largeur/profondeur. Le troisième exercice définit un problème de manipulation de pions et demande de construire le graphe d'états associé puis d'appliquer les algorithmes de recherche gloutonne et A*.

    Titre original

    TD2_AI

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document présente trois exercices portant sur la résolution de problèmes par recherche. Le premier exercice demande d'appliquer différentes stratégies de recherche sur un graphe donné. Le deuxième exercice propose d'analyser un graphe d'états et d'appliquer les algorithmes A* et de recherche en largeur/profondeur. Le troisième exercice définit un problème de manipulation de pions et demande de construire le graphe d'états associé puis d'appliquer les algorithmes de recherche gloutonne et A*.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    21 vues2 pages

    TD2 Ai

    Transféré par

    Meryem Kachani
    Ce document présente trois exercices portant sur la résolution de problèmes par recherche. Le premier exercice demande d'appliquer différentes stratégies de recherche sur un graphe donné. Le deuxième exercice propose d'analyser un graphe d'états et d'appliquer les algorithmes A* et de recherche en largeur/profondeur. Le troisième exercice définit un problème de manipulation de pions et demande de construire le graphe d'états associé puis d'appliquer les algorithmes de recherche gloutonne et A*.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    TD2 IA et Résolution des Problèmes

    Exercice1
    Considérez le graphique de recherche présenté à droite. S est l'état de départ et G est l'état
    de but. Toutes les arêtes sont bidirectionnelles.
    Pour chacune des stratégies de recherche suivantes, indiquez le chemin, son coût et
    complexités en temps et espace. Donner le calcul intermédiaire. (En cas d’égalité, utiliser
    l’ordre alphabétique)
    a) Profondeur
    b) Largeur
    c) Cout Uniforme
    d) Gourmande
    d) A*

    Exercice 2.
    Le graphe suivant est le graphe d’état d’un problème :
    Les chiffres indiqués entre parenthèses sont les valeurs de la fonction heuristique, et ceux
    qui ne sont pas entre parenthèses sont les coûts des actions permettant de passer d’un état
    à un autre. L’état initial est le noeud A.
    Q1. Analyse du graphe
    En observant le graphe, déduisez quel est l’état terminal, ou quels sont les états terminaux
    (i.e. les objectifs).
    L’heuristique utilisée est-elle admissible ? Pourquoi ?
    Q2. Recherche aveugle
    Sans appliquer l’algorithme, quel est d’après vous le type de recherche aveugle le plus
    adapté à ce problème : recherche en profondeur ou recherche en largeur ? Expliquez
    rapidement pourquoi.
    Q3. Recherche informée
    Appliquez l’algorithme A*. Détaillez le déroulement de l’algorithme pas à pas (avec du
    texte, comme en cours et en TP, inutile de donner l’arbre de recherche). A la fin, vous
    indiquerez quel est le chemin que l’algorithme a parcouru pour trouver la solution, et
    vous indiquerez aussi le chemin qui constitue la solution.
    La solution est-elle optimale ? Pourquoi ?
    Remarque importante : quand deux nœuds de la frange ont la même valeur, on les
    range dans l’ordre alphabétique.

    Exercice 3
    Nous considérons un monde avec 4 pions (A,B,C,D) non superposables. Ils peuvent être
    arrangés dans n’importe quel ordre, sauf A qui ne peut pas être plus à droite que D. Par
    exemple, ABCD et CBAD sont deux états possibles du monde, tandis que DCBA et
    CDAB ne sont pas possibles. Le monde peut être manipulé par une action de la forme
    echange(x, y) qui échange les pions des positions x et y. Par exemple echange(1, 2)
    transforme BCAD dans CBAD. Seules les actions echange(1, 2), echange(2, 3) et
    echange(2, 4) sont autorisées. Ils donnent un successeur uniquement si la situation
    atteinte est possible.
    Q1. Dessinez le graphe d’états.

    Q2. On suppose que l’état de départ est ADBC et l’état que l’on veut atteindre est
    CBAD. On suppose que chaque action coûte 1. Donnez une “bonne” heuristique h
    admissible (mais aussi différente de 0 pour les noeuds non-finaux) pour ce problème.
    Le principe de l’heuristique devrait être suffisamment général pour pouvoir
    s’appliquer à des problèmes similaires.

    Q3. Appliquez la recherche gloutonne avec votre heuristique. Si vous n’avez pas trouvé
    d’heuristique, utilisez l’heuristique h = (nombre de pions mal placés). Ne
    considérez pas les noeuds déjà développés. En cas d’égalité choisissez un nœud à
    développer au hasard.

    Q4. Appliquez la recherche A* avec votre heuristique. Si vous n’avez pas trouvé
    d’heuristique, utilisez l’heuristique h = (nombre de pions mal placés)/2. Ne
    considérez pas les noeuds déjà développés. En cas d’égalité choisissez un nœud à
    développer au hasard.

    Vous aimerez peut-être aussi