Résoudre des Problèmes avec l'IA — Algorithmes, A* et Espaces d'États

1. Formulation d'un problème

Avant de résoudre un problème, il faut le formaliser rigoureusement. Un problème de recherche est défini par cinq composants.

Problème = (S₀, Actions, Transition, Test_But, Coût)

S₀         : état initial
Actions(s) : ensemble des actions disponibles dans l'état s
Transition(s, a) : état résultant de l'action a dans l'état s
Test_But(s) : vrai si s est un état but
Coût(s, a, s') : coût de la transition de s vers s' via a

Une solution est une séquence d'actions conduisant de l'état initial à un état but. Une solution optimale minimise le coût total du chemin.

Abstraction

La formulation implique de choisir le niveau d'abstraction approprié. Un état trop détaillé (position exacte de chaque atome) rend le problème intraitable. Un état trop abstrait peut perdre des informations cruciales. L'art est de trouver le bon niveau de représentation.

2. Espace d'états et graphe

L'espace d'états est l'ensemble de tous les états accessibles depuis l'état initial. Il est représenté comme un graphe orienté où :

• Les nœuds représentent les états
• Les arcs représentent les actions
• Les poids des arcs représentent les coûts

Taille de l'espace d'états :
- Taquin 8  : 9!/2 = 181 440 états
- Taquin 15 : 16!/2 ≈ 10¹³ états
- Échecs    : ≈ 10⁴⁷ états légaux
- Go        : ≈ 10¹⁷⁰ états possibles

Un nœud de recherche n'est pas un état : c'est une structure de données contenant un état, son parent, l'action qui y a mené, le coût du chemin et la profondeur. L'arbre de recherche est construit dynamiquement lors de l'exploration.

3. Recherche non informée (aveugle)

Les algorithmes non informés n'utilisent aucune information sur la distance au but. Ils explorent l'espace d'états de façon systématique.

BFS — Largeur d'abord (Breadth-First Search)

Explore tous les nœuds de profondeur d avant d+1. Utilise une file FIFO. Garantit de trouver la solution de profondeur minimale.

BFS(problème):
  frontière ← file([état_initial])
  explorés  ← {}
  tant que frontière non vide:
    nœud ← frontière.dépiler()
    si test_but(nœud.état): retourner solution(nœud)
    explorés.ajouter(nœud.état)
    pour chaque action dans actions(nœud.état):
      enfant ← expand(nœud, action)
      si enfant.état ∉ explorés ∪ frontière:
        frontière.enfiler(enfant)

DFS — Profondeur d'abord (Depth-First Search)

Explore le chemin le plus profond avant de revenir en arrière. Utilise une pile LIFO ou la récursion. Très économe en mémoire : O(bm) où b est le facteur de branchement et m la profondeur maximale.

DLS — Recherche en profondeur limitée

DFS avec une limite de profondeur L. Évite les branches infinies. Problème : si la solution est plus profonde que L, elle n'est pas trouvée.

IDDFS — Approfondissement itératif

Combine les avantages de BFS (optimalité) et DFS (efficacité mémoire). Exécute DLS avec L = 0, 1, 2, ... jusqu'à trouver une solution. Complexité temporelle : O(b^d), spatial : O(bd).

UCS — Recherche au moindre coût (Uniform-Cost Search)

Généralise BFS aux coûts non uniformes. Utilise une file de priorité sur le coût du chemin g(n). Garantit l'optimalité si les coûts sont positifs. Équivalent à l'algorithme de Dijkstra.

4. Recherche informée et heuristiques

Les algorithmes informés utilisent une heuristique h(n) estimant le coût du chemin le plus court de n jusqu'au but.

Greedy Best-First Search

Choisit le nœud qui semble le plus proche du but selon h(n). Rapide mais non optimal et incomplet (peut boucler).

// Greedy utilise f(n) = h(n) uniquement
f(n) = h(n)  // estimation coût restant jusqu'au but

Algorithme A*

L'algorithme A* est le plus utilisé en IA pour la recherche informée. Il combine le coût réel g(n) et l'heuristique h(n).

f(n) = g(n) + h(n)

g(n) : coût réel du chemin depuis l'état initial jusqu'à n
h(n) : estimation du coût de n jusqu'au but
f(n) : estimation du coût total du meilleur chemin passant par n

Heuristiques pour le taquin

• h1 = nombre de pièces mal placées : admissible car chaque pièce nécessite au moins 1 mouvement.
• h2 = distance de Manhattan : somme des distances (horizontale + verticale) de chaque pièce à sa position cible. Plus précise que h1. Si h2 ≥ h1 pour tout état, on dit que h2 domine h1.

// Exemple distance Manhattan pour taquin 8
État:    [7,2,4]    Cible: [1,2,3]
         [5,0,6]           [4,5,6]
         [8,3,1]           [7,8,0]

h2 = |pos_act(1) - pos_cible(1)|₁ + ... = 18

5. Propriétés des algorithmes de recherche

On évalue un algorithme selon quatre critères fondamentaux.

┌─────────┬──────────┬──────────┬──────────┬──────────┐
│ Algo    │Complétude│Optimalité│ Temps    │ Espace   │
├─────────┼──────────┼──────────┼──────────┼──────────┤
│ BFS     │ Oui*     │ Oui*     │ O(b^d)   │ O(b^d)   │
│ DFS     │ Non      │ Non      │ O(b^m)   │ O(bm)    │
│ DLS     │ Non      │ Non      │ O(b^l)   │ O(bl)    │
│ IDDFS   │ Oui*     │ Oui*     │ O(b^d)   │ O(bd)    │
│ UCS     │ Oui*     │ Oui*     │ O(b^C/ε) │ O(b^C/ε) │
│ Greedy  │ Non      │ Non      │ O(b^m)   │ O(b^m)   │
│ A*      │ Oui*     │ Oui**    │ O(b^d)   │ O(b^d)   │
└─────────┴──────────┴──────────┴──────────┴──────────┘
* Si graphe fini ou solution à profondeur finie
** Si heuristique admissible

6. Problèmes de Satisfaction de Contraintes (CSP)

Un CSP est défini par un triplet (X, D, C) :

• X = {X₁, ..., Xₙ} : ensemble de variables
• D = {D₁, ..., Dₙ} : domaines de chaque variable
• C = {C₁, ..., Cₘ} : contraintes entre variables

Une solution est une affectation de valeurs à toutes les variables qui satisfait toutes les contraintes.

Algorithmes CSP

Backtracking : algorithme de base qui affecte des valeurs une par une et revient en arrière en cas d'inconsistance. Arc-consistency (AC-3) : prétraitement qui élimine les valeurs inconsistantes des domaines. Forward checking : propagation des contraintes après chaque affectation.

// Backtracking pour CSP
function Backtrack(affectation, csp):
  si affectation complète: retourner affectation
  var ← ChoixVariable(csp, affectation)
  pour valeur dans OrdreValeurs(var, affectation, csp):
    si consistent(valeur, affectation, csp):
      affectation.ajouter(var = valeur)
      résultat ← Backtrack(affectation, csp)
      si résultat ≠ échec: retourner résultat
      affectation.supprimer(var = valeur)
  retourner échec

Heuristiques CSP

• MRV (Minimum Remaining Values) : choisir la variable au domaine le plus réduit
• Degree heuristic : choisir la variable impliquée dans le plus de contraintes
• LCV (Least Constraining Value) : choisir la valeur qui réduit le moins les domaines voisins

7. Exemples classiques

Problème des 8-Reines

Placer 8 reines sur un échiquier 8×8 sans qu'aucune ne puisse en attaquer une autre (pas de même ligne, colonne ou diagonale).

Variables  : Xᵢ = colonne de la reine sur la ligne i, i=1..8
Domaines   : Dᵢ = {1,2,3,4,5,6,7,8}
Contraintes: Xᵢ ≠ Xⱼ (colonnes différentes)
             |Xᵢ - Xⱼ| ≠ |i - j| (diagonales différentes)

Nombre de solutions : 92 (dont 12 fondamentales)

Taquin 8

Déplacer les tuiles numérotées 1-8 sur une grille 3×3 pour atteindre la configuration cible. Espace de recherche de 181 440 états. A* avec distance Manhattan résout les instances difficiles en moins de 5 ms.

Labyrinthe

Trouver un chemin d'une entrée à une sortie dans un labyrinthe. BFS trouve le chemin le plus court (en nombre de cases). A* avec heuristique distance euclidienne trouve souvent la solution plus rapidement.

FAQ — Questions fréquentes