Problème codage python algorithme A*

PangolinRobuste42 Messages postés 8 Date d'inscription vendredi 29 mars 2024 Statut Membre Dernière intervention 5 avril 2024 - 29 mars 2024 à 16:23
yg_be Messages postés 22692 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 16 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)

2 réponses

Whismeril Messages postés 19022 Date d'inscription mardi 11 mars 2003 Statut Contributeur Dernière intervention 17 avril 2024 656
29 mars 2024 à 16:36

Bonjour

pour éviter les réponses croisées, la question a aussi été posée sur CCM

https://forums.commentcamarche.net/forum/affich-38023634-probleme-codage-pyrthon-alorithme-a


0
yg_be Messages postés 22692 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 16 avril 2024
4 avril 2024 à 22:02

bonjour,

pourquoi es-tu satisfait de ta fonction heuristique?

0
Rejoignez-nous