Module projet.solvers.SolverAStar
module pour le solver AStar
Expand source code
""" module pour le solver AStar """
from projet.outils.GrapheDeLieux import GrapheDeLieux
from projet.etape2.Etat import Etat
"""
* implementation du A etoile
"""
class SolverAStar :
"""
Implementation du A etoile
"""
# attributs
# //////////////////////////////////////////////
__nbEtatsExplores__ : int = 0
""" metrique pour comparer les solutions : nb d'etat explores """
__nbEtatsGeneres__ : int = 0
""" metrique pour comparer les solutions : nb d'etat generes """
# methodes
# //////////////////////////////////////////////
def aStar(e : Etat) :
""" implementation du A etoile pour la recherche du plus court chemin
depuis l'état e jusqu'à trouver une solution
:param e: etat de depart de la recherche
:return renverra l'etat solution s'il existe ou null sinon
"""
SolverAStar.__nbEtatsExplores__ = 0
SolverAStar.__nbEtatsGeneres__ = 0
# liste A_Faire, sera triee par ordre decroissant
AF = []
# on utilise des tables de hachage pour faciliter l'acces
# aux infos : ici l'etat sert de cle et permet d'acceder
# aux valeurs de f, g et au pere
f : dict = {} # HashMap<Etat, Double>()
g : dict = {} # HashMap<Etat, Double>()
pere : dict = {} # HashMap<Etat, Etat>()
f[e] = 0
g[e] = 0
pere[e] = None
AF.append(e)
SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + 1
while len(AF) != 0 :
courant = SolverAStar.__getBest__(AF, f)
SolverAStar.__nbEtatsExplores__ = SolverAStar.__nbEtatsExplores__ + 1
gcourant = g[courant] # poids de courant
if (courant.estSolution()) :
courant.displayPath(pere)
print("la lg du plus court chemin est ",g[courant])
SolverAStar.__affMetrique__(courant)
return courant
lesFils = courant.successeurs()
SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + len(lesFils)
for s in lesFils :
# poids de courant + (poids successeur - poids courant)
gsuivant = gcourant + courant.k(s)
if ( s not in g ) :
# nouvel etat
# donc mise a jour des tables de hachage et de AF
g[s] = gsuivant
f[s] = gsuivant + s.h()
pere[s] = courant
SolverAStar.__ajoutDsAF__(AF,s,f)
else :
if g[s] > gsuivant :
# on a ameliore le score du successeur
# donc remise a jour des tables de hachage
g[s] = gsuivant
f[s] = gsuivant + s.h()
pere[s] = courant
# remise ds AF s'il n'y est plus
if (s not in AF) :
SolverAStar.__ajoutDsAF__(AF,s,f)
return None
def aStarOpti(e : Etat) :
""" implementation du A etoile optimise pour la recherche du plus
court chemin depuis l'état e jusqu'à trouver une solution
(l'optimisation consiste à ne pas memoriser les peres, donc
a n'utiliser que si la liste des peres n'a pas d'importance)
:param e: etat de depart de la recherche
:return renverra l'etat solution s'il existe ou null sinon
"""
SolverAStar.__nbEtatsExplores__ = 0
SolverAStar.__nbEtatsGeneres__ = 0
# liste A_Faire, sera triee par ordre decroissant
AF = []
# on utilise des tables de hachage pour faciliter l'acces
# aux infos : ici l'etat sert de cle et permet d'acceder
# aux valeurs de f, g
f : dict = {} # HashMap<Etat, Double>()
g : dict = {} # HashMap<Etat, Double>()
f[e] = 0
g[e] = 0
AF.append(e)
SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + 1
while len(AF) != 0 :
courant = SolverAStar.__getBest__(AF,f)
#print("AF = ",SolverAStar.__afficheAF__(AF))
#print("courant = ",courant)
SolverAStar.__nbEtatsExplores__ = SolverAStar.__nbEtatsExplores__ + 1
gcourant = g[courant] # poids de courant
if (courant.estSolution()) :
courant.displayPath()
print("la lg du plus court chemin est ",g[courant])
SolverAStar.__affMetrique__(courant)
return courant
lesFils = courant.successeurs()
SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + len(lesFils)
for s in lesFils :
# poids de courant + (poids successeur - poids courant)
gsuivant = gcourant + courant.k(s)
if ( s not in g) :
# nouvel etat
# donc mise a jour des tables de hachage et de AF
g[s] = gsuivant
f[s] = gsuivant + s.h()
SolverAStar.__ajoutDsAF__(AF,s,f)
else :
if g[s] > gsuivant :
# on a ameliore le score du successeur
# donc remise a jour des tables de hachage
g[s] = gsuivant
f[s] = gsuivant + s.h()
# remise ds AF s'il n'y est plus
if (s not in AF) :
SolverAStar.__ajoutDsAF__(AF,s,f)
return None
def __getBest__(AF : list, f : dict) :
""" recherche du meilleur suivant la valeur de f """
e : Etat = AF[len(AF)-1]
AF.pop ()
return e
def __ajoutDsAF__(AF : list, s : Etat, f : dict) :
""" mise a jour de AF avec l'etat s en respectant l'ordre
decroissant impose par f """
val = f[s]
i = 0
while (i < len(AF) and (f[AF[i]] > val)) :
i = i + 1
if i == len(AF) :
AF.append(s)
else :
AF.insert(i,s)
def __afficheAF__(AF : list) :
""" pour affichage de la liste des etats a voir """
s : str = ""
for e in AF :
s = s +str(e) + " - "
return s
def __affMetrique__(sol : Etat) :
""" affichage des metriques """
print(str(sol)+"\n=======(nb d'etats explores = "
+str(SolverAStar.__nbEtatsExplores__)+")========\n"
+"=======(nb d'etats generes = "
+str(SolverAStar.__nbEtatsGeneres__)+")========\n")
Classes
class SolverAStar
-
Implementation du A etoile
Expand source code
class SolverAStar : """ Implementation du A etoile """ # attributs # ////////////////////////////////////////////// __nbEtatsExplores__ : int = 0 """ metrique pour comparer les solutions : nb d'etat explores """ __nbEtatsGeneres__ : int = 0 """ metrique pour comparer les solutions : nb d'etat generes """ # methodes # ////////////////////////////////////////////// def aStar(e : Etat) : """ implementation du A etoile pour la recherche du plus court chemin depuis l'état e jusqu'à trouver une solution :param e: etat de depart de la recherche :return renverra l'etat solution s'il existe ou null sinon """ SolverAStar.__nbEtatsExplores__ = 0 SolverAStar.__nbEtatsGeneres__ = 0 # liste A_Faire, sera triee par ordre decroissant AF = [] # on utilise des tables de hachage pour faciliter l'acces # aux infos : ici l'etat sert de cle et permet d'acceder # aux valeurs de f, g et au pere f : dict = {} # HashMap<Etat, Double>() g : dict = {} # HashMap<Etat, Double>() pere : dict = {} # HashMap<Etat, Etat>() f[e] = 0 g[e] = 0 pere[e] = None AF.append(e) SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + 1 while len(AF) != 0 : courant = SolverAStar.__getBest__(AF, f) SolverAStar.__nbEtatsExplores__ = SolverAStar.__nbEtatsExplores__ + 1 gcourant = g[courant] # poids de courant if (courant.estSolution()) : courant.displayPath(pere) print("la lg du plus court chemin est ",g[courant]) SolverAStar.__affMetrique__(courant) return courant lesFils = courant.successeurs() SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + len(lesFils) for s in lesFils : # poids de courant + (poids successeur - poids courant) gsuivant = gcourant + courant.k(s) if ( s not in g ) : # nouvel etat # donc mise a jour des tables de hachage et de AF g[s] = gsuivant f[s] = gsuivant + s.h() pere[s] = courant SolverAStar.__ajoutDsAF__(AF,s,f) else : if g[s] > gsuivant : # on a ameliore le score du successeur # donc remise a jour des tables de hachage g[s] = gsuivant f[s] = gsuivant + s.h() pere[s] = courant # remise ds AF s'il n'y est plus if (s not in AF) : SolverAStar.__ajoutDsAF__(AF,s,f) return None def aStarOpti(e : Etat) : """ implementation du A etoile optimise pour la recherche du plus court chemin depuis l'état e jusqu'à trouver une solution (l'optimisation consiste à ne pas memoriser les peres, donc a n'utiliser que si la liste des peres n'a pas d'importance) :param e: etat de depart de la recherche :return renverra l'etat solution s'il existe ou null sinon """ SolverAStar.__nbEtatsExplores__ = 0 SolverAStar.__nbEtatsGeneres__ = 0 # liste A_Faire, sera triee par ordre decroissant AF = [] # on utilise des tables de hachage pour faciliter l'acces # aux infos : ici l'etat sert de cle et permet d'acceder # aux valeurs de f, g f : dict = {} # HashMap<Etat, Double>() g : dict = {} # HashMap<Etat, Double>() f[e] = 0 g[e] = 0 AF.append(e) SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + 1 while len(AF) != 0 : courant = SolverAStar.__getBest__(AF,f) #print("AF = ",SolverAStar.__afficheAF__(AF)) #print("courant = ",courant) SolverAStar.__nbEtatsExplores__ = SolverAStar.__nbEtatsExplores__ + 1 gcourant = g[courant] # poids de courant if (courant.estSolution()) : courant.displayPath() print("la lg du plus court chemin est ",g[courant]) SolverAStar.__affMetrique__(courant) return courant lesFils = courant.successeurs() SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + len(lesFils) for s in lesFils : # poids de courant + (poids successeur - poids courant) gsuivant = gcourant + courant.k(s) if ( s not in g) : # nouvel etat # donc mise a jour des tables de hachage et de AF g[s] = gsuivant f[s] = gsuivant + s.h() SolverAStar.__ajoutDsAF__(AF,s,f) else : if g[s] > gsuivant : # on a ameliore le score du successeur # donc remise a jour des tables de hachage g[s] = gsuivant f[s] = gsuivant + s.h() # remise ds AF s'il n'y est plus if (s not in AF) : SolverAStar.__ajoutDsAF__(AF,s,f) return None def __getBest__(AF : list, f : dict) : """ recherche du meilleur suivant la valeur de f """ e : Etat = AF[len(AF)-1] AF.pop () return e def __ajoutDsAF__(AF : list, s : Etat, f : dict) : """ mise a jour de AF avec l'etat s en respectant l'ordre decroissant impose par f """ val = f[s] i = 0 while (i < len(AF) and (f[AF[i]] > val)) : i = i + 1 if i == len(AF) : AF.append(s) else : AF.insert(i,s) def __afficheAF__(AF : list) : """ pour affichage de la liste des etats a voir """ s : str = "" for e in AF : s = s +str(e) + " - " return s def __affMetrique__(sol : Etat) : """ affichage des metriques """ print(str(sol)+"\n=======(nb d'etats explores = " +str(SolverAStar.__nbEtatsExplores__)+")========\n" +"=======(nb d'etats generes = " +str(SolverAStar.__nbEtatsGeneres__)+")========\n")
Methods
def aStar(e: Etat)
-
implementation du A etoile pour la recherche du plus court chemin depuis l'état e jusqu'à trouver une solution
:param e: etat de depart de la recherche
:return renverra l'etat solution s'il existe ou null sinon
Expand source code
def aStar(e : Etat) : """ implementation du A etoile pour la recherche du plus court chemin depuis l'état e jusqu'à trouver une solution :param e: etat de depart de la recherche :return renverra l'etat solution s'il existe ou null sinon """ SolverAStar.__nbEtatsExplores__ = 0 SolverAStar.__nbEtatsGeneres__ = 0 # liste A_Faire, sera triee par ordre decroissant AF = [] # on utilise des tables de hachage pour faciliter l'acces # aux infos : ici l'etat sert de cle et permet d'acceder # aux valeurs de f, g et au pere f : dict = {} # HashMap<Etat, Double>() g : dict = {} # HashMap<Etat, Double>() pere : dict = {} # HashMap<Etat, Etat>() f[e] = 0 g[e] = 0 pere[e] = None AF.append(e) SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + 1 while len(AF) != 0 : courant = SolverAStar.__getBest__(AF, f) SolverAStar.__nbEtatsExplores__ = SolverAStar.__nbEtatsExplores__ + 1 gcourant = g[courant] # poids de courant if (courant.estSolution()) : courant.displayPath(pere) print("la lg du plus court chemin est ",g[courant]) SolverAStar.__affMetrique__(courant) return courant lesFils = courant.successeurs() SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + len(lesFils) for s in lesFils : # poids de courant + (poids successeur - poids courant) gsuivant = gcourant + courant.k(s) if ( s not in g ) : # nouvel etat # donc mise a jour des tables de hachage et de AF g[s] = gsuivant f[s] = gsuivant + s.h() pere[s] = courant SolverAStar.__ajoutDsAF__(AF,s,f) else : if g[s] > gsuivant : # on a ameliore le score du successeur # donc remise a jour des tables de hachage g[s] = gsuivant f[s] = gsuivant + s.h() pere[s] = courant # remise ds AF s'il n'y est plus if (s not in AF) : SolverAStar.__ajoutDsAF__(AF,s,f) return None
def aStarOpti(e: Etat)
-
implementation du A etoile optimise pour la recherche du plus court chemin depuis l'état e jusqu'à trouver une solution (l'optimisation consiste à ne pas memoriser les peres, donc a n'utiliser que si la liste des peres n'a pas d'importance)
:param e: etat de depart de la recherche
:return renverra l'etat solution s'il existe ou null sinon
Expand source code
def aStarOpti(e : Etat) : """ implementation du A etoile optimise pour la recherche du plus court chemin depuis l'état e jusqu'à trouver une solution (l'optimisation consiste à ne pas memoriser les peres, donc a n'utiliser que si la liste des peres n'a pas d'importance) :param e: etat de depart de la recherche :return renverra l'etat solution s'il existe ou null sinon """ SolverAStar.__nbEtatsExplores__ = 0 SolverAStar.__nbEtatsGeneres__ = 0 # liste A_Faire, sera triee par ordre decroissant AF = [] # on utilise des tables de hachage pour faciliter l'acces # aux infos : ici l'etat sert de cle et permet d'acceder # aux valeurs de f, g f : dict = {} # HashMap<Etat, Double>() g : dict = {} # HashMap<Etat, Double>() f[e] = 0 g[e] = 0 AF.append(e) SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + 1 while len(AF) != 0 : courant = SolverAStar.__getBest__(AF,f) #print("AF = ",SolverAStar.__afficheAF__(AF)) #print("courant = ",courant) SolverAStar.__nbEtatsExplores__ = SolverAStar.__nbEtatsExplores__ + 1 gcourant = g[courant] # poids de courant if (courant.estSolution()) : courant.displayPath() print("la lg du plus court chemin est ",g[courant]) SolverAStar.__affMetrique__(courant) return courant lesFils = courant.successeurs() SolverAStar.__nbEtatsGeneres__ = SolverAStar.__nbEtatsGeneres__ + len(lesFils) for s in lesFils : # poids de courant + (poids successeur - poids courant) gsuivant = gcourant + courant.k(s) if ( s not in g) : # nouvel etat # donc mise a jour des tables de hachage et de AF g[s] = gsuivant f[s] = gsuivant + s.h() SolverAStar.__ajoutDsAF__(AF,s,f) else : if g[s] > gsuivant : # on a ameliore le score du successeur # donc remise a jour des tables de hachage g[s] = gsuivant f[s] = gsuivant + s.h() # remise ds AF s'il n'y est plus if (s not in AF) : SolverAStar.__ajoutDsAF__(AF,s,f) return None