Problème codage python algorithme A*
Résolu
PangolinRobuste42
Messages postés
10
Statut
Membre
-
Phil_1857 -
Phil_1857 -
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 prend beaucoup de coup pour résoudre un taquin. Je ne comprends pas pourquoi mon algorithme prend autant de coup pour résoudre un taquin, ce qui le rend très lent pour des taquins 4*4
Ci-joint mon code :
# Renvoie toutes les positions du taquin
# après une actions licites
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.
"""
# Pour ne pas modifier M avec les permutations
N = [M[k] for k in range(len(M))]
# Permute les deux cases cibles
N[pose_k] , N[cible] = N[cible] , N[pose_k]
return N
def possibilite(M):
"""
Renvoie toutes les positions du taquin après
une actions licite.
"""
# Position de la case guidant le mouvement
pose_k = f_pose_k(M)
# Liste des déplacements licites de la matrice
dep_licite = deplacement_possible(
int(len(M) ** 0.5),
pose_k + 1
)
return [
permutation_taquin(M,pose_k,cible-1)
for cible in dep_licite
]
# Heuristique
matrice_de_poids = [
5, 5, 4, 4, # ici taille 4
4, 4, 3, 3,
3, 2, 2, 2,
2, 1, 1, 1
]
# Programme pour la fonction heuristique_1
def ligne(taille_M, case):
"""
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éale.
"""
# taille_M provisoire
# len sera calculé au début de la fonction total
# et la variable len M déjà établie.
taille_M = int(len(M)**0.5)
distance = 0
for case in range(taille_M ** 2 - 1):
# print(case + 1)
# Différence de hauteur(en terme de ligne)
# entre la case rangée et la case du sudoku
difference_hauteur = abs(
ligne(taille_M, M[case]) -
ligne(taille_M,case+1)
)
# Compte les déplacements verticaux
distance += difference_hauteur
# 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éplacements horizontaux
# Principe: on ramène les cases sur une même ligne
# (après les déplacements verticaux, puis soustraction)
return distance
# A*
# On fait le choix d'un tri par insertion car chaque élément
# est ajouté 1 par 1.
def tri_insertion_dichotomie(liste,noeuds):
"""
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'algorithme :
# Nous allons créer un graphe au fur et à mesure.
# Chaque nœud est obtenu par une action licite
# du taquin qui y contient le graphe, est ordonné par
# le nombre d'actions nécessaires pour y aller.
# Le point clef est: nous allons naviguer dans le graphe
# de manière ciblée (nous évaluerons prioritairement
# les nœuds possédant une valeur heuristique faible)
# ce que contient un nœud.
# Si un nœud n'a jamais été testé : noeuds[0] = True
# Réciproquement, noeuds[0] = False,
# De plus, un nœud possède:
# - 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.
# Initialisation:
# Cette liste va être triée au fur et à mesure,
# afin de classer les potentiels candidats selon la valeur
# de la fonction heuristique
graphe = [
[False, M, [], heuristique(M)]
]
# La tête est la configuration du taquin qui est étudié,
# et qui est changée à chaque tour de boucle.
tete = [False, M, [], heuristique(M)]
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 tête au
# graphe, en triant ce dernier par la fonction
# heuristique associé aux taquins.
# Trie le graphe en fonction de la
# valeur de l'heuristique.
graphe = tri_insertion_dichotomie(
graphe,
[True, noeuds, tete[2] + [tete[1]],
heuristique(noeuds)]
)
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 déjà testés
# (possibilité de revenir sur un même taquin
# après différents déplacements.
# On cherche le candidat qui respecte les conditions
# ci-dessus, le graphe étant trié par son heuristique.
indice += 1
# print(
# memoire,
# not graphe[indice][0],
# graphe[indice][1] in memoire,
# "passe ou casse"
# )
graphe[indice][0] = False
tete = graphe[indice]
# Compile le chemin et le taquin final
return tete[2] + [tete[1]]
# Fonction finale
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)
A voir également:
- En n'utilisant que le clavier, quel mot obtenez-vous ? pix
- Codage ascii - Guide
- Citizen code python avis - Accueil - Outils
- Codage binaire - Guide
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Python pix ✓ - Forum Python
7 réponses
Bonjour,
Si j'ai bien compris, tu veux utiliser l'algorithme A* dans le graphe des configuration du taquin :
- Chaque nœud correspond à une disposition possible du taquin
- On construit un lien (u, v) si en un mouvement, on peut passer de u à v.
- Le but est alors de trouver un chemin entre la configuration de départ s et une configuration cible t (typiquement, celle où les nombres sont dans le bon ordre). L'existence d'un tel chemin n'est pas garantie (voir ici).
- Comme ce graphe est très grand (voir ici), tu ne peux pas te permettre de le construire complètement, et c'est pourquoi tu vas vouloir le construire dynamiquement, en fonction des configurations qui te paraissent les plus prometteuses.
En admettant que j'ai bien compris il y a plusieurs aspects pour avoir un programme efficace :
- Dans ton problème, il est clair qu'il existe dans ce graphe plusieurs chemins pour aller d'une configuration u à une configuration v (ne serait ce qu'en faisant des alternance de mouvement inutile). Cela signifie que tu as intérêt dans ton exploration à être prudent, et à ne pas traiter une configuration déjà traitée. On parle alors de programmation dynamique. Je suppose que c'est ce que tu appelles dans ton code "si un taquin a déjà été testé" ?
Dans ton implémentation :
- Certaines fonctions sont fréquemment appelées et pas optimisées. Par exemple f_pose_k construit une liste en mémoire (dont seule la première valeur est utile). Il vaudrait mieux utiliser la méthode find.
- Tu passes ton temps à recalculer la largeur/hauteur de ta grille (ici 4) avec len(M) ** 0.5. Ce n'est pas très stratégique pour plusieurs raisons.
- De manière générale, un calcul de puissance est cher (plus qu'un appel à math.sqrt)
- Ici, il suffirait de calculer une fois pour toute cette valeur (appelons la n) et passer n en paramètre à tes fonctions qui en ont besoin.
- Tu mémorises dans chaque nœud le chemin utilisé pour l'atteindre. Ce chemin n'étant en général pas unique, cela veut dire qu'il faut élire le meilleur.
- Ce n'est sans doute pas un problème dans A* (comparé à Dijkstra) mais ça soulève surtout un problème du point de vue de la mémoire.
- Supposons que ton chemin soit s -> u -> v -> w -> t, cela signie que dans u : tu mémorises [s], puis dans v : [s, u], puis dans w [s, u, v], puis dans t [s, u, v, w]. Clairement c'est redondant donc ça prend plus de mémoire et surtout ça te force à construire toutes ces listes.
- En général, on utilise plutôt un vecteur de prédécesseurs (donc on associe à un sommet depuis quel sommet on l'a atteint -- quel arc dans le cas général). Dans mon exemple, ce serait {u: s, v: u, w: v, t: w}. Pour reconstruire le chemin, on part de la cible et on "remonte" le vecteur pour reconstruire le chemin.
Peut-être aussi que ça vaudrait le coup que tu regardes des implémentations existantes, par exemple celle-ci.
Update: mon code ne donnait pas le chemin optimal (bien qu'il fonctionnait) car il faut en plus de la valeur heuristique, ajouter la profondeur de graphe (sinon, le programme peut préférer une configuration avec un faible valeur heuristique même si elle est extrêmement loin dans le graphe).
ainsi, à la ligne 199, il fallait ajouter "+len(tete[2])" après l'appel de la fonction heuristique
merci pour vos aides, elles m'ont été utiles.
bonjour,
tu n'expliques pas comment appeller ton code.
Salut.
Avec un simple array.
board = [7, 4, 2, 9, 1, 3, 8, 5, 6] taquin(board)
Pour ma part j'aurais choisi le 0 pour la case vide, si on met un 0 dans l'array, on se prend un IndexError, ce qui ne me semble pas trop logique, mais j'ai pas trop cherché à comprendre le code =)
Il faut déjà savoir que la moitié des combinaisons sont insolubles, voir wikipédia.
Rien ne semble testé dans le code de PangolinRobuste si le taquin est soluble.
Puis de toute façon, python ni même aucun langage de script n'est adapté pour résoudre ce genre de problème si on cherche la rapidité, le même algo en c, c++ sera bien plus rapide, y a pas mal d'exemples sur internet de la résolution des taquins dans divers langages et plusieurs algos.
Bonjour,
J'ai déjà fait un Taquin 3x3 avec Tkinter en utilisant les distances Manhattan
Ca fonctionne, mais évidement, pour que le problème soit soluble, il faut
partir de la configuration à atteindre, et déplacer les chiffres pour mélanger
avant de lancer la résolution
Prêt à mélanger:
Mélangé: on lance la résolution:
Résolu:
bonjour,
premièrement, pour les taquin non solubles, j'ai créé une autre fonction afin de savoir si un taquin est soluble ou non.
même si nos notation des cases dans le taquin diffèrent, (moi, je bouge ta case "8")
Est ce possible de jeter un coup d'œil à ton code si c'est du python?
merci dans tout les cas, bonne soirée
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Tes appels incessants à la fonction ligne() sont totalement inutiles. Il est préférable de créer un tableau, et d'y enregistrer les réponses possibles à cette fonction.
Cette fonction ligne() est très mal écrite, mais cela devient accessoire si tu l'appelles beaucoup moins.
La fonction de distance ne me semble pas être adéquate pour évaluer la proximité d'un taquin par rapport à la solution finale.
Je pense donc qu'il est inutile de la calculer, et, surtout, de trier en fonction de cela.
Si j'étais toi, je ne testerais surement pas des taquins de 16 cases. Je regarderais comment le programme se comporte avec des taquins compliqués de 9 cases. Par exemple avec un taquin "impossible" de 9.
Bonjour,
Tu voulais voir mon code, je n'avais pas vu ta réponse :-)
Mon taquin n'est jamais insoluble car on commence par déplacer les cases
à partir de la configuration ordonnée:
# Taquin 06/04/2023 10:42:34
# | 1 2 3
# ---------------------------
# 1 | 1 2 3
# |
# 2 | 4 5 6
# |
# 3 | 7 8 9
import copy
import random
from tkinter import *
def wait():
''' Waits for 1 second, then unlocks wait_var '''
global n
n += 1
if(n == 2):
wait_var.set(1)
return
main_win.after(800, wait)
def display_config(config, wait_or_not):
''' Displays the current configuration after 2 seconds '''
global n
if(wait_or_not):
n=0
wait()
main_win.wait_variable(wait_var)
graph_area.delete('all')
display_empty_grid()
for k in range(1,10):
c, r = (k-1)%3, (k-1)//3
x1,y1,x2,y2,xc,yc = coords_from_row_col(r,c)
t = ' ' if config[k] == 9 else str(config[k])
graph_area.create_text(xc, yc, text = str(t), fill = 'chocolate1', font = ('bold'))
def get_successors(configs, successors):
''' Finds the successors of a given configuration'''
nbs_to_move = [0]
empty = configs[0].index(9)
successors_nb = len(successors[empty])
for k in range(successors_nb):
config_copy = copy.copy(configs[0])
one_successor = successors[empty][k]
nbs_to_move.append(config_copy[one_successor])
config_copy[empty] = config_copy[one_successor]
config_copy[one_successor] = 9
configs.append(config_copy)
return(successors_nb, configs, nbs_to_move)
def manhattan(config, final_config):
''' Calculates the manhattan distance for a given configuration '''
m_dist = 0
for k in range(1,10):
current_nb = config[k]
col, row = (k-1)%3+1, (k-1)//3+1
dx, dy = final_config[current_nb][0]-col, final_config[current_nb][1]-row
coeff = (16 if current_nb == 1 else 1)
m_dist += coeff * (dx**4 + dy**4)
return(m_dist)
def get_minimum_distance(sn, nbs_to_move, last_moved_nb, m_distances):
''' Calculates the minimum distance of the successors, records the index of the corresponding config '''
minimum = 1000
for k in range(1,sn+1):
if(nbs_to_move[k] != last_moved_nb):
if(m_distances[k] < minimum):
minimum = m_distances[k]
config_index = k
elif(m_distances[k] == minimum):
if(random.random() < 0.5): config_index = k
return(minimum, config_index)
def run_search():
global configs, stop
tries, last_moved_nb = 0, 0
successors = {1:[2,4], 2:[1,3,5], 3:[2,6], 4:[1,5,7], 5:[2,4,6,8], 6:[3,5,9], 7:[4,8], 8:[5,7,9], 9:[6,8]}
final_config = {1:[1,1], 2:[2,1], 3:[3,1], 4:[1,2], 5:[3,2], 6:[1,3], 7:[2,3], 8:[3,3], 9:[2,2]}
while(True):
tries += 1
#Successors of current configuration
sn, configs, nbs_to_move = get_successors(configs, successors)
#Manhattan distance of each successor config
m_distances = [1000]
for k in range(1,sn+1): m_distances.append(manhattan(configs[k], final_config))
#Looking for the minimum distance, records the index of the corresponding config
minimum, config_index = get_minimum_distance(sn, nbs_to_move, last_moved_nb, m_distances)
if(minimum == 0):
display_config(configs[config_index], True)
graph_area.create_text(125, 270, text = 'Gagné en {} coups !'.format(tries), fill = 'green', font = ('bold'))
stop = True
break
last_moved_nb = nbs_to_move[config_index]
tmp = configs[config_index]
configs = []
configs.append(tmp)
display_config(configs[0], True)
graph_area.create_text(125, 220, text = '{}'.format(tries), font = ('bold'))
def coords_from_row_col(row,col):
''' Returns the square coordinates (top left and bottom right, center) from row and column '''
x1,y1 = x0+SQUARE*col, y0+SQUARE*row
x2,y2 = x1+SQUARE, y1+SQUARE
xc,yc = x1+(x2-x1)/2, y1+(y2-y1)/2
return(x1,y1,x2,y2,xc,yc)
def row_column_from_coords(x,y):
''' Returns row and column from the mouse coordinates '''
for i in range(0,SIZE):
for j in range(0,SIZE):
x1,y1,x2,y2,xc,yc = coords_from_row_col(i,j)
if(x > x1 and x < x2 and y > y1 and y < y2):
r,c = i,j
break
return(r,c)
def move_figure(x,y):
global click_nb, current_figure, configs
if(click_nb == 0):
click_nb += 1
r,c = row_column_from_coords(x,y)
k = r*3+c+1
current_figure = configs[0][k]
configs[0][k] = 9
display_config(configs[0], False)
else:
click_nb = 0
r,c = row_column_from_coords(x,y)
k = r*3+c+1
configs[0][k] = current_figure
display_config(configs[0], False)
def click_CB(event):
''' Mouse mb1 click '''
global stop, move, configs, click_nb
if(not stop):
if(event.y > 300):
move = False
run_search()
elif(move):
move_figure(event.x, event.y)
else:
game_init()
def display_empty_grid():
''' Displays a square of SIZE*SIZE boxes'''
col, _width = 'green2', 5
graph_area.delete('all')
graph_area.create_rectangle(x0, y0, x0+SIZE*SQUARE, y0+SIZE*SQUARE, width = _width, outline = col)
for k in range(1,SIZE):
graph_area.create_line(x0+k*SQUARE, y0, x0+k*SQUARE, y0+SIZE*SQUARE, width = _width, fill = col)
graph_area.create_line(x0, y0+k*SQUARE, x0+SIZE*SQUARE, y0+k*SQUARE, width = _width, fill = col)
def game_init():
global configs, stop, move , click_nb
configs = [[9 for k in range (10)]]
configs[0]= [0,1,2,3,4,9,5,6,7,8]
stop, move = False, True
click_nb = 0
display_empty_grid()
display_config(configs[0], False)
SIZE, SQUARE = 3,50
x0, y0 = 50,50
main_win = Tk()
main_win.geometry('275x350+600+50')
main_win.title('Taquin')
main_win.bind("<Button-1>", click_CB)
graph_area = Canvas(main_win, width = 250, height = 300, bg = 'ivory')
graph_area.place(x=10, y = 10)
wait_var = IntVar()
game_init()
main_win.mainloop()
Bonsoir,
Des fois mamiemando, je me demande pourquoi tu te décarcasses à faire des réponses aussi élaborées et complètes, alors qu'en majorité, le créateur du sujet ne prend jamais la peine de revenir au moins dire un petit merci. Suffit de regarder les sujets où tu es le dernier intervenant avec des reponses toujours détaillées. Tristesse, ccm se meurt...
Bonsoir à tous,
J'espère que mamiemando, que je salue, continuera longtemps à nous dispenser ce savoir qu'elle est une des seules à exposer avec tant de talent pédagogique et d'abnégation.
Si des visiteurs aussi éphémères qu'irrespectueux n'appliquent pas les règles élémentaires de politesse, qui devraient prévaloir même en dehors de la charte, ignorée ou contestée.
Au moins ces mises au point servent elles à celles et ceux qui essaient d'améliorer leurs connaissances pour mieux aider les autres membres, en exigeant au minimum les salutations usuelles et sans attendre un retour qui statistiquement est la portion congrue.
Alors, à quoi sert que mamiemando se décarcasse ? Au moins à recevoir parmi d'autres mes remerciements pour son dévouement.
je te remercie pour ta réponse très complète!, je vais tacher de résoudre tous les problèmes que tu as judicieusement relevés dès que mes concours se finissent.
merci encore !
Je profite de cette suite de commentaires pour remercier toutes les personnes qui apprécient les réponses que je prends le temps d'écrire, car c'est quelque chose qui me permet de garder le feu sacré :-) J'espère que mes recommandations serviront, mais ça, ce n'est plus entre mes mains ;-)
c'est bon, les concours étant passés, j'ai effectué tes modifications pour optimiser mon code. merci pour tes conseils