★ À maîtriser
📌 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 , où est l’état actuel, l’action et l’état résultant.
★ À maîtriser
📌 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 , son coût cumulé est .
★ À 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 ; dans l’analyse classique d’un arbre de recherche, son temps et sa mémoire sont de l’ordre de .
📌 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.
★ À maîtriser
📌 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.
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 et une mémoire pouvant atteindre selon la représentation.
Dans un arbre de recherche classique, DFS a une complexité en temps de et en mémoire de .
Dans un graphe fini parcouru avec mémorisation des sommets visités, DFS a une complexité temporelle de et utilise jusqu’à de mémoire selon la représentation.
📌 Dans un arbre de recherche, DFS consomme souvent moins de mémoire que BFS.
★ À 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.
File de priorité → coût minimal → retrait de l’objectif
★ À 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 compte les arêtes ; UCS additionne les coûts.
Comparaison de BFS, DFS et UCS
| Critère | BFS | DFS | UCS |
|---|---|---|---|
| Structure | File FIFO | Pile LIFO ou récursion | File de priorité |
| Choix | Plus ancienne entrée | Dernière entrée | Coût cumulé minimal |
| Optimalité | Oui si les coûts sont égaux | Non en général | Oui sous conditions sur les coûts |
| Usage typique | Nombre minimal d’étapes | Exploration en profondeur | Coût minimal |
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é ?
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.
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches