PangolinRobuste42
Messages postés8Date d'inscriptionvendredi 29 mars 2024StatutMembreDernière intervention 5 avril 2024
-
29 mars 2024 à 16:23
yg_be
Messages postés22733Date d'inscriptionlundi 9 juin 2008StatutContributeurDernière intervention29 avril 2024
-
4 avril 2024 à 22:02
Bonjour, dans le cadre de mes études, je dois coder un programme qui résout un jeu du taquin
mon choix c'est porté sur un algorithme A*, cependant, mon programme n'est pas efficace, et le chemin trouvé est souvent trop long
je ne comprends pas pourquoi mon algorithme prend autant de coup pour résoudre un taquin, j'ai pourtant une bonne fonction heuristique( Manhattan )
pour un taquin 3*3, la solution trouvé est un chemin de plus de 60 configurations, ce qui est trop long
pour un 4*4, le chemin est presque toujours d'une longueur superieur à 200
ci joint mon code
# # # # # # renvoie toutes les positions du taquin après une actions licite #
def f_pose_k(M):
'''renvoie la position de la case qui bouge '''
return [k for k in range(len(M)) if M[k] == len(M)][0]
def deplacement_possible(taille_M,k):
'''renvoie les coordonnées des déplacements possibles si la case 16 est à la position k'''
liste=[]
#disjonctions classiques des cas pour sélectionner les déplacements licites
if k%taille_M != 1: #colonne gauche
liste.append(k-1)
if k > taille_M: #ligne haute
liste.append(k-taille_M)
if k%taille_M != 0: #colonne droite
liste.append(k+1)
if k <= (taille_M**2 - taille_M): #ligne basse
liste.append(k+taille_M)
return liste
def permutation_taquin(M,pose_k,cible):
'''permute deux cases''' #cette fonction sert pour une compréhension de texte
N = [M[k] for k in range(len(M))] #pour ne pas modifier M avec les permutations
N[pose_k],N[cible] = N[cible],N[pose_k] #permute les deux cases cibles
return N
def possibilite(M):
'''renvoie toutes les positions du taquin après une actions licite'''
pose_k = f_pose_k(M) #position de la case guidant le mouvement
dep_licite = deplacement_possible(int(len(M)**0.5), pose_k+1) #liste des déplacements licites de la matrice
return [ permutation_taquin(M,pose_k,cible-1) for cible in dep_licite ]
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # partie fonction heuristique # # # # # # # # # # # # # # # # # # #
matrice_de_poids = [5,5,4,4, #ici taille 4
4,4,3,3,
3,2,2,2,
2,1,1,1]
def ligne(taille_M,case): #programme pour la fonction heuristique_1
'''ligne du jeu du taquin'''
for k in range(1,taille_M+1):
if case <= k*taille_M:
return k
return taille_M
def heuristique_Manhattan(M):
'''fonction heuristique dite "Manhattan", distance idéal'''
taille_M = int(len(M)**0.5) # # # provisoire, le len sera calculé au début de la fonction total, et la variable len M déjà établie.*
distance = 0
for case in range(taille_M**2-1):
#print(case+1)
difference_hauteur = abs(ligne(taille_M,M[case])-ligne(taille_M,case+1)) #différence de hauteur(en terme de ligne) entre la case rangée et la case du sudoku
distance += difference_hauteur #compte les déplacements verticaux
#note on peut pondérer la distance en la multipliant par matrice_de_poids[case]
distance += abs((max(case+1,M[case]))- ( min(case+1,M[case]) + taille_M*difference_hauteur))
#compte les déplacement horizontaux, principe: on ramène les cases sur une même ligne(après les déplacements verticaux, puis soustraction
return distance
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # algorithme_A_star # # # # # # # # # # # # # # # # # # # # # # # #
def tri_insertion_dichotomie(liste,noeuds): #On fait le choix d'un tri par insertion car chaque élément est ajouté 1 par 1.
'''ajoute un élément dans une liste trié par dichotomie''' #optimisation par récursive
n = len(liste)
if n == 1:
if liste[0][3] > noeuds[3]: #evalue pour la valeur de l'heuristique, ie pour l'indice 3
return [noeuds,liste[0]]
else:
return [liste[0],noeuds]
if noeuds[3] <= liste[n//2][3]: #si élément est dans la partie inférieure de la liste trié
return tri_insertion_dichotomie(liste[:n//2],noeuds) + liste[n//2:]
if noeuds[3] > liste[n//2][3]: #si élément est dans la partie supérieure de la liste trié
return liste[:n//2] + tri_insertion_dichotomie(liste[n//2:],noeuds)
def algorithme_A_star(M,heuristique):
'''cherche un chemin en étant guidée par un fonction heuristique'''
n = len(M)
#idée directrice de l'algo:
#Nous allons créer un graph au fur et à mesure. Chaque noeud est obtenu par une action licite du taquin qui y contient
#le graph est ordonné par le nombre d'action nécessaire pour y aller.
#le point clef est: nous allons naviguer dans le graphe de maniere ciblée (nous evalurons prioritairement les noeuds possedants une valeur heuristique faible)
#ce que contient un noeud:
#Si un noeuds n'a jamais été testé: noeuds[0] = True, reciproquement, noeuds[0] = False,
#de plus, un noeuds possede: -la matrice représentatrice du taquin
#-le chemin réalisé pour y parvenir
#-un approximation du nombre d'action nécessaire pour résoudre cette matrice.
graphe = [[False,M,[],heuristique(M)]] #initialisation #cette liste va être triée au fur et à mesure, afin de classer les potentiels candidats selon la veleur de la fonciton heuristique
tete = [False,M,[],heuristique(M)] #la tete est la configurtion du taquin qui est etudié, et est changé a chaque tour de boucle.
indice = 0
while tete[1] != [k for k in range(1,n+1)]: #tant que le taquin n'est pas résolu
for noeuds in possibilite(tete[1]): #ajoute les taquin obtenus depuis la tete au graphe, en triant ce dernier par la fonction heuristique associé aux taquins
graphe = tri_insertion_dichotomie(graphe,[True,noeuds,tete[2]+[tete[1]],heuristique(noeuds)]) #tri le graph en fonction de la valeur de l'heuristique
indice = 0
#print(graphe,"graphe")
while not graphe[indice][0] or graphe[indice][1] in [taquin[1] for taquin in graphe if not taquin[0]]:
#si le taquin n'a jamais été testé et n'appartient pas aux taquins deja testé(possibilité de revenir sur un meme taquin apres differents deplacements
indice += 1 #on cherche le candidat qui respecte les conditions ci dessus, le graphe etant trié par son heuristique.
#print(memoire,not graphe[indice][0], graphe[indice][1] in memoire,"passe ou casse")
graphe[indice][0] = False
tete = graphe[indice]
return tete[2]+[tete[1]] #compile le chemin et le taquin final
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # fonction final # # # # # # # # # # # # # # # # # # # # # # # # # #
def show(M):
n = int(len(M)**0.5)
for k in range(n):
print([M[k*n + j] for j in range(n)])
def taquin(M):
chemin = algorithme_A_star(M,heuristique_Manhattan)
for taquin in chemin:
print('to')
show(taquin)
return len(chemin)
