liste de liste

Version imprimable

Voir 40 message(s) de cette discussion en une page

02/04/2010, 22h07
josmiley

avec les valeurs que tu donnes dans le premier post, t'es sensé trouver quoi comme resultat ?
02/04/2010, 22h08
hyuga33

josmiley, je parcours pas Adj_liste en entier mais ponctuellement suivant les élémets de c[0] qui agissent du coup comme une sorte de "pointeurs".
02/04/2010, 22h16
hyuga33

je retrouve 55 comme valeur.
Mais faut voir tourner en entier car c[0] et c[1] changent à chaque itération dans le __main__.

et là c'est bon ?

Code:

1
2
3
4
#si ce que tu veux c'est poids total
print sum([sum([Adj_liste[a] for a in c[0]],[]).count(x) for x in c[1]]) #>> 40
#si ce que tu veux c'est poids pour chaque sommet
print [sum([Adj_liste[a] for a in c[0]],[]).count(x) for x in c[1]]  #>> [1, 2, 3, 4, 4, 5, 5, 8, 8, 0]

1 pièce(s) jointe(s)

A la fin ça me retourne 0 mais avec :

Code:

1
2
3
4
5
6
7
8
9
def arete_inter(c):
    poids = 0
    setC1 = set(c[1])
    setC0 = set(c[0])
    for i in c[0]:        
        poids += len(setC1 & set(Adj_liste[i]))
    for i in c[1]:        
        poids += len(setC0 & set(Adj_liste[i])) 
    return poids

ça marche bien.

Actuellement voila mon code en entier, je mets un fichier avec pour des tests mais pour moi ça à l'air de marcher bien.

Code:

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
# -*- coding: cp1252 -*-
# ==============================================================================
# METHODE RECUIT SIMULE
# ==============================================================================
"""ALGORITHME RECUIT SIMULE"""
__author__  = ""
__version__ = "1.0"
__date__    = " Avril 2010 "
__usage__   = " Mini-Projet."
# ------------------------------------------------------------------------------
from random import randrange, sample, choice, random, randint
from math import log, exp
import time
# ------------------------------------------------------------------------------
def complementaire():
    """renvoie la classe complementaire de c1: c2"""
    c1 = (sample(xrange(nb_sommet),int(nb_sommet/2)))
    c2 = [ i for i in xrange(nb_sommet) if not (i in c1) ]
    c1.sort()
    c2.sort()
    return c1, c2   
# ------------------------------------------------------------------------------
def configinit():
    """construit la classe initiale c1"""
    return (sample(xrange(nb_sommet),int(nb_sommet/2)))
# ------------------------------------------------------------------------------
def arete_inter(c):
    """renvoie le poids des arêtes entre c[0] et c[1]"""
    poids = 0
    setC1 = set(c[1])
    setC0 = set(c[0])
    for i in c[0]:        
        poids += len(setC1 & set(Adj_liste[i]))
    for i in c[1]:        
        poids += len(setC0 & set(Adj_liste[i])) 
    return poids
# ------------------------------------------------------------------------------
def Temp_init(taux_acc,c):
    """renvoie la donnée initiale de température"""
    temp = [ arete_inter(c) for i in range(100) ]
    temp.sort()
    return sum( temp[-1-i] for i in range(20) )/20/log(1./taux_acc)
# ------------------------------------------------------------------------------
def pick_and_drop(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = c[0][:],c[1][:]
    n = randint(1,2)
    if (n == 1) and (len(c1)>int(nb_sommet/2)-p):
        a = choice(c1)
        c2.append(a)
        c1.remove(a)
    elif (n == 2) and (len(c2)>int(nb_sommet/2)-p):
        a = choice(c2)
        c1.append(a)
        c2.remove(a)
    else:
        if (len(c1)>int(nb_sommet/2)-p):
            a = choice(c1)
            c2.append(a)
            c1.remove(a)
        else:
            a = choice(c2)
            c1.append(a)
            c2.remove(a)  
    c1.sort()
    c2.sort()
    return c1,c2
# ------------------------------------------------------------------------------
def sweep_and_swap(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = [],[]
    c1.extend(c[0])
    c2.extend(c[1])
    temp1 = choice(c1)
    temp2 = choice(c2)
    c1.remove(temp1)
    c2.remove(temp2)
    c1.append(temp2)
    c2.append(temp1)
    c1.sort()
    c2.sort()
    return c1,c2
# -----------------------------------------------------------------------------
def matrice_en_liste(Adj):
    """Convertit une matrice d'adjacence en liste d'adjacence."""
    adj_liste = []
    v = []
    n = len(Adj)
    for i in range(n):
        adj_liste.append([])
        v.append(i)
        for j in range(n):
            if (Adj[i][j] == 1) and (j not in v):
                adj_liste[i].append(j)
    return adj_liste
# ==============================================================================                   
def main():
    global nb_sommet, Adj_liste, taux_acc, coef, p, gel, equil_stat
 
    fichier = raw_input ("Quel fichier souhaitez-vous utiliser?")
    f = open(fichier,"r")
    donnees = f.read()
    nb = donnees.split()
    nb_sommet = int(nb[0])
    nb_arete = int(nb[1])
    print "Le nombre de sommet est ",nb_sommet, "et le nombre d'arêtes est ",nb_arete
    f.close()
    liste1=[]
    liste2=[]
    p=int(nb_sommet*0.01)+1
    for i in range(nb_arete):
        liste1.append(nb[2+3*i])
        liste2.append(nb[3+3*i])
    Adj = [[0 for j in range(nb_sommet)] for i in range(nb_sommet)]
    for i in range(nb_arete):
        Adj[int(liste1[i])-1][int(liste2[i])-1]=1
        Adj[int(liste2[i])-1][int(liste1[i])-1]=1
 
    Adj_liste = matrice_en_liste(Adj)
    courante = complementaire()
    poids = arete_inter(courante)
    taux_acc = raw_input("Donnez la valeur du taux acceptation si vous souhaitez?(par défaut il vaut 0.6)")
    if taux_acc == '':
        taux_acc = 0.6
    else:
        taux_acc = float(taux_acc)
    coef = raw_input("Donnez la valeur du coefficient de décroissance de la température si vous souhaitez?(par défaut il vaut 0.9)")
    if coef == '':
        coef = 0.9
    else:
        coef = float(coef)
    equil_stat = nb_sommet
    gel = raw_input("Donnez la valeur pour laquelle on estime que le système est gelé?(par défaut elle vaut 60)")
    if gel == '':
        gel = 60
    else:
        gel = int(gel)
 
    poids = arete_inter(courante)
    t = Temp_init(taux_acc,courante)
    Ncourante = pick_and_drop(courante)
    solution = courante
 
 
    choix = raw_input("tapez 1 si vous voulez utiliser le pick_and_drop, taper 2 si vous voulez utiliser le sweep_and_swap")
    temps = time.time ()
    if choix == '1':
 
        while gel>0:
            k = 0
            while k<equil_stat:
                k += 1
                Ncourante = pick_and_drop(courante)
                delta = arete_inter(Ncourante) - arete_inter(courante)
                if delta<0:
                    courante = Ncourante
                    if arete_inter(Ncourante)<poids:
                        poids = arete_inter(Ncourante)
                        solution = Ncourante
                else:
                    a = random()
                    if a<=exp(-delta/t):
                        courante = Ncourante
            t = t*coef
            gel -= 1
            print gel
    if choix == '2':
 
        while gel>0:
            k = 0
            while k<equil_stat:
                k += 1
                Ncourante = sweep_and_swap(courante)
                delta = arete_inter(Ncourante) - arete_inter(courante)
                if delta<0:
                    courante = Ncourante
                    if arete_inter(Ncourante)<arete_inter(solution):
                        poids = arete_inter(Ncourante)
                        solution = Ncourante
                else:
                    a = random()
                    if a<=exp(-delta/t):
                        courante = Ncourante
            t = t*coef
            gel -= 1
            print gel         
 
    print "le temps mis par l'algo est", (time.time () - temps)       
    print "Le poids est: " ,poids
 
if __name__ == "__main__":
    main()
 
# ============================================================================

pour le fichier 20s.txt le poids final est de 40 ou 39. L'algo ne donne pas une solution exacte mais pour ce genre de petit fichier on s'en rapproche réellement.

02/04/2010, 22h44
eyquem

Ce qui me trouble, c’est qu’il y a deux listes dans c.

On a maintenant l’information que les valeurs des deux sous-listes sont tous les sommets d’une figure : c[0] +c[1] est la liste de tous les sommets , n’est ce pas ?

Mais pourquoi sont ils distribués en deux sous-listes c[0] et c[1] ? Quelles significations ont ces deux sous-listes ?

Code:

1
2
3
4
5
6
7
8
9
def arete_inter(c):
    poids = 0
    setC1 = set(c[1])
    setC0 = set(c[0])
    for i in c[0]:        
        poids += len(setC1 & set(Adj_liste[i]))
    for i in c[1]:        
        poids += len(setC0 & set(Adj_liste[i])) 
    return poids

ça fait plus du tout ce que tu voulais au départ ... je rejoinds donc la question de eyquem ...

02/04/2010, 22h51
hyuga33

pour ta première question eyquem, la réponse est oui c[0]+c[1]=ensemble des sommets.
Au départ j'ai un graphe avec n sommets et des arêtes entre certains sommets de poids valant 1.
Je divise la liste de mes sommets en deux listes contenue dans c.
Le but est de trouver deux listes de sommets dont les arêtes passant entre ces deux listes soient minimales.
02/04/2010, 23h09
eyquem

Donc au départ, il y a n sommets d’un graphe,
on les prend tous et on les répartit dans deux listes selon une certaine loi,
PUIS on fait un test.
C'est bien ceci ?
Le calcul de poids constitue ce test ?

Ensuite une autre distribution des sommets dans deux listes est essayée et le test est refait sur les deux nouvelles sous-listes c[0] et c[1] ?

Sur l’ensemble des distributions testées , on en sélctionne en définitive une.
Mais le critère de choix n’est pas clair:
deux listes de sommets dont les arêtes passant entre ces deux listes soient minimales
Le pluriel est ici troublant. Ça ne constitue pas UN critère.

Est-ce que tu as le code qui permet de tester des distributions l’une après l’autre ?
Ou bien me trompe je ?

je refait bien une distribution aléatoire des sommets, je les déplace un par un grace à cet algo:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def pick_and_drop(c):
    """calcul les voisins de c[0] dans c[1]"""
    c1,c2 = c[0][:],c[1][:]
    n = randint(1,2)
    if (n == 1) and (len(c1)>int(nb_sommet/2)-p):
        a = choice(c1)
        c2.append(a)
        c1.remove(a)
    elif (n == 2) and (len(c2)>int(nb_sommet/2)-p):
        a = choice(c2)
        c1.append(a)
        c2.remove(a)
    else:
        if (len(c1)>int(nb_sommet/2)-p):
            a = choice(c1)
            c2.append(a)
            c1.remove(a)
        else:
            a = choice(c2)
            c1.append(a)
            c2.remove(a)  
    c1.sort()
    c2.sort()
    return c1,c2

Ensuite, je regarde si j'ai une meilleure solution ou pas.
Voila le code pour ça:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    while gel>0:
        k = 0
        while k<equil_stat:
            k += 1
            Ncourante = pick_and_drop(courante)
            delta = arete_inter(Ncourante) - arete_inter(courante)
            if delta<0:
                courante = Ncourante
                if arete_inter(Ncourante)<poids:
                    poids = arete_inter(Ncourante)
                    solution = Ncourante
            else:
                a = random()
                if a<=exp(-delta/t):
                    courante = Ncourante
        t = t*coef
        gel -= 1
        print gel

Mon critére d'optimalité est le poids = nombre d'arêtes entre les deux listes e sommets. J'espere que je me suis bien exprimé.

02/04/2010, 23h21
josmiley

au debut c[0] c'etait une liste de "pointeurs" vers Adj_liste dont il fallait sortir le nombre total d'intersections...maintenant c'est une liste de sommets ... je pige plus rien.
02/04/2010, 23h24
hyuga33

quand je disai que c'étit une sorte de "pointeurs" je voulais dire dans la boucle. En fait c'était grâce à lui que l'on sait ou on vas chercher nos info.
Il y a toujours un lien entre c[0] et Adj_liste étant donner que le premier est une liste de sommet et le deuxième une liste d'information(avec qui ce sommet est relié) sur les sommets.
02/04/2010, 23h31
eyquem

Code:

je pige plus rien.

C’est vrai que c’est un peu le bastringue. Mais j’aime bien... à la fin il va rester 20 lignes...

Ce qu’il faut nous expliquer maintenant, c’est ce que tu appelles une arête, stp

Parce que je ne comprends pas

Citation:

arêtes passant entre ces deux listes
d'arêtes entre les deux listes
02/04/2010, 23h35
hyuga33

une arête est un lien entre un sommet et un autre. Si il y a une arête entre deux sommets alors ces deux sommets sont liés. Mais il n'y a pas d'arêtes entre tous les sommets.
C'est pour ça que lorsque j'ai mes deux listes de sommets je veux que les sommets de la 1ère liste possédent le moins possible d'arêtes allant vers les sommets de l'autre liste.
02/04/2010, 23h37
josmiley

le 1er post était a peu pres clair ...
il faut donc chercher la jonction 'la moins lourde' entre c[0]-Adj_list-c[1] ... j'ai bon ?
02/04/2010, 23h47
hyuga33

c'est ça josmiley, t'as compris.
Je suis vraiment désolé de pas être trés clair, j'ai vraiment du mal à m'exprimer..
03/04/2010, 00h03
josmiley

Code:

print zip([len(set(c[0])&set(a))for a in Adj_liste],[len(set(c[1])&set(a))for a in Adj_liste])

retourne une liste de couples representant les liens sous la forme [ (c[0]-Adj_liste[0], c[1]-Adj_liste[0]), (c[0]-Adj_liste[1], c[1]-Adj_liste[1]), ...]
après j'ai pas bien comprite ce que tu veux.
03/04/2010, 00h12
eyquem

OK. J’en étais resté avec l’image d’une polyèdre, mais c’est un graphe et il peut y avoir des “arêtes’ qui se croisent.

J’ai pris le code à partir du début pour bien piger.

Pour le moment j’ai affiché Adj: c’est plein de 1

Citation:

[ [0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0],
[1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0],
[0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0],
[1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
[0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
[0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0],
[1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1],
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0],
[1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0] ]
03/04/2010, 00h15
hyuga33

c'est lamatrice d'adjacence.
A chaque fois qu'il existe une arête entre le sommet i et j alors la valeur de la matrice en (i,j) vaut 1.
Cette matrice donne la relation entre tous les sommets.
03/04/2010, 00h30
josmiley
Citation:

Envoyé par josmiley

Code:

print zip([len(set(c[0])&set(a))for a in Adj_liste],[len(set(c[1])&set(a))for a in Adj_liste])

retourne une liste de couples representant les liens sous la forme [ (c[0]-Adj_liste[0], c[1]-Adj_liste[0]), (c[0]-Adj_liste[1], c[1]-Adj_liste[1]), ...]
après j'ai pas bien comprite ce que tu veux.

et si tu veux la somme de tous les liens:
Code:

1 2 z = zip([len(set(c[0])&set(a)) for a in Adj_liste],[len(set(c[1])&set(a))for a in Adj_liste]) print sum([ sum(i) for i in z if not 0 in i])
ça me donne 96.

Voir 40 message(s) de cette discussion en une page