Recherche¶

class Element:
    """ Un élément dans l'espace de recherche. """

    def __init__(self, nom=''):
        """
            :param str nom: nom de l'élément (optionnel).
        """
        self.nom = nom

    def distance(self, element):
        """ Retourne la distance entre l'éléments courant et un autre.

            (A implémenter différemment dans les sous-classes, si nécessaire.)
        """

        return 1

    def __eq__(self, autre):
        return self.nom == autre.nom

    def __hash__(self):
        return hash(str(self))

    def __repr__(self):
        return '{}'.format(self.nom)

from math import sqrt
from .element import Element

class Ville(Element):
    """ Un élément représentant une ville.
    """

    def __init__(self, x, y, nom=''):
        """
            :param x: coordonnée en x de la ville.
            :param y: coordonnée en y de la ville.
            :param str nom: nom de la ville.
        """

        Element.__init__(self, nom)
        self.x = x
        self.y = y

    def distance(self, ville):
        """ Distance euclidienne entre la ville courante et la ville ``ville``. """
        return sqrt((self.x-ville.x)**2 + (self.y-ville.y)**2)

    def __eq__(self, autre):
        if not isinstance(autre, Ville):
            return False
        return self.x == autre.x and self.y == autre.y and self.nom == autre.nom

    def __hash__(self):
        return hash(str(self))

    def __repr__(self):
        return '{}({}, {})'.format(self.nom, self.x, self.y)

from copy import copy

class Espace:
    """ Un espace de recherche dans lequel les éléments sont connectés par des arcs. """

    def __init__(self, elements=None, arcs=None):
        """
            :param list elements: une liste d'éléments.
            :param list arcs: une liste d'arcs sous forme de tuples\
            ``(element_1, element_2)``.
        """

        self.elements = []
        if elements is not None:
            self.elements = sorted(self.elements, key=lambda e: e.nom)

        self.arcs = []
        if arcs is not None:
            self.ajoute_arcs(arcs)

    def ajoute_arcs(self, arcs):
        """
            Ajoute des arcs à l'espace.

            Les éventuels éléments nouveaux mentionnés dans\
            les arcs seront aussi ajoutés à la liste d'éléments
            de l'espace.

            :param list arcs: une liste d'arcs.
        """
        for element_1, element_2 in arcs:
            if not element_1 in self.elements:
                self.elements.append(element_1)
            if not element_2 in self.elements:
                self.elements.append(element_2)

            if not (element_1, element_2) in self.arcs:
                self.arcs.append((element_1, element_2))

        self.elements = sorted(self.elements, key=lambda e: e.nom)

    def trouve_voisins(self, element):
        """
            :return: les voisins d'un élément.
        """
        voisins = []

        for element_1, element_2 in self.arcs:
            if element_1 == element:
                voisins.append(element_2)
            if element_2 == element:
                voisins.append(element_1)

        voisins = sorted(voisins, key=lambda v: v.nom)

        return voisins

    def __repr__(self):
        rep = ''
        for element in self.elements:
            rep += '{}, '.format(element)
            rep += 'avec voisins: '
            voisins = self.trouve_voisins(element)
            rep += ', '.join(map(str, voisins))
            rep +='\n'

        return rep

from math import sqrt

class Noeud:
    """ Noeud généré de façon dynamique par un algorithme de recherche,\
        encapsulant un élément de l'espace de recherche.
    """

    def __init__(self, element, parent=None, cout=0, cout_f=0):
        """
            :param Element element: l'élément encapsulé.
            :param Noeud parent: le noeud parent du noeud courant, c'est-à-dire\
            le noeud qui a conduit à la découverte du noeud courant au cours de la\
            recherche.
            :param cout: coût du noeud courant (utile uniquement pour A\*).
            :param cout_f: coût heuristique du noeud courant (utile uniquement\
            pour A\*).
        """
        self.element = element
        self.parent = parent
        self.cout = cout
        self.cout_f = cout_f

    def __repr__(self):
        rep = '<{}, {}, {}>'.format(self.element,
                                   round(self.cout),
                                   round(self.cout_f))
        return rep

from .noeud import Noeud

class Recherche:
    """ Classe générique pour la recherche. """

    echec = 'échec'

    def __init__(self, espace, optimisee=False):
        """
            :param espace: l'espace de recherche.
            :param optimiser: indique si la recherche doit être optimisée pour éviter\
            les cycles.
        """

        self.espace = espace
        self.optimisee = optimisee

    def recherche(self, depart, but):
        """ Recherche un chemin allant de ``depart`` jusqu'à ``but``.

            :param depart: l'élément de départ.
            :param but: le l'élément but.

            :return: le chemin de ``depart `` à ``but``, ou ``'échec'``\
            s'il n'existe pas de chemin.
        """

        # L'heuristique à utiliser (utile uniquement pour A\*).
        self.h = lambda e: e.distance(but)

        noeud_depart = Noeud(depart, None, 0, self.h(depart))
        noeud_but = Noeud(but)

        return self.recherche_chemin(noeud_depart, noeud_but)

    def recherche_chemin(self, noeud_depart, noeud_but):
        """ Recherche un chemin allant de ``depart`` jusqu'à ``but``.

            :param noeud_depart: le noeud de départ.
            :param noeud_but: le noeud but.

            :return: les éléments encapsulés au long du chemin,\
            ou ``'échec'`` s'il n'existe pas de chemin.
        """
        queue = [noeud_depart]
        iterations = 0
        trace = {}

        while len(queue) > 0:
            noeud = queue.pop(0)

            if self.optimisee and self.detecte_cycle(trace, noeud):
                continue

            iterations += 1
            print('Itération {}: {}'.format(iterations, noeud))

            if noeud.element == noeud_but.element:
                return self.trouve_chemin(noeud)
            else:
                trace[noeud.element] = noeud
                successeurs = self.trouve_successeurs(noeud)
                queue = self.ajoute_successeurs(queue, successeurs)

        return Recherche.echec

    def trouve_chemin(self, noeud):
        chemin = []
        while noeud is not None:
            chemin.insert(0, noeud.element)
            noeud = noeud.parent

        return chemin

    def detecte_cycle(self, trace, noeud):
        """ Vérifie si le noeud courant a déjà été visité par un autre chemin,\
            et donc si l'on vient de parcourir un cycle dans l'espace de recherche.

            :param dict trace: un dictionnaire contenant les noeuds déjà visités ;\
            le dictionnaire associe à chaque élément le noeud qui l'encapsule.\
            Cela permet de tester rapidement si l'élément du noeud courant est\
            présent dans un autre noeud déjà visité.
            :return: True si le noeud courant a déjà été visité.
        """

        return noeud.element in trace

    def trouve_successeurs(self, noeud):
        """ Trouve les successeurs du noeud courant.

            :return: une liste contenant les noeuds successeurs du noeud courant.
        """
        successeurs = []
        voisins = self.espace.trouve_voisins(noeud.element)
        for voisin in voisins:

            # Évite les cycles à deux éléments a - b - a - b ...
            if noeud.parent is not None and noeud.parent.element == voisin:
                continue

            # Coût jusqu'au noeud successeur = coût jusqu'au noeud courant +
            # distance entre les deux noeuds.
            distance = noeud.element.distance(voisin)
            cout = noeud.cout + distance

            # Coût estimé = coût jusqu'au noeud successeur + coût estimé entre
            # le noeud successeur et le but.
            cout_f = cout + self.h(voisin)

            successeur = Noeud(voisin, noeud, cout, cout_f)
            successeurs.append(successeur)

        return successeurs

    def ajoute_successeurs(self, queue, successeurs):
        """ Ajoute les successeurs ``successeurs`` à la queue ``queue``\
            (à implémenter différemment pour DFS, BFS et A\*).

            La queue peut éventuellement être modifiée par la méthode.

            :param list queue: la queue des noeuds à explorer.
            :param list successeurs: les successeurs à ajouter.
            :return: la queue contenant tous les successeurs dans le\
            bon ordre.
        """

        # Nous retournons une liste vide pour éviter de déclencher une exception,
        # mais cette méthode doit être surchargée dans les sous-classes.
        return []

from .recherche import Recherche
from .noeud import Noeud

class RechercheBFS(Recherche):
    """ Recherche de chemin avec BFS. """

    def ajoute_successeurs(self, queue, successeurs):
        return queue + successeurs

from .recherche import Recherche
from .noeud import Noeud

class RechercheDFS(Recherche):
    """ Recherche de chemin avec DFS. """

    def ajoute_successeurs(self, queue, successeurs):
        return successeurs + queue

from moteurs_recherche.recherche import Recherche
from moteurs_recherche.noeud import Noeud

class RechercheAStar(Recherche):
    """ Recherche de chemin avec A\*. """

    def detecte_cycle(self, trace, noeud):
        if noeud.element not in trace:
            return False

        autre = trace[noeud.element]
        return autre.cout_f <= noeud.cout_f

    def ajoute_successeurs(self, queue, successeurs):
        queue = queue + successeurs
        queue = sorted(queue, key=lambda n: n.cout_f)

        return queue