Bonjour à tous / toutes,

Je viens vers vous parce que ça fait plusieurs heures que je m'arrache les cheveux sur un problème sûrement bidon !

Pour vous mettre dans le contexte : je suis étudiant et je dois faire un exercice de méta-heuristique. En gros, on a une grille de 5 * 5 éléments, et chaque élément est relié à son voisin. On mélange la grille, en gardant les liaisons, et on doit remettre la grille en l'état pour avoir des liaisons optimales en utilisant un algo de recuit simulé.
C'est donc ce que j'essaye de faire, en faisant un affichage de la grille à chaque étape. En affichage, j'affiche donc une grille de 5 * 5 rectangles, avec des lines pour les liaisons, et du text pour les numéros d'identifiant de chaque élément. Voilà le code, si vous voulez le run (j'utilise Python 2.7.10) :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import sys
import math
import copy
from random import shuffle
from random import randint
from math import sqrt
import time
from Tkinter import *
 
objet = []
 
class Component:
    def __init__(self, id_, x_, y_):
        self.id = id_
        self.x = x_
        self.y = y_
        self.links = []
 
def newList():
        liste = []
    for i in range(5):
        for j in range(5):
            bob = Component(i*5+j, i, j)
            liste.append(bob)
            if i > 0 :
                liste[i*5 -5 + j].links.append(bob)
                bob.links.append(liste[i*5 -5 + j])
            if j > 0 :
                liste[i*5 -1 + j].links.append(bob)
                bob.links.append(liste[i*5 -1 + j])
    return liste
 
def shuffleList(l_):
    shuffle(l_)
    for i in range(5):
        for j in range(5):
            l_[i*5+j].x = i
            l_[i*5+j].y = j
    return l_
 
def printComponentsList(l_):
    for x in l_:
        n = []
        for item in x.links:
            n.append(item.id)
        print("[{}]({};{}) -> {}".format(x.id, x.x, x.y, n))
 
def dist(c1, c2):
    val = (c1.x-c2.x)*(c1.x-c2.x) + (c1.y-c2.y)*(c1.y-c2.y)
    return sqrt(val)
 
def energy(l_):
    total = 0
    for x in l_:
        for item in x.links:
            total = total + dist(x, item)
    return total
 
def switch(l_):
    #print("---pre")
    #printComponentsList(l_)
    a = randint(0,24)
    b = randint(0,24)
    lbis = []
    for e in l_:
        lbis.append(copy.copy(e))
    c1 = lbis[a]
    c2 = lbis[b]
    c1.x = l_[b].x
    c1.y = l_[b].y
    c2.x = l_[a].x
    c2.y = l_[a].y
    lbis[a] = c2
    lbis[b] = c1
    #print("---pre")
    #printComponentsList(l_)
    #print("---next")
    #printComponentsList(lbis)
    #print("----")
    return lbis
 
def draw_squares(l_, canvas, fenetre):
    canvas.delete(ALL)
    canvas.update()
    for i in objet:
        canvas.delete(fenetre, i)
    del objet[:]
    for i in l_:
        print ("i dans draw_square : ID = ", i.id, ", coordx = ", i.x, ", coordy = ", i.y)
        for j in i.links:
            x_temp_i = i.x * 50 * 2 + 50
            y_temp_i = i.y * 50 * 2 + 50
            x_temp_j = j.x * 50 * 2 + 50
            y_temp_j = j.y * 50 * 2 + 50
            #a = canvas.create_line(x_temp_i + 25, y_temp_i + 25, x_temp_j + 25, y_temp_j + 25)
            b = canvas.create_rectangle(x_temp_i, y_temp_i, x_temp_i + 50, y_temp_i + 50, fill="white")
            c = canvas.create_rectangle(x_temp_j, y_temp_j, x_temp_j + 50, y_temp_j + 50, fill="white")
            d = canvas.create_text(x_temp_i + 25, y_temp_i + 25, text=i.id, font="Arial 15", fill="blue")
            e = canvas.create_text(x_temp_j + 25, y_temp_j + 25, text=j.id, font="Arial 15", fill="blue")
            #objet.append(a)
            objet.append(b)
            objet.append(c)
            objet.append(d)
            objet.append(e)
 
    canvas.update()
 
def boucle(liste, canvas, fenetre):
    s = liste
    e = energy(liste)
    k = 0
    while k < 100:
    sn = switch(s)
    en = energy(sn)
    if en < e :
        s = sn
        e = en
        print("Energy: {}".format(en));
                canvas.delete(ALL)
                draw_squares(s, canvas, fenetre)
                printComponentsList(s)
    k += 1
 
def main():
    fenetre = Tk();
    canvas = Canvas(fenetre, width=550, height=550)
    canvas.pack()
    liste = newList()
    printComponentsList(liste)
    draw_squares(liste, canvas, fenetre)
    print("Energy: {}".format(energy(liste)));
    liste = shuffleList(liste)
    printComponentsList(liste)
    draw_squares(liste, canvas, fenetre)
    print("Energy: {}".format(energy(liste)));
 
    btn = Button(text='go', command= lambda liste=liste, canvas=canvas, fenetre=fenetre:boucle(liste, canvas, fenetre))
    btn.pack(); 
    fenetre.mainloop()
 
if __name__ == '__main__': main()
Ce qui nous intéresse, ce sont les trois dernières fonctions, main() qui init un peu tout, boucle() qui lance l'algo et draw_squares() qui change la grille à chaque étape nous rapprochant de la solution. Et la fonction printComponentsList() permet d'afficher la liste des éléments avec leur coordonnées sur la grille et leurs liaisons.
Quand je run : je fais un draw_squares avec la liste init, donc bien triée et avec les bonnes liaisons. Je n'affiche pas cette grille, elle m'intéresse pas vraiment. On mélange la grille, on affiche la nouvelle grille, qui correspond parfaitement à la liste affichée. Ensuite on run la boucle en appuyant sur "Go". Et là, rien ne va plus.
J'ai l'impression que même avec un delete de tout élément du canvas, il affiche tout ce qui était là avant, et rajoutant seulement les éléments nouveaux. Donc dès la première étape de la boucle, quand j'essaie d'afficher la grille, les éléments n'ont pas bougé, les liaisons déjà là avant ne bougent pas, mais il affiche les nouvelles liaisons, celles des éléments qui sont censé changés. Au final, à la fin, j'ai une grille avec des numéros ID complètement désordonnée par rapport à la liste donnée dans le shell, et le print dans draw_squares me confirme que la liste est bonne et l'affichage est faux, certains numéros ID sont présents plusieurs fois, d'autres se superposent à certains, les liaisons ne correspondent plus à rien... C'est la bazar, et j'ai essayé plusieurs trucs, plusieurs fonctions, j'ai pas réussi à arranger la chose.

Si vous voulez tester, j'ai laisser des print de debug. Deux lignes sont commentées, ce sont les liaisons que je n'affiche pas, chaque chose en son temps, c'est déjà le bazar avec les éléments et les ID. Chose curieuse encore : quand je rajoute un time.sleep(1) après avoir delete chaque élément, et avant la boucle for pour les canvas.create... les étapes ne s'affichent, seulement l'étape finale. Et le résultat est tout autant décevant.

Voilà, j'espère vous avoir bien décrit le soucis, en espérant aussi que vous pouvez m'aider !

Merci bien !