Plus court chemin en présence d'information contextuelle

Répertoire GitHub correspondant à cet article : https://github.com/peportier/ia05-heuristics

Comment améliorer la recherche d'un plus court chemin entre un nœud source et un nœud cible quand nous possédons pour tout nœud du graphe une estimation de la distance séparant de la cible ?

La notion de fonction heuristique

Définitions

La fonction est appelée fonction heuristique.

Déf. Une heuristique est admissible si pour tout nœud , est une borne inférieure de la plus courte distance séparant de la cible , i.e. (avec désignant la longueur d'un chemin optimal entre et ).

Déf. Une heuristique est cohérente si pour toute arête nous avons (avec le poids de l'arête ).

Déf. Soient un chemin et le coût du chemin . Nous posons . Une heuristique est monotone si pour tout nous avons . C'est-à-dire que l'estimation du poids total d'un chemin ne décroît pas lors du passage d'un nœud à ses successeurs.

Équivalence entre cohérence et monotonie

Nous remarquons que cohérence et monotonicité sont deux propriétés équivalentes. En effet, pour deux nœuds adjacents et sur un chemin , nous avons :

ééûéé

L'autre implication (viz. monotonicité implique cohérence) vient de :

ééé

Cohérence implique admissibilité

Aussi, une heuristique cohérente est admissible (la réciproque n'est pas vraie). En effet, si est cohérente, pour toute arête nous avons . Soit un chemin quelconque , nous avons :

éé

En particulier, dans le cas d'un plus court chemin : .

Sur l'exemple ci-dessous, une heuristique est admissible si :

Elle est cohérente si :

L'heuristique proposée ci-dessous est donc admissible mais non cohérente.

13u (h.u = 3)v (h.v = 1)t (h.t = 0)

 

L'algorithme A*

L'algorithme A* est un exemple d'amélioration de l'algorithme de Dijkstra grâce à l'utilisation d'une fonction heuristique. A* associe à un nœud du graphe la valeur :

est le poids optimal actuellement connu pour un chemin menant de à , et est une heuristique admissible (i.e., une borne inférieure de la distance séparant de la cible ).

Nous remarquons que pour un nœud gris minimal (au sens de ), nous avons pour tout successeur de :

éàéé

Ainsi, l'algorithme A* correspond exactement à l'algorithme de Dijkstra avec la repondération suivante :

Si l'heuristique est monotone alors tous les poids restent positifs et la preuve de correction de Dijkstra s'applique !

De plus, nous allons montrer que, dans le cas d'une heuristique monotone, il n'existe pas d'algorithme qui trouve la solution optimale en explorant moins de nœuds que . Soit le coût de la solution optimale. Nous montrons que tout algorithme optimal (i.e., qui trouvera toujours la solution optimale) doit visiter tous les nœuds pour lesquels .

Travaillons par l'absurde en supposant qu'il existe un algorithme qui trouve une solution optimale (i.e., avec ) en ne visitant pas un nœud pour lequel . Montrons qu'il peut alors exister un autre chemin avec qui n'est pas trouvé par A. Soit le chemin tel que . Mettons qu'il existe une arête de poids (i.e., ). Puisque le voisinage de n'a pas été exploré par , ce dernier ne peut pas savoir que l'arête existe. Soit le chemin . Nous avons : .

Comparer des heuristiques

Plus une heuristique est proche de la valeur optimale plus elle est informée.

Plus une heuristique est informée, mieux elle minimise la taille de l'espace exploré, mais en général elle est également plus coûteuse en temps de calcul qu'une heuristique moins informée.

Le jeu du Taquin

Contexte

Prenons l'exemple simple du jeu de taquin de côté 8 (n-puzzle) dont on rappelle ci-dessous le voisinage.

eightpuzzle

Heuristiques

Voici quelques exemples d'heuristiques ordonnées par degré d'information :

Implémentation

Nous commençons par définir le type d'un nœud et d'une fonction heuristique.

 

Nous introduisons une fonction accessoire pour calculer la taille du côté d'une grille.

 

Puis nous définissons trois heuristiques.

 

La fonction final_state indique si la configuration finale est atteinte.

 

Nous utilisons une fonction pour retourner la plus petite distance actuellement connue pour rejoindre un nœud donné. Dans le cas d'un nœud pour lequel aucune estimation de distance n'a pour l'instant été proposée, cette fonction retourne l'infini.

 

Nous adaptons l'algorithme (i.e. Dijkstra...) pour le jeu du taquin.

Nous introduisons une fonction pour calculer le voisinage d'une position.

 

Le corps de l'algorithme devrait être sans surprises.

 

Nous introduisons une fonction pour afficher une grille.

 

Nous testons le programme sur une petite grille de côté 8.

 

Nous trouvons une solution optimale en 20 coups. En fonction de l'heuristique utilisée, le nombre de nœuds explorés change significativement.

heuristiquenb nœuds explorés
breadth44696
nbmis2877
manh189

Passage à l'échelle

Même avec l'heuristique manh, si nous testons notre programme sur des instances de taille 15 (i.e., des grilles de côté 4), nous observons qu'il ne trouve parfois pas de solution en un temps raisonnable.

 

L'algorithme A* en tant que variante de la recherche en largeur est gourmand en mémoire (toutes les configurations de coût inférieur à la solution optimale sont mémorisées).

Approfondissement itéré

Pour économiser la mémoire, la stratégie de l'approfondissement itéré propose de faire un parcours en profondeur jusqu'à une profondeur maximale . Si aucune solution n'est trouvée, une nouvelle recherche est lancée jusqu'à une profondeur maximale . Etc.

Soit le nombre de nœuds d'un espace d'états structuré en arbre enraciné de profondeur et de facteur de branchement (i.e., chaque nœud qui n'est pas une feuille possède fils).

Donc, à partir d'un facteur de branchement , il y a moins de nœuds dans la somme de tous les arbres excepté le dernier que de nœuds dans le dernier arbre. Ce raisonnement justifie l'utilisation de l'approfondissement itéré qui peut permettre une économie en mémoire sans que les visites multiples d'un même noeud aient un impact sur le nombre totale d'opérations lors de l'exécution de l'algorithme.

Approfondissement itéré pour A*

Le code source d'une implémentation de l'algorithme appliqué au problème du taquin est disponible à l'adresse suivante : https://github.com/peportier/ia06-idastar

Génération du voisinage en

Jusqu'à présent, nous stockons les voisins sous forme de configurations complètes. Générer un voisin pour une grille avec des côtés de taille nécessite opérations et demande d'allouer une nouvelle zone mémoire. En stockant le coup qui permet de transformer la configuration actuelle en une voisine, la génération de chaque voisin devient de complexité et il n'est plus nécessaire de réserver une nouvelle zone mémoire. Un code source utilisant cette stratégie est disponible à l'adresse suivante : https://github.com/peportier/ia07-idastar-delta-nei

-optimalité

Un algorithme de recherche est -optimal s'il termine en retournant une solution de coût au plus avec la configuration initiale, la configuration finale et une petite constante positive.

Nous montrons que l'algorithme avec une fonction de coût est -optimal pour une heuristique admissible. En effet, pour un nœud gris minimal, nous avons :

éœèàèà

Lorsque la cible est rencontrée, .