Lab 5 : Algorithmes de recherche


Dans cette série, vous allez vous familiariser avec les trois principaux algorithmes de recherche, à savoir en profondeur d'abord (DFS), en largeur d'abord (BFS) et selon A*. Nous les utiliserons pour trouver un chemin entre deux villes (peu importe la longueur du chemin).

Durée estimée : 2 heures.

Fichiers :

libRechercheTemplate.py
rechercheTemplate.py
personne.py
carte.py.

Objectifs de la série

Introduction rapide à la programmation objet en Python

Dans cette série, nous allons devoir utiliser des types de structures de données abstraits (TDA) pour la gestion des villes et des noeuds de recherche. Comme en java, Python vous offre la possibilité de créer des classes et de manipuler des objets. (La syntaxe complète pour la gestion de classe se trouve au chapitre 9 du tutoriel de Python).

Afin de vous familiariser avec la syntaxe Python, voici un petit exemple :

  class Personne:

   # constructeur
   def __init__(self,nom,age):
      self.nom = nom
      self.age = age

    def anniversaire(self):
      self.age+=1

  class Etudiant(Personne): # héritage

   # constructeur
    def __init__(self,nom,age,section):
      Personne.__init__(self,nom,age) # héritage
      self.section=section

    # surcharge la fonction qui retourne une représentation en String de l'objet
    def __str__(self):
      out = "Etudiant %s a %d ans et est en section: %s\n" % (self.nom, self.age,self.section)
      return out

    def changeSection(self, nouvelleSection):
      self.section=nouvelleSection


  # liste globale
  etudiants=[]

  def afficheEtudiants():
  print( "Listes des étudiants:\n")
    for etud in etudiants:
       print( "\t", etud)


  toto = Etudiant( "Toto", 23, "SSC" )
  print( toto)
  toto.anniversaire()
  toto.changeSection( "INF" )
  print( toto)

 

L'exemple ci-dessus affichera:

 

  Etudiant Toto a 23 ans et est en section: SSC

  Etudiant Toto a 24 ans et est en section: INF

Étudions plus en détail cette exemple.

ATTENTION 1 : Malheureusement, et contrairement à beaucoup de langages de programmation, Python ne vous laisse pas décider de comment sont passés les paramètres (par références ou par valeurs). Python travaille en object-reference, qui est en fait une combinaison du passage en référence et par valeur. Plus concrètement, si le paramètre est un objet mutable (une liste, un dictionnaire, notre classe Personne), alors l'objet est passé en référence. Cependant, si l'objet n'est pas mutable (nombre, string, tuple), alors le paramètre est passé en valeur.

ATTENTION 2 : Vu l'ambiguïté causée par la passage en paramètre, certaines fonctions (comme append, extend, sort) retourneront None si on travaille sur des listes mutables (comme c'est le cas dans notre exemple). Ceci est normal, car il y a eu beaucoup de confusion dans le passé de savoir si ces fonctions retournaient un nouvel objet ou bien une référence sur l'ancien. La solution (simple) de ce problème est de NE PAS DIRECTEMENT retourner le résultat.

Pour comprendre ce problème, regardez l'exemple ci-dessous :

  toto = Etudiant("Toto",23,"INF" )
  titi = Etudiant("Titi",22,"SSC")
  tata = Etudiant("Tata",25,"SSC")

  etudiants=[toto,titi,tata]
  print( etudiants.sort(key = lambda e : e.age))

L'exemple ci-dessus affichera :

  None

Tandis que :

  toto = Etudiant("Toto",23,"INF" )
  titi = Etudiant("Titi",22,"SSC")
  tata = Etudiant("Tata",25,"SSC")

  etudiants=[toto,titi,tata]
  etudiants.sort(key = lambda e : e.age)
  afficheEtudiants()


affichera :

  Liste des étudiants:
    Etudiant Titi a 22 ans et est en section: SSC
    Etudiant Toto a 24 ans et est en section: INF
    Etudiant Tata a 25 ans et est en section: SSC

 

Exercice 1 : Codage des classes de base

La classe Element

Dans cet exercice, vous allez devoir manipuler des éléments dans un espace à deux dimensions. Nous programmerons des algorithmes de recherche de chemin le plus court entre deux points. Commencez par copier le fichier libRechercheTemplate.py chez vous.

Le constructeur __init__ ()

Notre élément est défini dans un espace à deux dimensions, c'est à dire avec une coordonnée en X et une en Y. De plus, notre élément aura un nom qui lui servira d'identifiant et une liste de voisins.
Écrivez le constructeur qui initialise tous ces attributs depuis des valeurs passées en paramètres, sauf pour l'attribut voisins qui sera initialisé à []. En résumé, la classe Element aura quatre attributs :

Les méthodes de classe

Ensuite, écrivez les fonctions suivantes :

La classe Noeud

Lors de la recherche, chaque Element sera modélisé par un noeud dans l'arbre de recherche. De ce fait, nous allons maintenant écrire une classe Noeud permettant de manipuler un noeud.

Le constructeur __init__()

La classe Noeud contient trois attributs :

Les méthodes de classe

Ensuite, écrivez les fonctions suivantes :

Rappel : Pour A*, nous utiliserons la fonction f(n)=c(n)+h(n).

La méthode successeurs (self, but)

Lors de la recherche, vous allez devoir générer tous les successeurs du noeud sur lequel vous travaillez. Écrivez une fonction successeurs qui prend en paramètre l'objet de destination finale but et qui va retourner tous les voisins du noeud sur lequel on se trouve.

De plus, vous allez devoir mettre à jour les attributs coutC et coutF pour chaque nouveau successeur trouvé. Vous utiliserez l'objet but (de type Element) pour calculer la distance h(n).

Indication 1 : Utilisez la fonction map(une_fonction,une_liste).

Indication 2 : N'oubliez pas de convertir les voisins et le noeud but en objets de type Noeud. Pour ce faire, utilisez de nouveau la fonction map.

La classe Ville

La classe Element définie auparavant servait à définir des éléments en général. Dans cet exercice, vous allez travailler avec des villes. Cependant, une ville a exactement les mêmes attributs qu'un Element. La seule différence sera le contenu retourné par la fonction __str__().

Depuis le fichier rechercheTemplate.py, complétez la classe Ville de façon à ce quelle soit une sous-classe de element.
La fonction __repr__() devra retourner une représentation en String de l'objet Ville, et contenir la valeur de tous les attributs.

La classe Villes

Comme vous devez vous en douter, nous allons devoir gérer un ensemble d'objets Ville ; cette ensemble formera une carte. Comme vous pouvez le constater dans le fichier rechercheTemplate.py, il existe un dictionnaire global CARTE. C'est celui-ci qui sera utilisé pour stocker toutes nos villes.

Vous allez maintenant implémenter la classe Villes. 

Le constructeur __init__ ()

Contrairement aux autres classes, celle-ci ne contient pas d'attributs. Cependant, elle utilisera le dictionnaire global CARTE pour stocker toutes les villes. Utilisez le constructeur pour initialiser CARTE à {}.

Les méthodes de classe

Ensuite, écrivez les méthodes suivantes :

Exercice 2 : Algorithmes de recherche

Nous allons maintenant développer un outil de recherche qui implémente les trois principaux algorithmes (DFS, BFS et A*) vus en cours.

Le principe de tout algorithme de recherche est de trouver un but (ici une ville de destination) à partir d'un point de départ (la ville de départ). Comme vu en cours, l'espace exploré par le processus de recherche est un arbre constitué de noeuds et d'arcs. Chaque noeud de recherche correspond à une étape dans la recherche. L'exploration d'un noeud de recherche permet éventuellement de trouver des successeurs, c'est à dire de nouveaux noeuds de recherche.

Les algorithmes que nous allons étudier ne se différencient que par la gestion de la liste des noeuds ouverts Q : 

L'algorithme de recherche est donné ci-dessous : 

 
  Recherche (Noeud_depart, Noeud_but, methode)
    1. Q <- [Noeud_depart] 
    2. WHILE Q non vide
    3.   n <- premier (Q), Q <- reste (Q)
    4.   IF n est un noeud but THEN
    5.     RETURN n
    6.   ELSE
    7.     S <- successeurs de n
    8.     Q <- ajouterSuccesseurs(Q,S,methode)
    9.   END IF
   10. END WHILE
   11. RETURN ECHEC
  END Recherche
 

Comme vous pouvez le constater, l'algorithme de base est le même quelle que soit la méthode utilisée (DFS, BFS et A*). La seule chose qui change, c'est la façon d'ajouter les successeurs à la liste Q.

Plus concrètement, la fonction qui ajoute les successeurs à Q est définie comme suit : 

 
  AjouteSuccesseurs(Q, S, methode)
    1. IF methode is "DFS" THEN 
    2.   RETURN S + Q
    3. ELSE IF methode is "BFS" THEN
    4.   RETURN Q + S
    5. ELSE IF methode is "A*" THEN
    6.   Q = Q + S
    7.   RETURN Q.sort()
    8. ELSE
    8.   RETURN ECHEC
   10. END IF
  END AjouteSuccesseurs
 

Dans l'heuristique A*, la liste Q doit être triée par ordre croissant du résultat de la fonction d'évaluation f(n) ; par conséquent vous devez fournir un argument key à la fontion sort().

Implémentez l'algorithme de recherche ci-dessus pour les méthodes DFS, BFS et A*. Utilisez les classes Villes, Ville et Noeud. 

Ensuite, testez-le sur le fichier test.

Qu'en concluez-vous ? Quelle est l'importance de l'heuristique utilisée par A* ? Regardez surtout le nombre de noeuds de recherche examinés. Que pouvez-vous conclure sur les algorithmes en regardant la longueur des chemins (en nombre de villes traversées) ?
 

Optionnel

Pour vous montrer l’utilité de ces algorithmes de recherche, un autre fichier de test vous est proposé : suisse.py. Ce fichier contient des villes suisses avec leurs relations. Lancez les algorithmes de recherche sur ce fichier et constatez le résultat. Pourquoi l’algorithme DFS boucle-t-il à l’infini ? Testez maintenant en commentant le code appelant l’algorithme DFS ; quel résultat obtenez-vous maintenant ?

Exercice 3: algorithmes de recherche avec détection de cycles

Comme vous avez pu le constater, l'algorithme n'est pas très efficace car certains noeuds sont visités plusieurs fois (DFS et BFS). De plus, il est nécessaire de gérer les boucles infinies dans le cas où le graphe est cyclique.

Cette détection de cycles nécessite la maintenance d'une liste de noeuds déjà explorés, C. Dans le cas de DFS et BFS, et avant d'étendre un noeud, l'algorithme va contrôler la présence de ce noeud dans C. Si le noeud est déjà présent, cela veut dire que l'exploration des successeurs a déjà été faite, et que par conséquence, il n'est plus nécessaire de l'explorer.

Cependant, l'algorithme A* autorise un noeud n à être visité plusieurs fois, et donc à se trouver dans la liste C. Dans ce cas, on va revisiter ce noeud si et seulement si le coût f(n) est inférieur au coût f(n) déjà présent dans C.

En résumé, l'algorithme de recherche optimisée est le suivant : 

 
  RechercheOptimisee(Noeud_depart, Noeud_but, methode)
    1. Q <- [Noeud_depart] 
    2. C <- [] 
    3. WHILE Q non vide
    4.   n <- premier(Q), Q <- reste(Q)
    5.   IF n est un noeud but THEN
    6.     RETURN n
    7.   ELSE
    8.     IF (n not in C or 
   ...(n=n' in C and f(n)<f(n') and methode is  "A*")  THEN
    9.       S <- successeurs de n
   10.       Q <- ajouterSuccesseurs(Q,S,methode)
   11.       ajoute n dans C
   12.     END IF
   13.   END IF
   14. END WHILE
   15. RETURN ECHEC
  END RechercheOptimisee
 

En vous basant sur l'algorithme ci-dessus, implémentez l'algorithme de recherche optimisée.

Indication : Dans le fichier libRechercheTemplate.py, implémentez une classe Noeuds qui vous permettra de manipuler les noeuds de C.

Ensuite, testez votre algorithme sur le fichier test et, en option, sur celui-ci.

Que constatez-vous ?

Copyright LIA - 2006-2007. Author: vincent.schickel-zuber@epfl.ch - le 28 Mars 2006 - Last modified 18 May 2013 by Marina Boia