Recherche Heuristiquement Ordonnee Dans Les Graphes D'Etats. Algorithmes Et Proprietes

Un paradigme de résolution de problème, relativement ancien, consiste à explorer l'espace des énoncés alternatifs qui peuvent être dérivés d'un énoncé originel lorsqu'il est soumis à un ensemble d'opérateurs de transformation, jusqu'à atteindre une formulation-but. Il est alors convenu de considérer que le problème est résolu. Les transitions entre énoncés alternatifs sont représentées au moyen d'un graphe d'états. Chercher une solution consiste à révéler un chemin entre le sommet du graphe d'états représentant l'énoncé originel et un sommet représentant une formulation-but. Ordinairement, les arcs du graphe d'états sont valués et l'on souhaite découvrir des chemins-solutions de longueur réduite. A cette fin, les techniques de recherche heuristiquement ordonnée proposent une panoplie d'algorithmes qui exploitent des fonctions d'évaluation. L'un des plus populaires est sans doute l'algorithme dénommé A*. Des algorithmes de recherche heuristiquement ordonnée ont été employés pour résoudre des problèmes de recherche opérationnelle pour contribuer au guidage de démonstrateurs automatiques de théorèmes, pour traiter des problèmes de navigation en robotique, pour assistance en génération automatique de langage naturel, en correction d'orthographe ou en diagnostic de pannes. Dans les publications qui traitent de recherche heuristique, la terminologie et les procédés de description varient sensiblement, au point qu'il est difficile d'appréhender les rapports entre algorithmes; l'exposé des propriétés et leurs justifications sont parfois lacunaires, voire entachés d'erreurs. Ce livre répond de manière approfondie et rigoureuse aux questions suivantes : avec quels graphes d'états, quelles fonctions d'évaluation, quels algorithmes peut-on assurer l'arrêt, la découverte d'une solution, son optimalité ou sous-optimalité, ou limiter la complexité de calcul ? Il présente un panorama étendu, structuré et unifié des principaux algorithmes disponibles, prouve et compare méticuleusement leurs propriétés propose de nombreuses extensions et innovations (longueur généralisée, famille élargie de graphes d'états, termes heuristiques évolutifs, diverses variantes d'algorithmes monodirectionnels ou bidirectionnels). Exposé cohérent et progressif des connaissances en RHO, cet ouvrage intéressera les étudiants de DEA et DESS en intelligence artificielle et recherche opérationnelle. Il fournit également à l'élève-ingénieur et l'ingénieur une typologie d'algorithmes précisément qualifiés et spécifiés. Enfin, le chercheur en IA y trouvera une synthèse des travaux disponibles sur le sujet avec des résultats nouveaux et inédits ainsi que des indications pour des voies d'investigation futures.