Print bookPrint book

Méthodes de résolution de problèmes

Site: Campus Numérique UABT
Course: Intelligence Artificielle
Book: Méthodes de résolution de problèmes
Printed by: Visiteur anonyme
Date: Sunday, 19 May 2024, 6:54 PM

Table of contents

1. Définition problème

Un problème est une collection d’informations que l’agent utilise pour décider quelles actions accomplir. 
Définir un problème c’est:
  • Identifier un état initial (donc choix d’un langage de description d’états du problème)
  • Identifier les actions possibles par définition d’opérateurs de changement d’état (donc définition de l’ensemble des états possibles du problème)
Nature du problème:

  • Problèmes de jeux : concis et bien défini comme le jeu du taquin, des n reines, leur modélisation est facile et il sont intéressant pour comparer les différentes stratégies de résolution.


  • Problèmes du monde réel : complexes et très ouverts comme le calcul de routes, le voyageur de commerce, la navigation de robots. Il sont difficiles à résoudre dans le cas général (trop de paramètres) d’où l’importance de la modélisation.

2. Espace de recherche

Un espace de recherche est un ensemble des états atteignables depuis l’état initial par n’importe quelle séquence d’actions.

Il peut être représenté par un graphe orienté. Les sommets sont les états, les arcs sont les actions.

Donc, pour résoudre un problème il faut:
  • Formulation d’un but: un état à atteindre.
  • Formulation d’un problème: les états et les actions à considérer.
  • Exploration de solutions: examiner les différentes séquences d’actions menant à un état but et choisir la meilleure.
Exemple1:


Exemple 2:

3. Résolution de problèmes

  • On part du principe que tous les problèmes étudiés sont composés d’un ensemble de situations que l’on peut décrire à l’aide d’un ensemble de variables appelés variables d’états.
  • L’état d’un problème est alors l’ensemble des valeurs prises par les variables à un instant donné. L’espace d’état d’un problème est l’ensemble de tous ses états possibles.
  • Chaque état possède un ensemble d’états qui lui sont accessibles  dans le problème. Les opérateurs permettent de définir cet ensemble, et c’est la stratégie de résolution qui donnera la façon de choisir parmi ces états accessibles celle menant à une solution.
  • Un problème est défini pour un objectif particulier. On doit donc également définir une fonction de test de but atteint qui détermine si un état du problème correspond à un état but du problème.
  • Une solution est une séquence d’actions permettant de passer de l’état initial vers un état but.
  • On peut considérer que la résolution d’un problème est la découverte d’un état du problème ayant des caractéristiques données (la solution).
Le processus de résolution de problème consiste donc à construire un arbre de recherche où chaque nœud de l’arbre correspond soit à l’état initial du problème, soit à un développement du sommet parent par un des opérateurs du problème.

Généralement, on représente un problème par un espace d'états (arbre/graphe) où chaque état est une configuration possible du problème. Et donc résoudre le problème consiste à trouve un chemin dans le graphe.

Arbre de recherche:

  • La racine de l’arbre correspond à l’état initial du problème.
  • Les feuilles de l’arbre correspondent à des états sans successeur dans l’arbre ou des nœuds qui n’ont pas encore été développés.
  • Un chemin est une séquence de sommets partant du sommet à une feuille.
  • Le coût d’un chemin est défini par la somme des coûts de chaque opérateur intervenant dans la construction du chemin.

3.1. Stratégies aveugles

Dans l'exploration non informée (aveugle):
  • Pas d'information sur les états
  • Générer des successeurs et distinguer état final / non final
Il y a plusieurs algorithmes tels que:

  • En largeur d'abord
  • À coût uniforme
  • En profondeur d'abord
  • En profondeur limitée
  • En profondeur itérative
Recherche en profondeur
  • Chaque sommet choisi pour être exploré voit tous ses successeurs générés avant qu’un autre sommet ne soit exploré.
  • Une recherche en profondeur peut se révéler dangereuse : l’algorithme risque de développer une branche infinie stérile sans que le mécanisme de retour en arrière puisse se déclencher.
  • On ajoute dans ce cas une limite de profondeur.

Recherche en largeur:
Cette stratégie donne une plus grande priorité aux sommets les moins profonds du graphe de recherche en explorant les sommets de même profondeur.



3.2. Stratégies heuristiques

  • Les stratégies informées ou heuristiques utilisent un ensemble de règles qui permettent d’évaluer la probabilité qu’un chemin allant du nœud courant au nœud solution soit meilleur que les autres.
  • Cette information permet l’estimation des bénéfices des divers chemins avant de les parcourir améliore le processus de recherche.
  • Les algorithmes de recherche heuristique utilisent des fonctions appelées fonctions heuristiques.  h : E –>R

Heuristique:

  • Une heuristique est une mesure associée à un état donné qu’on notera h(Ei).
  • Une heuristique est un critère ou une méthode permettant de déterminer parmi plusieurs lignes de conduite celle qui promet d’être la plus efficace pour atteindre un but.
  • Elle fournit rapidement une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation difficile.
  • Une heuristique s'impose quand les algorithmes de résolution exacte sont de complexité exponentielle.
Les heuristiques peuvent être classées en deux catégories :
    • Méthodes constructives qui génèrent des solutions à partir d’une solution initiale en essayant d’en ajouter petit à petit des éléments jusqu’à ce qu’une solution complète soit obtenue.
    • Méthodes de fouilles locales qui démarrent avec une solution initialement complète (probablement moins intéressante), et de manière répétitive essaie d’améliorer cette solution en explorant son voisinage.

En effet, dans certains cas, le prix à payer pour utiliser des méthodes de programmation mathématique peut être une très grande complexité mathématique qui se traduit par des temps de calculs souvent longs. Parce qu’en pratique, une solution à un problème décisionnel doit être proposée dans des temps raisonnables, on sacrifie en partie la qualité de la solution au sens purement mathématique pour accélérer le processus de résolution.

On cite quelques algorithmes informés:
  • Meilleur d'abord
  • Algorithmes gloutons
  • Algorithme A∗
  • Coût uniforme
  • Méta-heuristiques

3.3. Algorithme glouton (greedy algorithm)

  • Un algorithme glouton fait, étape par étape, le choix d’un optimum local.
  • A chaque itération, on fixe la valeur d'une des variables décrivant le problème sans remettre en cause les choix antérieurs.
  • Le principe est donc de partir d'une solution incomplète que l'on complète de proche en proche en effectuant des choix définitifs : à chaque étape, on traite une partie des variables sur lesquelles on ne revient plus.
  • Conception facile à mettre en œuvre.
  • Rapides mais ne fournissent pas toujours la solution optimale au problème donné.
  • Construit une solution pas à pas sans revenir sur ses décisions,
  • Obtenir un résultat optimum global
  • Effectue à chaque étape le choix qui semble le meilleur.

Les algorithmes gloutons utilisent une fonction d’évaluation f(n) pour chaque nœud


•Fonction d’évaluation

f(n) = h(n) (heuristique)    où   

•f(n)= estimation du coût de n à but
•h(n) = distance en ligne droite de n à but

Exemple:
On considère le problème où l’on doit rendre la monnaie pour une certaine somme S avec le moins possible de pièces de monnaies.


Sachant qu'on a des pièces de 1, 2, 5, 10, 20.
Quelle est la  solution optimale?
Avec S=26

  1. On va tout d'abord trier les types de pièces par valeurs décroissantes.
  2. Pour chaque valeur de pièce, maximiser le nombre de pièces choisies.
  3. Répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante tant que celle-ci n’est pas nulle.

Donc, pour  S=26 (3 pièces), on va obtenir:

  • 1 pièce de 20
  • 1 pièce de 5
  • 1 pièce de 1


Maintenant, si on veut rendre la somme S = 26  en pièces de 7, 6, 1. Quelle est la solution optimale?

•Algorithme glouton (8 pièces)
    • 3 Pièces de 7
    •  5 pièces de 1
•Solution optimale (4 pièces)
    • 2 pièces de 7
    • 2 pièces de 6

3.4. Algorithme A*

Faire une estimation du chemin complet (du nœud initial jusqu’à un but).
Fonction d’évaluation f(n) = g(n) + h(n)

g(n) = coût jusqu’à présent  pour atteindre n

h(n) = coût estimé de n à un but

f(n) = coût total du chemin passant par n à un but

Exemple: Le voyageur de commerce en Roumani



Etape 1:


Etape 2:



Etape 3:


Etape 4: