Problème codage python algorithme A*

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)