Fiche de révision : Recherche non informée en IA

Plan du Cours

  1. Fondements de la recherche en IA
  2. Frontière et critères de recherche
  3. Recherche en largeur BFS
  4. Recherche en profondeur DFS
  5. Recherche à coût uniforme
  6. Comparaison et applications

1. Fondements de la recherche en IA

Notions clés & Définitions

  • Recherche en IA : Explore des états et des actions possibles afin de trouver une solution à un problème.
  • État : La représentation de la situation pertinente du problème à un instant donné.
  • Action : Une opération disponible qui permet de passer d’un état à un autre.

★ À maîtriser

  • Un problème de recherche classique comprend :
    • un état initial
    • des actions
    • un modèle de transition
    • un test d’objectif
    • un coût du chemin

📌 Le graphe d’états représente les états et transitions possibles, tandis que l’arbre de recherche représente les chemins explorés et peut contenir plusieurs occurrences d’un même état.

Compléments

📐 Formule - La transition s’écrit s′=T(s,a)s' = T(s,a), où ss est l’état actuel, aa l’action et s′s' l’état résultant.

2. Frontière et critères de recherche

Notions clés & Définitions

  • Frontière : Contient les nœuds découverts mais pas encore développés.
  • Profondeur : Le nombre d’arêtes séparant un nœud de la racine dans l’arbre de recherche.

★ À maîtriser

  • La structure utilisée pour la frontière détermine la stratégie : une file FIFO pour BFS, une pile LIFO pour DFS et une file de priorité pour UCS.

📌 Un algorithme est complet s’il garantit de trouver une solution lorsqu’elle existe sous les hypothèses requises, et optimal s’il garantit une solution de coût minimal.

Compléments

📐 Formule - Si les actions d’un chemin ont les coûts c1,c2,…,ckc_1,c_2,\ldots,c_k, son coût cumulé est g(n)=∑i=1kcig(n)=\sum_{i=1}^{k}c_i.

  • L’analyse d’un algorithme de recherche porte notamment sur le facteur de branchement maximal b, la profondeur de la solution la moins profonde d, la profondeur maximale m, le coût optimal C* et le coût minimal strictement positif ε d’une action lorsqu’il existe.

3. Recherche en largeur BFS

Notions clés & Définitions

  • Recherche en largeur : Explore les nœuds niveau par niveau, en ordre de profondeur croissante.

★ À maîtriser

📌 Dans un graphe non pondéré, BFS trouve un chemin avec un nombre minimal d’arêtes si la recherche est correctement implémentée.

📌 BFS est complète sous des hypothèses usuelles, notamment un facteur de branchement fini, et optimale si chaque action a le même coût.

Compléments

  • BFS utilise une file FIFO, où le premier nœud ajouté est le premier retiré.

  • Dans un graphe fini représenté par des listes d’adjacence, BFS s’exécute en temps O(V+E)O(V+E); dans l’analyse classique d’un arbre de recherche, son temps et sa mémoire sont de l’ordre de O(bd+1)O(b^{d+1}).

📌 Un parcours BFS qui retourne l’ordre de visite ne fournit pas nécessairement le chemin vers l’objectif; il faut mémoriser les parents ou prédécesseurs pour reconstruire ce chemin.

4. Recherche en profondeur DFS

Notions clés & Définitions

  • Recherche en profondeur : Choisit un successeur, poursuit aussi profondément que possible, puis revient en arrière pour explorer les branches restantes.

★ À maîtriser

  • DFS utilise une pile LIFO ou un mécanisme récursif et privilégie la profondeur plutôt que l’exploration de tous les nœuds d’un même niveau.

📌 DFS termine dans un graphe fini avec gestion des sommets visités, mais sa complétude n’est pas garantie dans un espace infini sans précautions.

  • DFS n’est généralement pas optimal et peut explorer longtemps une branche peu prometteuse.

Compléments

📌 DFS peut trouver rapidement une solution située profondément dans la première branche explorée, mais cette solution n’est pas nécessairement la plus courte.

  • Dans un graphe fini parcouru avec mémorisation des sommets visités, DFS a une complexité temporelle de O(V+E)O(V+E) et une mémoire pouvant atteindre O(V)O(V) selon la représentation.

  • Dans un arbre de recherche classique, DFS a une complexité en temps de O(bm)O(b^m) et en mémoire de O(bm)O(bm).

  • Dans un graphe fini parcouru avec mémorisation des sommets visités, DFS a une complexité temporelle de O(V+E)O(V + E) et utilise jusqu’à O(V)O(V) de mémoire selon la représentation.

📌 Dans un arbre de recherche, DFS consomme souvent moins de mémoire que BFS.

5. Recherche à coût uniforme

Notions clés & Définitions

  • Recherche à coût uniforme : La recherche à coût uniforme (UCS, Uniform-Cost Search) conserve les nœuds dans une file de priorité et développe celui dont le coût cumulé depuis le départ est minimal, jusqu’à retirer l’objectif de la file.
  • Coût cumulé : Le coût cumulé g(n)g(n) est le coût du chemin allant du nœud de départ au nœud nn.

★ À maîtriser

📌 Avec des coûts d’action non négatifs, UCS trouve un chemin optimal si l’algorithme est correctement implémenté et que les conditions de terminaison sont satisfaites.

📌 Dans UCS, le test d’objectif s’effectue au retrait du nœud de la file, car un nœud découvert par un chemin coûteux peut ensuite être atteint par un chemin moins coûteux.

Compléments

  • UCS ignore une entrée obsolète de la file lorsque son coût ne correspond plus au meilleur coût connu pour le sommet.

  • UCS reconstruit le chemin en remontant les parents depuis l’objectif, puis en inversant l’ordre obtenu.

📌 UCS est complet sous les hypothèses classiques, notamment si le facteur de branchement est fini et si les coûts d’action sont bornés inférieurement par une constante strictement positive.

  • La mémoire utilisée par UCS peut être importante, car plusieurs chemins candidats sont conservés.

  • Dans un graphe où A→B coûte 2, A→C coûte 5, B→D coûte 4 et C→D coûte 1, les chemins A→B→D et A→C→D coûtent chacun 6, si bien que UCS garantit un coût minimal sans garantir un chemin unique.

Astuce mémo

File de priorité → coût minimal → retrait de l’objectif

6. Comparaison et applications

★ À maîtriser

📌 BFS minimise le nombre d’arêtes lorsque les coûts sont uniformes, tandis que UCS minimise le coût cumulé lorsque les coûts diffèrent.

Compléments

  • BFS utilise une file FIFO, DFS une pile LIFO ou la récursion, et UCS une file de priorité qui sélectionne le coût cumulé minimal.

  • BFS est complet sous les conditions usuelles, DFS ne l’est pas dans tous les espaces, et UCS est complet sous des conditions portant sur les coûts.

  • BFS est optimal lorsque les coûts sont égaux, DFS ne l’est pas en général et UCS l’est sous les conditions usuelles sur les coûts.

  • Les usages typiques des algorithmes sont :

    • BFS : trouver le nombre minimal de sauts dans un réseau non pondéré
    • DFS : explorer des dossiers ou des branches
    • UCS : rechercher un itinéraire minimal lorsque les coûts des liaisons diffèrent

Astuce mémo

BFS compte les arêtes ; UCS additionne les coûts.

Tableaux de synthèse

Comparaison de BFS, DFS et UCS

CritèreBFSDFSUCS
StructureFile FIFOPile LIFO ou récursionFile de priorité
ChoixPlus ancienne entréeDernière entréeCoût cumulé minimal
OptimalitéOui si les coûts sont égauxNon en généralOui sous conditions sur les coûts
Usage typiqueNombre minimal d’étapesExploration en profondeurCoût minimal

Teste tes connaissances

Teste tes connaissances sur Recherche non informée en IA avec 10 questions à choix multiples et corrections détaillées.

1. Un robot doit résoudre un labyrinthe sans connaître à l’avance l’itinéraire gagnant. Que fait-il dans le cadre d’une recherche en IA ?

2. Dans un problème, deux chemins différents conduisent au même état. Quelle représentation peut montrer cet état plusieurs fois, une fois pour chaque chemin exploré ?

Faire le QCM →

Révisez avec les flashcards

Mémorisez les concepts clés de Recherche non informée en IA avec 10 flashcards interactives.

Que cherche à trouver la recherche en IA en explorant des états et des actions possibles ?

Une solution à un problème.

Quels éléments comprend un problème de recherche classique ?

Un état initial, des actions, un modèle de transition, un test d’objectif et un coût du chemin.

Que contient la frontière dans un algorithme de recherche ?

Les nœuds découverts mais pas encore développés.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.

Générateur de fiches