Best first search (8puzzle)

Heuristique :

Recherche du meilleur d’abord
(Best First)

1. Introduction :

• Les algorithmes de recherche heuristique  utilisent l'information disponible pour rendre le processus de recherche plus efficace.
• une information heuristique est une règle ou une méthode qui permet d’évaluer la probabilité qu’un chemin allant du nœud courant au nœud solution soit meilleur que les autres.

1. Principe de la Recherche du Meilleur d’abord :

• Explorer du nœud avec le meilleur score d’abord. Une fonction d’ évaluation est utilisée pour attribuer une note à chaque nœud candidat.
• Conserver deux listes, l’une contenant une liste de candidats à explorer ( OPEN) , et l’autre contenant une liste de nœuds déjà visités( CLOSED) à ne pas explorer à nouveau.
• Explorer le meilleur chemin en étendant à chaque fois le nœud qui a la meilleure valeur h(s) mais garde les autres chemins en attente.

• Revenir sur les autres chemins si à un moment donné, le chemin choisi devient moins intéressant que les autres chemins.
• Combinaison entre la recherche en profondeur et en largeur .

1. Algorithme de la Recherche du Meilleur d’abord :

• État initial = la planche initiale
• État final = la planche finale (solution)
• La Recherche :

• Commence avec l’état initial = état courant (x)
• Pour l’état courant :

• générer tous les mouvements possibles
• compter les carreaux mal assortis (fonction m(x))
• Calculer la fonction heuristique f(x) = m(x)
• Sélecter le prochain état e avec la valeur minimale de f(x)
• État courant = prochain état  
• Répéter jusqu‘à la solution finale

1. Application (Jeu de 8-puzzles ):

• Principe :   Réaliser une configuration donnée de tuiles d’une manière optimale qui minimise le nombre de déplacements à partir d'une configuration donnée (initiale) en faisant glisser les tuiles individuellement . Ceci en tenant compte de la fonction heuristique  f(x) = m(x)

→ choisir à chaque étape le cas où f(x) est minimale.

1. Références :

• Document : Algorithmes de recherche heuristique (Cours : A. Belaïd Université de Nancy 2)
• Document : Le Jeu et l’intelligence artificielle  (Oana Frunza , University of Ottawa, 7 mai, 2012)
• https://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Best-first_search
• https://www.cs.utexas.edu/users/novak/asg-8p.html
• http://www.aiai.ed.ac.uk/~gwickler/eightpuzzle-inf.html

...