Problème codage python algorithme A*

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.

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:

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()