Demande d'aide pour élaborer un algo pour un pb simple mais long

Version imprimable

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

06/11/2007, 09h11
Nemerle

Je reprends l'idée de graphe où chacun des 9 sommets a 5 flèches entrantes & 5 sortantes: pour chacun des 9 sommets s1...s9, on défini

- un double compteur In/Out initialisé à IO(si)=(5,5), afin de compter le nombre des flèches en entrée/sortie
- d'un double vecteur V(si,8,2) de booléens représentant les voisins In/Out, avec un double compteur v(si,2) comptant le nombre d'éléments de V(si,-,1) à false et le nombre d'éléments de V(si,-,2) à false (histoire de connaître le nombre de candidats disponible)

Il "suffit" alors de définir un ordre lexicographique de sélection des flèches par sommet; à chaque flèche si --> sj, on fait

- IO(si)=(a,b) => IO(si)=(a-1,b)
- IO(sj)=(x,y) => IO(sj)=(x,y-1)

- on passe à True le "ième" élément de V(sj,-,2) et v(sj,-,2)=v(sj,-,2)-1
- on passe à True le "jème" élément de V(si,-,1) et v(si,-,1)=v(sj,-,1)-1

A chaque itération possible on choisit une flèche permettant de réduire les IP sans les passer en négatif; il y a échec de construction quand l'un des v(si,-,-) ou v(sj,-,-) est inférieur à la composante correspondante de IO(si) ou IO(sj).

Une fois un graphe terminé, on détermine sa matrice d'adjacence...
06/11/2007, 09h30
mougel

Citation:

Envoyé par fremen167

Mougel, est-ce que ça peut répondre à ton besoin ?

C'est effectivement beaucoup plus structuré que tout ce que j'ai pu faire.
Je vais écrire ton programme en VBA (le seul langage que je maîtrise)

Cependant j'ai un doute, car avec des règles analogues (heuristiques jusqu'à la 5è ligne) mon programme n'en finit pas de tourner...
06/11/2007, 10h07
mougel

Citation:

Envoyé par Nemerle

Je reprends l'idée de graphe où chacun des 9 sommets a 5 flèches entrantes & 5 sortantes: pour chacun des 9 sommets s1...s9, on défini

Je ne distingue pas bien l'apport d'une telle formalisation.
Dans ma tête, elle ne me paraît pas conduire à un code plus rapide que celui manipulant des tableaux (2,2), et est moins "visuelle" (en ce qui me concerne, sa manipulation mentale est plus difficile que celle de tableaux)
06/11/2007, 10h54
Nemerle

Citation:

Envoyé par mougel

elle ne me paraît pas conduire à un code plus rapide

C'est justement là où je ne suis pas sûr...

autre point: l'algo proposé avec les graphes, à des conditions d'arrêts minimales, exhaustives & indiscutables.

Il est clair que l'algo se basant sur la vision graphe est de loin plus chiant à écrire, là je suis d'accord... et puis don't act, c'est juste une proposition, rien de plus! ;)
06/11/2007, 10h56
Rakken

Une autre idée, potentiellement a creuser.
En partant de mon algo naif, il y a trop de solution a tester. Mais si au lieu de construire simplement les lignes en vérifiant au fur et a mesure que les colones sont bonne, on construit par couple ligne/colone, il est peut être possible d'être plus efficace dans l'élimination des branches. Je m'explique
Les 126 lignes possibles sont également les 126 colones possibles.
Donc premier niveau, on prend les couples ligne/colone l1/c1 qui sont possible (en gros, tout ceux tels que le premier digit de l1 = le premier digit de c1)
Ca va donner une liste de matrice du genre
111110000
1xxxxxxxxx
1xxxxxxxxx
1xxxxxxxxx
1xxxxxxxxx
0xxxxxxxxx
0xxxxxxxxx
0xxxxxxxxx
0xxxxxxxxx
Avec l'intérieur (une matrice 8*8) a completer. (Ca fait moins peur une matrice 8*8 non ? :aie:)
Pour le premier niveau on est déjà passé d'un rang 126*126 (~15000) a un truc du genre 63*63 (les cas avec leur premier digit a 1) + 63*63 (les cas avec leur premier digit a 0). Bref, on a divisé les cas par deux (et sur 10 000 000 000 000 000 000, même si ca suffit pas, ca fait quand même 5 000 000 000 000 000 000 cas a tester en moins ^_^)
Ensuite pour les niveaux suivant, on complete avec les cas qui matchent, du genre
111110000
111110000
1xxxxxxxxx
1xxxxxxxxx
1xxxxxxxxx
0xxxxxxxxx
0xxxxxxxxx
0xxxxxxxxx
0xxxxxxxxx
Mais on s'épargne, pour cette matrice là et pour la seconde ligne, tous les cas ou la seconde ligne commence par un 0. Et chaque niveau est plus discriminant.
Après faut voir s'il est plus interessant de completer une ligne, puis une colone, puis de nouveau une ligne, etc, ou juste les lignes en considérant que les matrices 8*8 sont trouvable.
L'avantage de cette construction est d'avoir des découpages de branches situé a très haut niveau. Par contre, pour les niveaux 2/3/4, j'ai peur que la combinatoire des possibles ne suffise quand même a faire exploser joyeusement le truc.
'fin bref, c'est une autre piste, a voir si elle est viable.
06/11/2007, 11h05
fremen167

Citation:

Envoyé par Rakken

Mais si au lieu de construire simplement les lignes en vérifiant au fur et a mesure que les colones sont bonne, on construit par couple ligne/colone, il est peut être possible d'être plus efficace dans l'élimination des branches.

Oui, c'était ma première suggestion, mais je pense que ce que j'ai proposé depuis est largement plus efficace, même si la question des permutations de solutions génératrices n'est pas encore résolue... efficacement.
06/11/2007, 11h57
mougel

Aide spécialisée ?

Quelqu'un connaît-il des forums calés en théorie des graphes (et en algorithmique associée) ?:aie:
06/11/2007, 12h33
fremen167

Génération des permutations

Bon, je ne sais pas si tu as pu faire tourner mon algo jusqu'au bout, mais je peux te proposer une solution pour la génération des permutations sans doublons à partir des génératrices.

Je pars de l'observation suivante : si 2 lignes (resp. 2 colonnes) sont égales, alors les permutations de colonnes ne changent pas cet état de fait. Bien sûr, c'est la même chose pour les colonnes.

On a dans une génératrice au maximum 9 lignes différentes et 9 colonnes différentes. On les identifie par le numéro de leur premier représentant dans la génératrice. Par exemple, si L2 = L3, les lignes seront représentées par :
1, 2, 2, 4, 5... 9

On fait de même pour les colonnes.

Générer l'ensembles des permutations Lignes / Colonnes possibles revient à générer l'ensemble des arrangements de ces valeurs, pour les lignes et pour les colonnes, et faire le produit cartésien des deux ensembles.

Il est relativement simple de générer les arrangements dans l'ordre lexicographique, et ainsi d'éviter les doublons.

Ensuite, tu n'as plus, pour chaque élément du produit cartésien, qu'à recherche dans la génératrice les valeurs des lignes et des colonnes pour les afficher.

Si Nl1... Nl9 sont le nombre d'occurence de chaque "type de ligne" (regroupant les lignes identiques), et Nc1... Nc9 pour les colonnes, le nombre de permutations est :
(9 !)^2 / Produit (Nl1 !) * Produit (Ncj !), soit (9!)^2 dans le cas sans doublon (tous les Nli et Ncj valent 1).
06/11/2007, 13h51
mougel

Citation:

Envoyé par fremen167

Bon, je ne sais pas si tu as pu faire tourner mon algo jusqu'au bout, mais je peux te proposer une solution pour la génération des permutations sans doublons à partir des génératrices.

Merci beaucoup pour ton aide.
Je n'ai pas encore écrit ton algo (je programme lentement et j'attends un week-end où j'aurai un peu de tps)
Par ailleurs (ce que je ne précisais pas dans l'énoncé) seules les génératrices m'intéressent.
Ainsi, l'identification des doublons ne m'intéresse que si elle permet d'accélérer un balayage exhaustif de toutes les matrices lexico en zappant les doublons.
06/11/2007, 14h13
fremen167

Citation:

Envoyé par mougel

Merci beaucoup pour ton aide.

Ben de rien, ça fait plaisir de faire un peu d'algo :P

Ca faisait un moment... et je serai content si tu me confirmes que ça fonctionne !
07/11/2007, 00h53
Nemerle

Tétu comme un boeuf, je reviens vers les graphes: soit (x,y) les graphes orientés ayant x sommets, dont chaque sommet possède y flèches sortantes et y entrantes...

Un dessin? ;)

http://www.badongo.com/pic/2120635 (petite erreur dans eulh dessin: il faut lire (2,2), pas (2,1)...)

qui me donnera (4,3) et (5,3) ??

pis après, il sera temps d'écrire l'algorithme...
07/11/2007, 22h24
fremen167

Citation:

Envoyé par Nemerle

Tétu comme un boeuf...

Comme je le suis pas mal aussi, et que le formalisme des graphes ne m'aide pas à mieux voir le problème, je préfère poursuivre sur la même voie.

Je viens de me rendre compte que ma règle 3 étendue n'est pas assez étendue :lol:

Nouvelle règle 3 : Le nombre de 1 dans les colonnes 1 à 5 des lignes 3 à 9 ne peut pas être supérieur au nombre de 1 dans les colonnes 1 à 5 de la ligne 2.

Dans le cas contraire, on pourrait permuter la ligne contrevenante avec L2, puis permuter les colonnes pour placer les 1 à gauche, et la nouvelle L2 serait supérieure à la précédente.

Il découle de cette règle que la 4ème et la 5ème possibilité de L2 que j'avais retenues ne sont pas possibles.

Pour la 5ème, on voit que les lignes 6 à 9 ne respectent pas la règle.
Pour la 4ème, il découle de la règle que pour les colonnes 1 à 5, il ne peut pas y avoir + de 6 '1' dans les lignes 3 à 5, et pas plus de 8 dans les lignes 6 à 9, soit un maximum de 21 '1' pour 5 colonnes (alors qu'il en faut 25).

Nous n'avons plus que 3 L2 à explorer...

Je pense que la règle 3 doit être encore enrichie pour garantir que les solutions générées seront bien des génératrices, je vais encore y réfléchir.

:yaisse2: Voila l'algo (sous Excel....) qui se base sur la notion de graphe:

on recherche tous les graphes à 9 sommets ayant chacun 5 flèches sortantes et 5 entrantes. Pour ce faire, on construit les flèches sortantes en comptant les entrantes...

Les sommets sont 0,1,...,8. Sans restriction, les 5 flèches partantes de 0 vont vers 4,5,6,7 et 8. On parse selon l'ordre lexico par sommets croissant.

Les soluces affichées sont de la forme

(4 5 6 7 8 ) (0 2 3 4 5 ) (0 1 3 4 5 ) (0 1 2 4 5 ) (0 1 6 7 8 ) (0 1 6 7 8 ) (1 2 3 7 8 ) (2 3 5 6 8 ) (2 3 4 6 7 )

chaque () repésentant les sommets d'arrivées des flèches pour les sommets 0,1,...,8.

Par exemple, le second () de l'exemple ci-dessus dit que les flèches
issues de 1 vont vers 0,2,3,4,5.

En excel, on teste les 50 000 1ieres possibilités (pour ~2000 soluces trouvées) en 20 secondes (sur mon vieux T41).

A+

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
Private Sub CommandButton1_Click()
Dim inn(8) As Integer       '====== inn(s) = le nb de flèches rentrantes en s
Dim libre As Integer        '====== le nombre de flèches à créer
Dim c(8, 4) As Integer      '====== compteur des candidats par sommets
Dim pc As Integer           '====== pointe le pc'ième sommet en cours de tentative
Dim succes, total As Double
Dim fini, b, bb As Boolean
Dim j, k, l As Integer
fin = False
Dim sol As String
For i = 0 To 8
    inn(i) = 0
Next i
'======= ici, on crée 5 flèches issues de 0 vers 4,5,6,7 et 8
'======= (à équivalence près toutes les solutions commencent par ça)
pc = 1
For i = 0 To 4
    c(0, i) = 4 + i
    inn(4 + i) = 1
Next i
c(1, 0) = 0
For i = 1 To 4
    c(1, i) = 1 + i
Next i
c(1, 4) = 4
libre = 40
succes = 0
total = 0
 
While fini = False
    j = 4
    c(pc, j) = c(pc, j) + 1
    If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
    While (c(pc, 4) > 8 And j > 0)
        j = j - 1
        c(pc, j) = c(pc, j) + 1
        If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
        For k = j + 1 To 4
            c(pc, k) = c(pc, k - 1) + 1
            If c(pc, k) = pc Then c(pc, k) = c(pc, k) + 1
        Next k
    Wend
    If (c(pc, 4) < 9 And (9 - pc) * 5 >= libre) Then
        b = True
        j = 0
        While (b = True And j < 5)
            If inn(c(pc, j)) = 5 Then
                b = False
            Else
                j = j + 1
            End If
        Wend
        bb = True
        j = pc + 1
        While (bb = True And j < 9) '=== si bb passe à false, la soluce ok est en fait ko!
            If (k >= 3 And inn(k) < k - 2) Then
                bb = False
            Else
                j = j + 1
            End If
        Wend
        If (b = True And bb = True) Then '====== succes sur le sommet pc!
            For j = 0 To 4
                inn(c(pc, j)) = inn(c(pc, j)) + 1
                libre = libre - 1
            Next j
            If (pc = 8 Or libre = 0) Then '====== graphe trouvé!!!
                succes = succes + 1
                sol = ""
                For k = 0 To 8
                    sol = sol + " ("
                    For l = 0 To 4
                        sol = sol & c(k, l) & " "
                    Next l
                    sol = sol + ")"
                Next k
                Worksheets("Sheet1").Cells(5 + succes, 2) = sol
                Worksheets("Sheet1").Cells(4, 2) = succes
                For j = 0 To 4 '====== on annule la sélection c(pc,-)
                libre = libre + 1
                inn(c(pc, j)) = inn(c(pc, j)) - 1
                Next j
                c(pc, 4) = c(pc, 4) + 1
                If c(pc, 4) = pc Then c(pc, 4) = c(pc, 4) + 1
            Else
                pc = pc + 1
                For j = 0 To 4
                    c(pc, j) = j 'c(pc - 1, j)
                    If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
                    If j > 0 Then
                        If c(pc, j) <= c(pc, j - 1) Then c(pc, j) = c(pc, j - 1) + 1
                    End If
                Next j
                c(pc, 4) = c(pc, 4) - 1
            End If
        End If
    Else   '======== échec
        total = total + 1
        Worksheets("Sheet1").Cells(6, 2) = total
        pc = pc - 1
        If pc = 0 Then
            fini = True '========= tout est parsé, car c(1,-) = 45679
        Else
            For j = 0 To 4 '====== on annule la sélection c(pc,-)
                libre = libre + 1
                inn(c(pc, j)) = inn(c(pc, j)) - 1
            Next j
            l = 0
            For j = 1 To pc - 2
               If c(j, 4) > l Then l = c(j, 4)
            Next j
            k = 4
            While (c(pc, k) > l And k >= pc)
                k = k - 1
            Wend
            c(pc, k) = c(pc, k) + 1
            If c(pc, k) = pc Then c(pc, k) = c(pc, k) + 1
            For l = k + 1 To 4
                c(pc, l) = c(pc, l - 1) + 1
                If c(pc, l) = pc Then c(pc, l) = c(pc, l) + 1
            Next l
        End If
    End If
Wend
End Sub

09/11/2007, 21h04
fremen167

Bravo ! Mais honnêtement, j'ai du mal à comprendre...

Tu peux ajouter quelques commentaires ?

Par exemple, je ne comprend pas ceci :

Citation:

Code:

Dim c(8, 4) As Integer '====== compteur des candidats par sommets

S'il s'agit d'un comptage, logiquement, on devrait avoir un tableau à 1 dimension :

Code:

Dim c(8) As Integer '====== compteur des candidats par sommets

Non ?
10/11/2007, 01h26
Nemerle

ok, j'ajouterai les commentaires semaine prochaine!
Si c'est bien c(8,4), c'est des compteurs à 5 dimensions:
c(s,0),...,c(s,4) représente les sommets d'arrivée issus de s, et tu "fais tourner" les compteurs de tous les chemins en essayant d'aller de 0 à 8!

inn(s) représente le nombre de chemin rentrant en s. Des que inn(s)=5, le sommet n'est plus accessible!

Par choix, pour s=0 j'ai pris 45678
Ensuite, on passe au sommet s=1, et on teste 02345 (ca marche)
on passe à s=2 et on teste 01345 (ca marche)
et on cherche à arriver à s=8...

Si un essai en s plante, par exemple 23568, on incrémente lexicographiquement la tentative en s: soit 23569, zut! ca ne va pas, le 5ième terme dépasse 8, donc on recule d'un cran: 23578.

Ensuite, il y a quelques endroits d'optimisations naturels on on arrete d'augmenter le compteur pour remonter en s-1.

Exemple: tu es en s=6 (plus que 2 sommets en plus), mais inn(7)=3, alors tu peux t'arrêter... car il n'y a plus que les flèches issues de 7 et 8 pour rajouter les 2 fleches entrantes manquantes en 7, et c'est pas possible (pas de boucle de 7 vers 7)... ;)

Etc... si à un sommet s on teste 45678, il n'y a pas de suivant, on "remonte" en s-1, et on incremente le compteur...
10/11/2007, 01h37
Nemerle

BTW, sur un 1,2 Gh et 512 de RAM, les 65536 lignes de soluces d'excel sont remplies en 3mn, pour ~1M de cas testés... ça serait intéressant de voir l'algo sur une bonne babasse en VRAI langage...

Quelques commentaires en +, comme demandé.

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
Private Sub CommandButton1_Click()
Dim inn(8) As Integer       '====== inn(s) = le nb de flèches rentrantes en s
Dim libre As Integer        '====== le nombre de flèches restantes à créer
Dim c(8, 4) As Integer      '====== compteur des candidats par sommets:
'==== c(s,0)...,c(s,4) donne les flèches s-->c(s,0) ,...,s-->c(s,4) qu'on va tester
'==== on va chercher à construire les flèches en allant du sommet 1 au sommet 8:
'==== si au sommet 8 les candidats c(8,-) sont OK, c'est gagné!!
Dim pc As Integer           '====== pointe le ième sommet en cours de tentative
Dim succes, total As Double
Dim fini, b, bb As Boolean
Dim j, k, l As Integer
fin = False
Dim sol As String
For i = 0 To 8
    inn(i) = 0
Next i
'======= ici, on crée 5 flèches issues de 0 vers 4,5,6,7 et 8
'======= (à équivalence près toutes les solutions commencent par ça)
pc = 1
For i = 0 To 4
    c(0, i) = 4 + i
    inn(4 + i) = 1
Next i
c(1, 0) = 0
For i = 1 To 4
    c(1, i) = 1 + i
Next i
c(1, 4) = 4
libre = 40
succes = 0
total = 0
 
While fini = False
    j = 4
    c(pc, j) = c(pc, j) + 1 '== on incrémente le 5ième sommet
    If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1 '== ici, c'est pour ne pas créer une flèche pc --> pc (ce test est présent tout le long du code)
    While (c(pc, 4) > 8 And j > 0) '=== si le 5ième sommet est >8, on passe au 4ième
'=== et on l'incrémente "lexico" et le 5ième est alors le 4ième+1. Et on redescend tant que.... Au pire, à la fin j=0.
        j = j - 1
        c(pc, j) = c(pc, j) + 1
        If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
        For k = j + 1 To 4
            c(pc, k) = c(pc, k - 1) + 1
            If c(pc, k) = pc Then c(pc, k) = c(pc, k) + 1
        Next k
    Wend
    If (c(pc, 4) < 9 And (9 - pc) * 5 >= libre) Then '==== sinon, c(pc,4)=5,6,7,8,9 où il n'y a plus de place suffisante libre pour crée rles 5 flèches, et ON A FINI avec ce sommet, il faut remonter au précédent
        b = True 
'=== donc ici, les c(pc,-) peuvent être testées pour créer les 5 flèches
        j = 0
        While (b = True And j < 5)
            If inn(c(pc, j)) = 5 Then
 '=== le somment c(pc,j) n'a plus de place pour recevoir une flèche!!
                b = False
            Else
                j = j + 1
            End If
        Wend '=== à la fin b=false si l'une des flèches ne peut pas être construire...
        bb = True
        j = pc + 1
        While (bb = True And j < 9) 
'=== ici, on évalue ce que va donner la construction des 5 flèches: peut-être 
'=== que cela va amener à une position qui ne marchera pas: par exemple,
'=== si au sommet 6 on construit les 5 flèches mais qu'alors inn(7)=3, on
'=== devra ultérieurement construire 2 flèches allant vers 7: impossible, car
'=== les 2 sommets restant à traiter sont 7 et 8, et on ne fait pas de 7 --> 7.
            If (k >= 3 And inn(k) < k - 2) Then
                bb = False
            Else
                j = j + 1
            End If
        Wend
        If (b = True And bb = True) Then
 '====== succes sur le sommet pc! Les flèches sont les pc --> c(pc,-)
            For j = 0 To 4 '=== on MAJ la disponibilité des sommets
                inn(c(pc, j)) = inn(c(pc, j)) + 1
            Next j
            libre = libre - 5 '=== on réduit le nombre de flèches à créer
            If (pc = 8 Or libre = 0) Then '====== graphe trouvé!!!
                succes = succes + 1
                sol = ""
                For k = 0 To 8
                    sol = sol + " ("
                    For l = 0 To 4
                        sol = sol & c(k, l) & " "
                    Next l
                    sol = sol + ")"
                Next k
                Worksheets("Sheet1").Cells(5 + succes, 2) = sol
                Worksheets("Sheet1").Cells(4, 2) = succes
                '====== ici, on annule la sélection c(pc,-) du graphe trouvé, pour remonter
                For j = 0 To 4 
                libre = libre + 1
                inn(c(pc, j)) = inn(c(pc, j)) - 1
                Next j
                c(pc, 4) = c(pc, 4) + 1
                If c(pc, 4) = pc Then c(pc, 4) = c(pc, 4) + 1
            Else
                pc = pc + 1
                For j = 0 To 4
                    c(pc, j) = j 'c(pc - 1, j)
                    If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
                    If j > 0 Then
                        If c(pc, j) <= c(pc, j - 1) Then c(pc, j) = c(pc, j - 1) + 1
                    End If
                Next j
                c(pc, 4) = c(pc, 4) - 1
            End If
        End If
    Else   '======== échec des candidats c(pc,-)
        total = total + 1
        Worksheets("Sheet1").Cells(6, 2) = total
        pc = pc - 1 '==== on remonte au sommet précédent
        If pc = 0 Then
            fini = True '========= tout est parsé, car c(1,-) = 45679
        Else
            For j = 0 To 4 '====== on annule la sélection c(pc,-)
                libre = libre + 1
                inn(c(pc, j)) = inn(c(pc, j)) - 1
            Next j
            l = 0
            For j = 1 To pc - 2
               If c(j, 4) > l Then l = c(j, 4)
            Next j
            k = 4
            While (c(pc, k) > l And k >= pc)
                k = k - 1
            Wend
            c(pc, k) = c(pc, k) + 1
            If c(pc, k) = pc Then c(pc, k) = c(pc, k) + 1
            For l = k + 1 To 4
                c(pc, l) = c(pc, l - 1) + 1
                If c(pc, l) = pc Then c(pc, l) = c(pc, l) + 1
            Next l
        End If
    End If
Wend
End Sub

14/11/2007, 10h51
fremen167

Merci beaucoup !
Je vais lire tout ça attentivement ;)
14/11/2007, 20h00
fremen167

Quelques questions
Nemerle, j'ai quelques questions au sujet de ton code...

Sur le calcul de bb :

Si j'ai bien compris, tu veux vérifier que les arcs sortants restant à générer suffiront à compléter les nombres d'arcs entrants restants.

1) Le test n'est-il pas plutôt :
Code:

1 2 If inn(j) < pc - 2
En effet, on contrôle que 5 - inn(j) (= nombres d'arcs entrants restant à calculer pour le noeud j) > 8 - (pc + 1) (= nombre de noeuds candidats pour générer des arcs sortants).

2) Pourquoi limiter ce test aux j > pc ? En fait, on doit distinguer les j > pc parce que le nombre de candidats est décrémenté de 1 (pour exclure les arcs réflexifs), mais on peut tester tous les noeuds, il me semble.

Sur le traitement effectué après l'échec des candidats c(pc,-) :
- tu commences par calculer le max des c(j,4) pour 0 < j < pc-2
==> 3) pourquoi pas pc - 1 ?
- puis pour pc, tu recherches le plus grand k tel que c(pc,k) > ce max.
==> 4) ne faut-il pas écrire
Code:

1 2 While (c(pc, k) > l And k > 0)
Mais surtout :
5) Pourquoi ce calcul ? Je vois que tu repars de ce c(pc,k) en l'incrémentant, mais j'ai l'impression qu'en faisant cela, tu interdis des solutions possibles. Je suppose que c'est pour éviter les doublons, mais je ne comprend pas comment ça marche :cry:
15/11/2007, 00h35
Nemerle
Citation:
Envoyé par fremen167

Sur le traitement effectué après l'échec des candidats c(pc,-) :
- tu commences par calculer le max des c(j,4) pour 0 < j < pc-2
==> 3) pourquoi pas pc - 1 ?
- puis pour pc, tu recherches le plus grand k tel que c(pc,k) > ce max.
==> 4) ne faut-il pas écrire

Code:

1 2 While (c(pc, k) > l And k > 0)
Sur les points précédents 1 & 2, précise, je ne comprends pas trop tes questions... mais peu-être suis-je fatigué... ;)

concernant l'après échec:

- en pc, ça à foiré;
- on recule donc en pc-1 après avoir mis à jour libre et inn();
- en pc-1, on s'intéresse à ce qu'il y a en 1....pc-2, car "dans le compteur en pc6&, si on a essayé des sommets "nouveaux", c'est plus la peine". Je m'explique:

imagine que pour

pc=1: c(1,-) = 12345
pc=2: c(2,-) = 23456
pc=3: c(3,-)= 23467
pc=4: ECHEC

ICI, en pc=3, on a testé par rapport à pc=1 & 2 un nouveau sommet: 7, qui a donné un échec. Tester en =c=3 le sommet 8 ne sert à rien: car dans cette configuration, les sommets 7 et 8 fournissent les mêmes possibilités....

Dans l'algo, l

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