On parle d'IA Symbolique car la connaissance est représentée par des symboles significatifs de niveau supérieur + le raisonnement repose sur la manipulation de ces symboles. Le monde est donc décrit par des symboles, et la connaissance du monde par des relations, des règles et des contraintes s'appliquant à ces symboles.

Le graphe possède un ensemble de noeuds (nodes) reliés par des arêtes (edges) orientées. L'ensemble des nodes que l'on peut atteindre en suivant les arêtes d'un node est appelé "successeurs de n".

Reformuler un problème de recherche :

• Ensemble d'états (nodes) = ensemble de toutes les situations possibles dans le monde considéré
• Transitions entre états (edges, arêtes) = chemins permettant de passer d'un état à l'autre
• Etat initial = le noeud à partir duquel on commence
• Etat souhaité (objectif) = noeud du graphe où l'on souhaite se trouver

Résoudre le problème = trouver un chemin dans le graphe allant de l'état initial à l'état final. On privilégie généralement les chemins les plus courts (solutions plus efficaces).

Un algorithme de parcours de graphe (graph traversal algorithm) trouve un chemin dans un graphe d'un noeud à l'autre.

Breadth First Search (BFS) - Idée générale : essayer chaque successeur du noeud initial, les successeurs de ces successeurs, ... jusqu'à atteindre l'état souhaité.

Caractéristiques d'un BFS : complet (si une solution existe, il l'a trouvera) ; optimal (chemin le plus court) ; peut être gourmand en temps de calcul et en mémoire si la solution est complexe (long chemin) ; améliorable en le rendant bidirectionnel (de l'état initial vers l'état final - et état final vers état initial simultanément).

Depth First Search (DFS) - Idée général : suivre une branche du graphe jusqu'à son extrémité et revenir en arrière si l'état final n'est pas atteint. Il utilise une pile au lieu d'une file d'attente, et peut être implémenté facilement de manière récursive).

Caractéristiques d'un DFS : complet, mais pas optimal, peut consommer moins de mémoire que BFS, peut suivre une branche pendant très longtemps même si l'état final est proche de l'initial.

> Variante avec limite de profondeur : si atteinte, l'algo cesse de suivre la branche et revient en arrière.

A* : un algorithme de recherche informé = il utilise des informations sur une estimation du chemin restant à suivre et choisit le successeur susceptible de conduire plus rapidement vers l'état final => au lieu d'explorer toutes les possibilités, il choisit sa direction basée sur une idée générale qui rapprochera de l'objectif. Cette "idée générale" (= estimation du chemin restant à parcourir pour atteindre l'objectif) = une fonction heuristique fournie, conçue pour être précise et facile à calculer pour tout noeud / état.

Liste des prochains état à visiter à chaque étape : f(n) = g(n) + h(n), où g(n) = la longueur du chemin pour atteindre l'état n ; h(n) = résultat de la fonction heuristique pour n.

Le choix de la fonction heuristique s'appuie généralement sur une intuition basée sur une abstraction du problème.

Caractéristiques de A* : complet ; optimal sous la condition que l'heuristique soit admissible (= qu'elle ne surestime jamais la longueur réelle du chemin restant vers l'état final ; si la fonction heuristique est bien choisie, A* trouvera un chemin plus que rapidement que BFS et souvent que DFS. A* avec h(n) = 1 = BFS.