Lab 5 : Algorithmes de recherche¶

Fichiers¶

• libRechercheTemplate.py
• rechercheTemplate.py
• personne.py
• carte.py
• suisse.py
• testRecherche.py

Objectifs de la série¶

• Principes des trois algorithmes de recherche principaux.
• L’importance de l’heuristique pour la recherche par A*.

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, tiré de personne.py:

class Personne:

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

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

class Etudiant(Personne): # héritage

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

    def __str__(self):
        """ surcharge la fonction qui retourne une représentation en String de l'objet """
        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 cet exemple.

• Tout d’abord, nous commençons par définir une classe Personne. Ensuite, nous définissons un constructeur (__init__ (self,...)) qui met à jour les attributs publics nom et age, et une méthode anniversaire qui incrémente d’une unité l’âge d’une personne.
• De plus, nous définissons une autre classe Etudiant qui est elle-même une sous-classe de Personne. Comme vous pouvez le constater, le constructeur de la classe Etudiant fait appel au constructeur de la classe Personne pour instantier les attributs nom et age (vu qu’ils sont hérités).
• La méthode __str__(self) est une méthode de la classe Object et héritée (mais peut être surchargée). Dans la classe Etudiant, la méthode __str__(self) retourne une string de l’objet .

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)``)

Qui 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¶

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 :

• DFS (en profondeur d’abord) : place les nouveaux noeuds en tête de Q.
• BFS (en largeur d’abord) : place les nouveaux noeuds en queue de Q.
• A* : insère les nouveaux noeuds de manière à ce que Q soit ordonnée selon le coût de ses éléments. Le coût d’un noeud de recherche est évalué par une heuristique adaptée au problème. Il veut simplement modéliser la “distance” au but, de manière à privilégier l’exploration du noeud le plus prometteur.

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 carte.py.

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.

Ensuite, testez votre algorithme sur le fichier carte.py et, en option, sur suisse.py.

Que constatez-vous ?