IA et Machine Learning - Recherche de Solution - Cours - 2024-2025

Université de Gabes Institut Supérieur D’informatique et Multimédia de Gabes IA et Machine Learning Chapitre III Recherche de solution Enseignante : Ines NJEH CHAKER Fillière: LISI3 2024-2025 Défis relevés en solution...

Université de Gabes Institut Supérieur D’informatique et Multimédia de Gabes IA et Machine Learning Chapitre III Recherche de solution Enseignante : Ines NJEH CHAKER Fillière: LISI3 2024-2025 Défis relevés en solution Solution Optimale Solution Multiples Si la somme des coûts du chemin est Un ou plusieurs chemin(s) d’opérateurs optimale (la plus petite) qui conduisent à l’état but à partir de SPar forcément le plus court chemin de l’état initial. en terme de nœuds … 2 Méthodes de recherche de solution Recherche de solution Augmentation de solution partielle Application récursive [Generale and test] [Divide and Solve] On commence la résolution en utilisant un On décompose le problème en sous opérateur valide pour l’état initial problèmes jusqu’à arriver à des sous problèmes « triviaux » On continue à le faire à partir de l’état résultant Onrésout ces problèmes par la méthode précédente Retour en arrière en cas des états terminaux ou des états déjà explorés On remonte l’arbre de décomposition jusqu’à obtenir la solution au problème Si plus aucun choix d’opérateur n’est complet possible alors il n’y a pas de solution 3 Augmentation de solution partielle Algorithmes de recherche par augmentation de solution partielle Méthode aveugles Méthodes basées sur les heuristiques [méthodes non informées] [méthodes informées] Recherche du meilleur avant Recherche en largeur (Best-first) Recherche en profondeur Méthode gourmande Recherche en profondeur Algorithme A* limitée Algorithme IDA* Recherche par approfondissement itératif Algorithme RBFS Recherche en cout uniforme Algorithme SMA* 4 Augmentation de solution partielle Méthode de recherche non-informée Présentation § La recherche non informée ne contient aucune connaissance du domaine telle que la proximité, l'emplacement de l'objectif. § La recherche non informée applique une stratégie sans aucune information sur: ‑ l'espace de recherche, ‑ les opérateurs d'état initial et ‑ le test de l'objectif Il s’agit d’une recherche aveugle. La recherche non-informée examine chaque nœud de l'arbre et elle génère les états successeurs des états déjà explorés jusqu'à ce qu’elle atteigne le nœud d’objectif 5 Augmentation de solution partielle Méthode de recherche non-informée Algorithme général 6 Augmentation de solution partielle Méthode de recherche non-informée Algorithmes dérivés La recherche non informée est Méthodes aveugles une classe d'algorithmes de (méthodes non-informées) recherche à usage général qui fonctionne de force brute. Recherche en largeur Les méthodes de recherche Recherche en profondeur diffèrent les unes des autres selon l’ordre dans lequel les Recherche en profondeur nœuds sont explorés limitée Recherche par approfondissement itératif Stratégies différentes Recherche en cout uniforme 7 Augmentation de solution partielle Méthode de recherche non-informée Exemple : Problème de navigation d’un robot Il s’agit de déterminer le meilleur chemin qui permet d’atteindre un lieu donné. Dans notre cas, le robot veut se rendre de A à H. 1. Représenter le graphe d’états de ce problème en étiquetant le passage d’un point à un autre par la distance entre ces deux points. Utiliser la distance euclidienne ( , ) = ( − )² + ( − )² + ( − )² 2. Appliquer la méthode de recherche en largeur pour atteindre le but H. 8 Augmentation de solution partielle Méthode de recherche non-informée Exemple : Problème de navigation d’un robot Utiliser la distance euclidienne pour calculer la distance entre les points dans l’espace de navigation du robot: A 1 2 ( , ) = ( − )² + ( − )² + ( − )² B D 1 2 Créer le graphe C 1 E d’états associé au 1 2 problème de F G navigation 2 H 9 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Stratégie L'algorithme de recherche en largeur commence la recherche à partir du nœud racine de l'arbre et développe tous les nœuds successeurs au niveau niveau actuel avant de passer aux nœuds du niveau suivant. Liste d’attente Recherche en largeur est implémentée à l'aide de la structure de données de la file d'attente FIFO (First In First Out) 10 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Algorithme général La liste d’attente est du type FIFO Utiliser une file pour gérer la liste d’attente. 11 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur 1 Niveau 0................................................................................................................................................. 2 3 Niveau 1................................................................................................................................................. 4 5 6 7 Niveau 2................................................................................................................................................. 8 9 10 Niveau 3................................................................................................................................................. Niveau 4 11 12 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Exemple : Problème de navigation d’un robot Stratégie : étendre le nœd le A Implémentation : insertion des successeurs à la fin de la file d’attente Nœud étendu Nœuds à étendre {A} B D A {B , D} B {D , C} D {C , E} C {E , FC} C E E {FC , FE , G} FC {FE , G} FE {G} G {H} FC FE G H  But Chemin : A D E G H H Graphe d’état Nœuds testés : 9 Nœuds étendus : 6 Arbre de résolution 13 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Evaluation Complexité en temps Dans le pire des cas, il explorera chaque état dans l’arbre de résolution. On note que: -s est le nombre de successeurs de chaque état (nombre des arcs). -e est le nombre des états La complexité en temps est alors Complexité en espace La complexitée espace est donnée par Ce nombre dépend des différentes structures de données implémentées pour déterminer quels états ont déjà été ajoutés à la file d'attente. 14 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Evaluation La complexité de la recherche en largeur en espace et en temps dépend de la profondeur de l’arbre ou du nombre des nœuds dans chaque niveau de profondeur. La recherche en largeur est efficace lorsqu’il s’agit d’attaquer des petits problèmes. 15 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Evaluation Complétude La recherche en largeur est complète. Ce qui signifie que si l’état but le moins profond se trouve à une profondeur finie, alors l’algorithme va le retrouver. Ceci n’est valide que lorsque le nombre des enfants (successeurs) de chaque état est fini. Optimalité La recherche en largeur ne garantit pas avoir la solution optimale. La recherche en largeur est optimale dans deux conditions: Si le coût du chemin est une fonction non décroissante de la profondeur de l’état. Si le coût du chemin est le nombre des état visités. 16 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en largeur Discussion Méthode gourmande L’algorithme garantie l’obtention En espace mémoire : il nécessite d’une solution (si elle existe). beaucoup de mémoire car chaque Arbre avec nombre de niveaude l'arborescence doit être branches fini enregistré en mémoire pour S'il existe plusieurs solutions développer le niveau suivant. pour un problème donné, En temps de calcul : il a besoin de l’algorithme fournira la solution beaucoup de temps si la solution minimale qui nécessite le moins est éloignée du nœud racine. d'étapes. Il n’est pas efficace aux problèmes avec plusieurs chemins longs menant à la solution AVANTAGES …... INCONVÉNIENTS 17 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Présentation Stratégie La recherche en profondeur part du nœud racine et suit chaque chemin jusqu'à son nœud de profondeur la plus élevé avant de passer au chemin suivant. Explorer l’arbre/graphe en allant vers les degrés de profondeur croissants En cas d’échec: On revient en arrière (nœud père) On recherche une autre branche à explorer Liste d’attente Recherche en profondeur est implémentée à l'aide de la structure de données de la pile (et non pas la file!) d’attente LIFO 18 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Algorithme général Cet algorithme peut se prêter à une implémentation récursive. 19 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Algorithme général 1 Niveau 0................................................................................................................................................. 2 8 Niveau 1................................................................................................................................................. 3 7 9 11 Niveau 2................................................................................................................................................. 4 6 10 Niveau 3................................................................................................................................................. Niveau 4 5 20 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Exemple : Problème de navigation d’un robot Stratégie : étendre le nœd le Implémentation : insertion des successeurs en tête de la file d’attente A Nœd étendu Nœds à étendre {A} B DA A {B , D} B {C , D} C C {F , D} F {E , DA} E {G ,DE , DA } F G {H ,DE , DA } H  But E Chemin : A B C E F G H G DE Graphe d’état Nœuds testés : 7 Nœuds étendus : 6 H 21 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Evaluation Complexité en temps La complexité temporelle de la recherche ne profondeur sera équivalente au nœud traversé par l'algorithme. Elle est donnée par : ( ) Avec s = le nombre des enfants de chaque état et m = profondeur maximale de n'importe quel nœud Complexité en espace L' algorithme la recherche ne profondeur n'a besoin de stocker qu'un seul chemin à partir du nœud racine. Par conséquent, la complexité spatiale de la recherche en profondeur équivant à la taille de l’ensemble des feuilles de l’arbre qui correspondent au but(s), qui est: ( × ) 22 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Evaluation Complétude L'algorithme de recherche en profondeur est complet dans un espace d'état fini, car il étendra chaque nœud dans un arbre de recherche limité. Ceci n’est valide que si l’espace d’état contient une solution. Sinon l’algorithme n’est pas complet parce qu'il peut continuer sur un chemin infini, ignorant l’état but qui se trouve sur un autre chemin. Optimalité L'algorithme de recherche en profondeur n'est pas optimal, car il peut générer un grand nombre d'étapes ou un coût élevé pour atteindre le nœud d'objectif. 23 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Discussion L’algorithme nécessite très moins Il est possible que de nombreux de mémoire car il n'a besoin que états continuent de se reproduire, de stocker une pile de nœuds sur et il n'y a aucune garantie de le chemin du nœud racine au nœud actuel. trouver la solution. Il faut moins de temps pour L'algorithme envisage la recherche atteindre le nœud cible que en profondeur et parfois il peut l'algorithme (s'il traverse le bon aller jusqu'à la boucle infinie. chemin). AVANTAGES …... INCONVÉNIENTS 24 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Discussion Stratégie : Explorer le graphe en allant vers les degrés de profondeur croissants. En cas d’échec: On revient en arrière (nœud père) On recherche une autre branche à explorer Peut conduire à des chemins infiniment longs sans succès (méthode non algorithmique) Solution : la recherche en profondeur limitée La recherche se fait jusqu’à une limite prédéfinie Lp Cas d’échec : on augmente Lp 25 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur limitée Présentation La recherche en profondeur limitée combine les avantages de la recherche en largeur et en profondeur: Optimal et complet comme la recherche en largeur Économe en espace comme la recherche en profondeur La recherche en profondeur limitée est similaire à la recherche en profondeur avec une limite prédéterminée. La recherche en profondeur limitée peut résoudre l'inconvénient du chemin infini dans la recherche en profondeur d'abord. La recherche en profondeur limitée peut être terminée avec deux conditions d'échec: Valeur d’échec standard : elle indique que le problème n'a pas de solution. Valeur de limite de coupure : elle ne définit aucune solution pour le problème dans une limite de profondeur donnée. 26  Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur limitée Algorithme général 1 Niveau 0................................................................................................................................................. Limite = 3 2 3 Niveau 1................................................................................................................................................. 4 5 6 7 Niveau 2................................................................................................................................................. 8 9 10 Niveau 3................................................................................................................................................. Niveau 4 11 27 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur limitée Exemple : Problème de navigation d’un robot Stratégie : étendrelenœudleplusprofondsisaprofondeurd’explorationLest inférieureàlalimite Implémentation : insertion des successeurs en tête de la file d’attente uniquement lorsqueL d 30 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Stratégie La recherche par approfondissement itératif essaye toutes les valeurs possiblesdeLàpartirdeL=1 File d’attente Recherche par approfondissement itératif est implémenté à l'aide de la structure de données de la pile (et non pas la file !) d’attente LIFO Insertion des successeurs en tête de la file d’attente si (L < Limite) avec L variant de 1 à l’infini 31 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Algorithme général 32  Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Algorithme général 1 Niveau 0................................................................................................................................................. Limite = 1 2 3 Niveau 1................................................................................................................................................. Niveau 2 Échec................................................................................................................................................. Niveau 3 Augmenter................................................................................................................................................. la limite Niveau 4 33  Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Algorithme général 1 Niveau 0................................................................................................................................................. Limite = 2 2 5 Niveau 1................................................................................................................................................. 3 4 6 7 Niveau 2 Échec................................................................................................................................................. Niveau 3 Augmenter................................................................................................................................................. la limite Niveau 4 34  Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Algorithme général 1 Niveau 0................................................................................................................................................. Limite = 1 2 7 Niveau 1................................................................................................................................................. 3 6 8 10 Niveau 2 Échec................................................................................................................................................. 4 5 9 Niveau 3 Augmenter................................................................................................................................................. la limite Niveau 4 35  Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Algorithme général 1 Niveau 0................................................................................................................................................. Limite = 4 2 3 Niveau 1................................................................................................................................................. 4 5 6 7 Niveau 2 Succès................................................................................................................................................. 8 9 10 Niveau 3................................................................................................................................................. Niveau 4 11 36 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Exemple : Problème de navigation d’un robot Stratégie : étendre le nœud le plus profond si sa profondeur d’exploration L est inférieure à la limite Implémentation : insertion des successeurs en tête de la file d’attente si L < Limite L=1 Nœud étendu Nœuds à étendre A {A} A {B , D} B {D} D {} B D Chemin : - Nœuds testés : 3 Nœuds étendus : 1 37 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Exemple : Problème de navigation d’un robot Stratégie : étendre le nœud le plus profonde si sa profondeur d’exploration L est inférieure à la limite sinon passe au suivant Implémentation : insertion des successeurs en tête de la file d’attente si L < Limite L=2 Nœud étendu Nœuds à étendre {A} A {B , D} A B {C , D} C {D} D {E} B D E {} Chemin : - C E Nœuds testés : 5 Nœuds étendus : 3 38 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Exemple : Problème de navigation d’un robot Stratégie : étendre le nœud le plus profonde si sa profondeur d’exploration L est inférieure à la limite sinon passe au suivant Implémentation : insertion des successeurs en tête de la file d’attente si L < Limite L=3 A Nœud étendu Nœuds à étendre {A} A {B , D} B D B {C , D} C {F , D} F {D} → tester D {E} C E E {G , FE} G {FE} FE {} Chemin : - FC G FE Nœuds testés : 8 Nœuds étendus : 5 39 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Exemple : Problème de navigation d’un robot Stratégie : étendre le nœud le plus profonde si sa profondeur d’exploration L est inférieure à la limite sinon passe au suivant Implémentation : insertion des successeurs en tête de la file d’attente si L < Limite 0 A L=4 Nœud étendu Nœuds à étendre B D 1 {A} A {B , D} B {C , D} C E 2 C {F , D} F {E , D} E {D} 3 FC G FE D {ED} ED {G , FE} G {H , FE} H EF H  But 40 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Évaluation Complexité en temps Supposons que: b soit le facteur de branchement d soit la profondeur alors la complexité temporelle dans le pire des cas est O(bd) Complexité en espace La complexité spatiale sera O(bd). Complétude Cet algorithme est complet si la limite tend vers une valeur finie. Optimalité L'algorithme est optimal si le coût du chemin est une fonction non décroissante de la profondeur du nœud. 41 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Discussion Cette méthode combine les avantages des algorithmes de recherche en profondeur et de Le principal inconvénient de cet recherche en largeur du point de algorithmeest qu'il répète tout le vue: travail de la limite (itération) { recherche rapide efficacité de la mémoire. précédente. au niveau d’une itération AVANTAGES …... INCONVÉNIENTS 42 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche approfondissement itératif Etats redendants Deux types de redondances possibles :  Des états qui peuvent être visites deux fois sur le même chemin Ex des N reines : on déplace une reine puis on la remet sur la même case Pour l’éviter : ne jamais ajouter a la liste de nœuds a traiter des nœuds dont les chemins contiennent plusieurs fois le même état Cette modification ne change pas significativement la complexité en espace des differents algorithmes  Plusieurs chemins différents peuvent amener au même état Pour l’éviter : il faut se rappeler de tous les états déjà visites et de ne garder qu’un seul chemin par état Il faut donc gérer une liste des états déjà visités et y ajouter les états quand ils sont visités pour la première fois Avant de générer un successeur, il faut vérifier qu’il n’est pas dans la liste Cette modification ne changera pas trop la complexité en espace pour le parcours en largeur, mais très significativement pour le parcours en profondeur 43 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme La recherche à coût uniforme est utilisée pour parcourir un arbre (ou un graphe) pondéré. Objectif L'objectif principal de la recherche à coût uniforme est de trouver un chemin vers le nœud d'objectif qui a le coût cumulé le plus bas. Stratégie Étendre le nœud de cout le plus faible Liste d’attente Cette recherche est mise en œuvre par la file d'attente prioritaire. Ordonnancement de la file d’attente dans l’ordre croissant des coûts de chemin 44 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme La recherche en coût uniforme développe les nœuds en fonction de leurs coûts de chemin à partir du nœud racine. Elle donne la priorité maximale au coût cumulé le plus bas. La recherche de coût uniforme est équivalente à l'algorithme de recherche en largeur si le coût de chemin de toutes les connexions est le même. 45 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme Algorithme général S Niveau 0 1 4................................................................................................................................................. A B Niveau 1 3 2 5................................................................................................................................................. C D G Niveau 2 5 3................................................................................................................................................. 4 E F G Niveau 3................................................................................................................................................. 5 Niveau 4 G 46 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme Algorithme général 47 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme Exemple : Problème de navigation d’un robot Stratégie : Étendrelenœuddecoutleplusfaible A Implémentation : insertiondes successeurs dans l’ordre croissant des coûts de chemin B D En cas d’égalité : appliquer le principe LIFO Nœud étendu Nœuds à étendre C ED {A : 0} A {B : 1 , D : 2 } F B {C : 2 , D : 2} C GD {D : 2 , F : 3} D {F : 3 , ED : 4} F EF {EF : 4 , ED : 4} EF {ED : 4 , GF : 6} ED {GD : 6 , GF : 6} GD {GF : 6 , HD : 8} GF GF {HF : 8 , HD : 8} HF  But HF 48 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme La recherche à coût uniforme est utilisée pour parcourir un arbre (ou un graphe) pondéré. Objectif L'objectif principal de la recherche à coût uniforme est de trouver un chemin vers le nœud d'objectif qui a le coût cumulé le plus bas. Stratégie Étendre le nœud de cout le plus faible Liste d’attente Cette recherche est mise en œuvre par la file d'attente prioritaire. Ordonnancement de la file d’attente dans l’ordre croissant des coûts de chemin 49 Augmentation de solution partielle Méthodes de recherche non-informée : Recherche en cout uniforme Evaluation Complexité en temps Soit C* le coût de la solution optimale, et ε est chaque étape pour se rapprocher du nœud cible. Alors le nombre d'étapes est = ⁄ε + 1. ∗ Ici, nous avons pris +1, car nous partons de l'état 0 et terminons à ⁄ε. ∗ Par conséquent, la complexité temporelle dans le pire des cas de la recherche à coût uniforme est ∗ ( +[ ⁄ ] ) Complexité en espace La même logique s'applique à la complexité spatiale, donc la complexité spatiale dans le pire des cas de la recherche à coût uniforme est: ∗ ( +[ ⁄ ] ) 50 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur Evaluation Complétude La recherche de coût uniforme est terminée, par exemple s'il existe une solution, elle la trouvera. Optimalité La recherche à coût uniforme est toujours optimale car elle ne sélectionne qu'un chemin avec le coût de chemin le plus bas. 51 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Discussion Il ne se soucie pas du nombre La recherche de coût uniforme d ' éta p e s i m p l i q u é e s d a n s l a est optimale car à chaque état le recherche et ne se préoccupe que chemin avec le moindre coût est du coût du chemin. choisi. Par conséquent, cet algorithme peut être bloqué dans une boucle infinie. AVANTAGES …... INCONVÉNIENTS 52 Augmentation de solution partielle Recherche bidirectionnelle Présentation L'algorithme de recherche bidirectionnelle exécute deux recherches simultanées:  ………………………………………………………………………………………………………  …………………………………………………………………………………………………………………… …………………………………………………………………………………………………………………….. La recherche bidirectionnelle remplace un seul graphe de recherche par deux petits sous-graphes dans lesquels l'un commence la recherche à partir d'un sommet initial et l'autre à partir du sommet d'arrivée. La recherche s'arrête lorsque ces deux graphiques se croisent. La recherche bidirectionnelle peut utiliser des techniques de recherche telles que recherche en largeur, en profondeur, approfondissement itératif, etc. 53 Augmentation de solution partielle Recherche bidirectionnelle Motivation Elle est applicable si on peut faire une recherche à partir du but et si la recherche unidirectionnelle est inefficace Elle satisfait un besoin d’une vérification efficace de l’existence d’un nœud commun aux deux arbres. Stratégie Effectuer une recherche par chaînage avant à partir de l’état initial et une recherche par chaînage arrière à partir de l’état final. Arrêter la recherche lorsque les deux processus se rencontrent Contraintes Les états buts doivent être explicitement définis Il faut que les opérateurs puissent être inversés 54 Augmentation de solution partielle Recherche bidirectionnelle Algorithme général État initial 1 2 3 4 Recherche en avant Niveau 0................................................................................................................................................. 5 6 Niveau 1................................................................................................................................................. 7 Niveau 2................................................................................................................................................. 8 État d’intersection Niveau 3................................................................................................................................................. Recherche en arrière 9 Niveau 4................................................................................................................................................. 10 11 Niveau 5................................................................................................................................................. Niveau 6 12 13 14 15 État but 55  Augmentation de solution partielle Recherche bidirectionnelle Exemple : Problème de navigation d’un robot Reprenons le problème de navigation du robot en ajoutant de nouveaux points. Il s’agit de déterminer le chemin qui permet au robot deserendre de A à H. Objectif: Appliquer la méthode de recherche bidirectionnelle pour atteindre le but H. 56 Augmentation de solution partielle Recherche bidirectionnelle Exemple : Problème de navigation d’un robot Transformer le problème sous la forme d’un graphe d’états 57 Augmentation de solution partielle Recherche bidirectionnelle Exemple : Problème de navigation d’un robot Utiliser : La stratégie en profondeur pour la recherche en avant La stratégie en largeur pour la recherche en arrière A 1 2 Couper le graphe B I d’états en deux 1 D 1 morceaux C 1 J 1 G 2 1 F 1 K 1 2 E 1 H I 58 Augmentation de solution partielle Recherche bidirectionnelle Exemple : Problème de navigation d’un robot La stratégie en profondeur pour la recherche en avant État initial : le nœud A État but: le nœud I A 1 2 Nœud étendu Nœuds à étendre B 1 {A} D A {B , D} C B {C , D} 1 C {F , D} 2 F {E , D} F E {I , D} 1 E I  But 1 I 59 Augmentation de solution partielle Recherche bidirectionnelle Exemple : Problème de navigation d’un robot La stratégie en largeur pour la recherche en avant État initial : le nœud H État but: le nœud I 1 I Nœud étendu Nœuds à étendre 1 J {H} 1 G H {G , K} G {K , I} K 2 1 K {I , J} H I  But 60 Augmentation de solution partielle Recherche bidirectionnelle Exemple : Problème de navigation d’un robot Chemin : A B C F E I G H 61 Augmentation de solution partielle Recherche bidirectionnelle Évaluation Complexité en temps La complexité temporelle de la recherche bidirectionnelle à l'aide de BFS est O(bd). Complexité en espace La complexité spatiale de la recherche bidirectionnelle est O(bd). Complétude La recherche bidirectionnelle est complète si nous utilisons BFS dans les deux recherches. Optimalité La recherche bidirectionnelle est optimale. 62 Augmentation de solution partielle Méthode de recherche non-informée : Recherche en profondeur itératif Discussion La mise en œuvre de l'arbre de La recherche bidirectionnelle est recherche bidirectionnel est rapide. difficile. La recherche bidirectionnelle Dans la recherche bidirectionnelle, nécessite moins de mémoire il faut connaître à l'avance l'état du but. AVANTAGES …... INCONVÉNIENTS 63 Exercice 1 Soit l’arbre de résolution suivant. Appliquez les algorithmes de recherche non-informée (en largeur, en profondeur, en profondeur limité «L=1», en coût uniforme) tout en comparant les chemins trouvés, leur coûts, le nombre des nœuds étendus et le nombre des nœuds testés. 64 65 66 67 68 69