BDD IA Web services Architecture Info. Ubi.

M1

Petit résumé des algos

Recherche en largeur

• Complétude : Oui (si b (branchement) est fini)
• Complexité temporelle : O(b^d) (formule : ct = 1 + b + b × b + ··· + b^d)
• Complexité en espace : O(b^d)
• Optimalité : oui

Principe

• Étendre totalement le noeud sur 1 niveau
• Effectuer une recherche en largeur sur chacun des noeuds générés pris s équentiellement

Recherche en profondeur

• Complétude : oui (si espaces d'états finis et acycliques)
• Complexité temporelle : O(b^m)
• Complexité spatiale : O(b*m)
• Optimalité : non

Principe

• Placer un noeud dans une file d'attente
• Tant que la solution n'est pas trouvée de :
  • Retirer le noeud en tête de file
  • Déplacer ses fils et les placer en tête de la file (s'ils n'y sont pas déjà)

Recherche en profondeur limitée

• Complétude : Oui (si L ≥ d )
• Complexité temporelle : O(b^L)
• Complexité en espace : O(b*L)
• Optimalité : non

Principe

Recherche en profondeur avec une limite d'exploration L

Recherche par approfondissement itératif

• Complétude : Oui
• Complexité en temps : en O(b^d)
• Complexité en espace : en O(b×d)
• Optimalitée : oui (si L (augmentée ou non) = d)

Principe

• Recherche en profondeur limitée en incrémentant L dès que la profondeur L est atteinte
• Combine donc recherche en largeur et recherche en profondeur