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

05/11/2007, 16h13
pseudocode

Citation:

Envoyé par pseudocode

C'est moi ou je trouve que le probleme d'origine est nettement plus simple que celui du PO... :roll:

bon, s'il n'y a que moi qui trouve (5!)^8 c'est que j'ai du me gourer.
05/11/2007, 16h28
mougel

Edit:

Citation:

Envoyé par pseudocode

C'est moi ou je trouve que le probleme d'origine est nettement plus simple que celui du PO... :roll:

En ligne, les 9 groupes d'enfants.
En colonne les 9 numéros de familles
Chaque enfant est représenté par un 1 à l'intersection de la ligne correspondant à son groupe, et de la colonne correspondant à sa famille.

Comment trouves-tu 5!^8?

Sinon, le texte de Mc Kay donne le nombre des matrices recherchées.
Mais ce que je cherche, c'est de les inventorier. Je pense qu'il n'y a que quelques milliers (intuition gratuite)
05/11/2007, 16h36
mougel

Citation:

Envoyé par Rakken

Alors je ne garanti pas que ce soit l'algo le plus rapide pour trouver toutes les solutions mais je crois que ca peut le faire quand même.

C'est bien ce que je cherche: un algorithme suffisamment bourrin pour être facilement sûr qu'il ne comporte pas d'erreur.

Malheureusement, il me semble qu'un tel algo prend des siècles à s'exécuter.

Alors il faut effectivement faire des découpes de branches inutiles (correspondant à des matrices non valides, ou permutées de matrices déjà vues)
Mais la découpe doit être méthodique et intelligente: Voilà plusieurs fois que je détecte dans ma recherche une grosse erreur qui m'a fait découper par erreur telle ou telle branche, ou laisser telle ou telle branche inutile.

Ce que je cherche ici, c'est l'idée géniale qui apporterait méthode, clarté et efficacité. On a bien le droit de rêver, non?
05/11/2007, 16h40
mougel

Citation:

Envoyé par Nemerle

c'est un système de générateurs que tu cherches, mais ce que tu dis ne présage rien de bon: soit Chang a exhibé un exemple, soit il donne des générateurs pour un certain type de problème, et là c'est mieux...

Ce que Chang a montré, c'est que la notion de spectre ne correspond pas à la notion d'isomorphisme, en exhibant un exemple de matrices "isospectres" mais pas isomorphes.
On ne peut donc utiliser le spectre d'une matrice pour déterminer si oui ou non elles sont isomorphes.
On peut affirmer que si deux matrices n'ont pas le même spectre, elles ne sont pas isomorphes, mais on ne peut pas affirmer la réciproque
05/11/2007, 17h00
Nemerle

Citation:

Envoyé par Rakken

Et l'algorithme naif ?
Soit, a vue de nez 512 solutions. Parmis celle là, on récupere seulement les solutions qui ont leur somme à 5, une boucle et une addition et le tour est joué.

....

Y en a 126, et donc ton algo "naif" doit parser 126^9 cas, soit ~ 10^19= 10 000 000 000 000 000 000 cas.

T'as un réseau de Cray? ;)
05/11/2007, 17h04
pseudocode

Citation:

Envoyé par mougel

Comment trouves-tu 5!^8?

Bah tout simplement (5!)^9 / 5!

(5!)^9 = nombre de configurations valides (avec doublons)
5! = nombre de permutations dans un groupe de 5 elements
05/11/2007, 19h43
mougel

Citation:

Envoyé par pseudocode

Bah tout simplement (5!)^9 / 5!

(5!)^9 = nombre de configurations valides (avec doublons)
5! = nombre de permutations dans un groupe de 5 elements

Selon cette approche, ce ne serait pas plutôt la formule suivante:
[C(9,5)^9]/9!
c'est-à-dire le nombre de combinaisons de 9 objets pris 5 à 5, à la puissance 9 (= nombre de lignes) divisé par 9! (pour éliminer les permutations des lignes)
C'est peut-être une formule approchante, mais qui compte plusieurs fois chaque matrice
05/11/2007, 20h00
pseudocode

Citation:

Envoyé par mougel

Selon cette approche, ce ne serait pas plutôt la formule suivante:
[C(9,5)^9]/9!
c'est-à-dire le nombre de combinaisons de 9 objets pris 5 à 5, à la puissance 9 (= nombre de lignes) divisé par 9! (pour éliminer les permutations des lignes)
C'est peut-être une formule approchante, mais qui compte plusieurs fois chaque matrice

Non. Ce ne sont pas des combinaisons.

Un regroupement valide est un ensemble composé de 5 groupes de 9 enfants (avec les contraintes qu'on connait).

1er groupe: G1=(x1,x2,x3,...,x9), avec x1 dans la famille 1 (5 choix), x2 dans la famille 2 (5 choix), ... -> 5^9

2eme groupe: G2=(x1,x2,x3,...,x9), avec x1 dans la famille 1 (reste 4 choix), x2 dans la famille 2 (reste 4 choix), ... -> 4^9

...

5eme groupe: G5=(x1,x2,x3,...,x9), avec x1 dans la famille 1 (reste 1 choix), x2 dans la famille 2 (reste 1 choix), ... -> 1^9

=> total des groupes possibles = 5^9 * 4^9 * 3^9 * 2^9 * 1^9 = (5!)^9

Edit: on peut voir ca egalement comme le produit cartesien de toutes les permutations de groupes a 5 elements => 5! * 5! * ... * 5! = (5!)^9
05/11/2007, 21h23
Zavonen

Citation:

Y en a 126, et donc ton algo "naif" doit parser 126^9 cas, soit ~ 10^19= 10 000 000 000 000 000 000 cas.

Peut être pas tant que ça quand même.
On a vu qu'on peut supposer les lignes rangées dans l'ordre lexicographique croissant.
Ainsi je trouve pour les 4 premières lignes 'seulement' C126,4 et non 126^4. Bon, c'est du même odre de grandeur mais quand même, les contraintes commencent dès la cinquième ligne, donc ce n'est certainement pas un facteur 126 qui va intervenir, d'autant plus qu'on ne considère à chaque fois que les candidats 'supérieurs' à la quatrième ligne, et plus on avance et plus le poids des contraintes va être fort.
Il n'est peut être pas totalement illusoire d'essayer de 'passer en force', mais ça doit être très chaud quand même.
Passer l'étape de la cinquière ligne me paraît possible, j'en suis même sûr, c'est les étapes 6 et 7 qui doivent poser problème.
J'ai commencé à faire quelques essais.
Je stocke les 126 possibilités dans un tableau, et comme 'ô miracle' 126 tient sur un octet, on peut remplacer une ligne par son indice sur un octet, donc une matrice entière tient sur 9 octets et non 324 correspondant à 81 int.
Néammoins je bloque toujours sur le calcul de la ligne 6....
05/11/2007, 21h32
mougel

Citation:

Envoyé par pseudocode

Non. Ce ne sont pas des combinaisons.

Un regroupement valide est un ensemble composé de 5 groupes de 9 enfants (avec les contraintes qu'on connait).

L'énoncé n'est peut-être pas clair, mais il s'agit en fait de 9 groupes de 5 enfants, et non l'inverse.
Ce qui complique effectivement le pb.
05/11/2007, 21h49
fremen167

Citation:

Envoyé par Zavonen

Peut être pas tant que ça quand même.
On a vu qu'on peut supposer les lignes rangées dans l'ordre lexicographique croissant.
Ainsi je trouve pour les 4 premières lignes 'seulement' C126,4 et non 126^4.

Attention Zanoven, on n'a pas démontré que deux lignes doivent nécessairement être différentes !

En poussant un peu l'analyse, on peut réduire un peu plus le nombre de cas à explorer, mais je n'ai pas encore fini. Voici quand-même où j'en suis - je crois que c'est déjà mieux.

NB. : comme je vois mieux avec les '1' en premier, je travaille en ordre décroissant.

Je ne cherche pour le moment qu'à générer les solutions "génératrices", c'est à dire le plus grand élément de chaque classe de solution équivalentes par permutations.

Règle 1) L1 = 111110000 forcément. En effet, il suffit de trier les colonne de n'importe solution pour regrouper les 1 au début de la 1ère ligne.

Règle 2) C1 = 111110000 ! Et oui, on peut encore trier les 8 dernières lignes pour regrouper les 5 '1' en haut (et d'ailleurs, on doit le faire puisqu'on veut la génératrice de la classe).

Déjà, avec ces deux petits résultats, on ne cherche "plus que" parmi C 4 8 = 70 lignes maximum pour les 4 du haut, et 56 pour celles du bas (et en oubliant pas que les lignes sont triées, on est largement en dessous de 70^4 * 56^4).

Règle 3) L'élément (2, 2) de la matrice est forcément '1'. Si on prend l'hypothèse inverse, alors on n'a que des '0' dans le colonne 2 à 5 des lignes 2 à 5. En effet, si un autre '1' était présent, on pourrait le ramener en (2, 2) par permutation de ces 4 lignes et 4 colonnes (qui ne modifient pas les règles 1 et 2).

Bon, ben je continue encore un peu :P
05/11/2007, 21h57
fremen167

Citation:

Envoyé par fremen167

Règle 3) L'élément (2, 2) de la matrice est forcément '1'. Si on prend l'hypothèse inverse, alors on n'a que des '0' dans le colonne 2 à 5 des lignes 2 à 5. En effet, si un autre '1' était présent, on pourrait le ramener en (2, 2) par permutation de ces 4 lignes et 4 colonnes (qui ne modifient pas les règles 1 et 2).

Oups ! Je suis allé un peu vite sur la règle 3. En fait, il y a une solution (unique) avec 0 en (2, 2) :

111110000
100001111
100001111
100001111
100001111
011111000
011110100
011110010
011110001

Donc : règle 3 bis, soit (2, 2) = 0 et on a la solution ci-dessus, soit (2, 2) = 1 :roll:
05/11/2007, 21h58
pseudocode

Citation:

Envoyé par mougel

L'énoncé n'est peut-être pas clair, mais il s'agit en fait de 9 groupes de 5 enfants, et non l'inverse.
Ce qui complique effectivement le pb.

ah oui... effectivement c'est tout de suite plus compliqué. :aie:

il va falloir un peu de programmation dynamique pour trouver le nombre de regroupements possibles.
05/11/2007, 22h19
Nemerle

Citation:

Envoyé par Zavonen

Peut être pas tant que ça quand même.
On a vu qu'on peut supposer les lignes rangées dans l'ordre lexicographique croissant...

Bien sûr, j'énonçais juste la méthode "bourrine". .Il est clair que de nombreux cas sont "impossibles", au sens où l'algo s'arrête avant la 9ième ligne.

on peut chercher la logique qui permet de programmer "plus vite", mais aux vues des articles de recherches, le problème semble hardu. pas infaisable, juste hardu.

Mais le nbre de cas est effectivement important: il suffit juste de voir le problème comme un graphe orienté à 9 sommets où chacun des sommets à 5 flèches entrantes... et 5 sortantes. On imagine bien le nombre de cas.
05/11/2007, 22h46
fremen167

Je vois encore une amélioration à apporter (c'est une généralisation de ma "règle 3").

Règle 3 étendue ) Les colonnes 2 à 5 des lignes 3 à 5 ne comptent pas plus de '1' que les mêmes colonnes de la ligne 2. Sinon, on pourrait en permutant ces lignes et colonnes obtenir 1 ligne > L2.

Cela fait une contrainte supplémentaire qui permet de couper des branches.

Par ailleurs, on peut réduire fortement le nombre de L2 à traiter.

Règle 4 ) La ligne 2 a la structure suivante :
1 / i fois (1) / (5- i) fois 0 / (4 -i) fois 1 / i fois 0

Il suffit de voir que les 4 dernières colonnes ont autant de 1 que nécessaire pour compléter, et qu'on peut les trier pour mettre les 1 en premier (toujours pour assurer l'ordre lexicographique le caractère "générateur" de la solution).

Cette dernière règle permet de ne tester que les L2 suivantes :

111110000
111101000
111001100
110001110
100001111 (déjà vu - solution unique - la plus petite de notre ensemble de solutions).

Ceci dit, il reste encore pas mal de cas à traiter, et en plus, si tu veux générer toutes les permutations sans doublons de ces matrices, là ça fait vraiment beaucoup, et il n'est pas simple de détecter les doublons :aie:
05/11/2007, 23h00
Rakken

J'ai tenté de commencer un codage en force brute, mais au vu des premiers résultats, a moins d'avoir *beaucoup* de découpage de branches, et des découpages très discriminant (genre dans les tous premiers niveaux de l'arbre de solution), c'est effectivement difficilement envisageable (a moins d'avoir quelques années a perdre :aie:)

Par contre si quelqu'un trouve un algo qui le fait en un temps raisonnable (genre moins d'une journée de calcul ^^), qu'il n'hésite pas a poster l'algo surtout ;-)
05/11/2007, 23h02
mougel

précision

Citation:

Envoyé par fremen167

Ceci dit, il reste encore pas mal de cas à traiter, et en plus, si tu veux générer toutes les permutations sans doublons de ces matrices, là ça fait vraiment beaucoup, et il n'est pas simple de détecter les doublons :aie:

Peut-être, mais comme le dit Zavonen:

Citation:

Envoyé par Zavonen

plus on avance et plus le poids des contraintes va être fort.
Il n'est peut être pas totalement illusoire d'essayer de 'passer en force', mais ça doit être très chaud quand même.

Là où l'algo doit être béton, c'est en particulier dans sa capacité à détecter les doublons.
Pour ma part, et pour prendre le même ordre d'inventaire que fremen167 (descendant), je teste les 8! permutations possibles des colonnes 2 à 9 sur chaque matrice examinée. Si l'une de ces permutations conduit à une matrice lexicographiquement supérieure à la matrice examinée, j'abandonne celle-ci. En effet, cela signifierait qu'elle fait doublon avec une matrice déjà vue.
05/11/2007, 23h10
fremen167

Est-ce que parmi ceux qui ont essayé de code l'algo, quelqu'un a implémenté mes règles (et est-ce que vous êtes d'accord avec) ?

J'avoue qu'il me semble compliqué de calculer combien de branches sont coupées, mais j'ai l'impression que ça réduit pas mal, non ?

Proposition d'algo simple

Voici en pseudo Pascal l'implémentation des règles que je propose.

Le traitement utilise les données suivantes (variables globales):

Code:

1
2
3
4
5
 
 
matrice (1:9; 1:9) : 1 matrice 9 * * pour stocker l'état du tableau
modele (1:126 ; 1;9) : 1 tableau des lignes "modèles" (les 126)
L2 : 1 tableau des indices des 5 lignes L2 possibles

Le code des principaux traitements est le suivant :

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
 
Procedure Explorer (num-ligne, num-modele : int) ;
Var num-deb, num-fin : integer ;
Begin
If Controle-contraintes(num-ligne)
Then
   If num-ligne = 9
   Then afficher
   Else
      {Règle 2}
      IF num-ligne > 5
      Then num-deb = max (71, num-modele)
      Else num-deb = num-modele
      End-if
 
      If num-deb < 71
      Then num-fin = 70
      Else num-fin = 126
      End-if
 
      FOR 1 := num-deb to num-fin DO
      Begin
         {Ajout de la ligne i de modèle en ligne (num-ligne + 1) de la matrice
          On incrémente aussi les totaux de colonnes}
         Ajouter (num-ligne + 1, i) ;
         Explorer (num-ligne + 1, i) ;
         {Retrait de la ligne (num-ligne + 1) de la matrice (il s'agit de décrémenter les totaux par colonne)}
         Retirer (num-ligne + 1) ;
      End
   End-if
{Si controle-contraintes retourne faux, inutile d'aller + loin dans cette branche}
End ;
 
Function Controle-contrainte (num-ligne : integer) : boolean ;
Var lig, col, Cumul-ligne : integer ;
    res : boolean ;
Begin
Res := true ;
Cumul-ligne := Matrice(num-ligne,2) + Matrice (num-ligne,3) + Matrice(num-ligne,4) + Matrice (num-ligne,5)
 
{Règle 3 étendue}
If Cumul-ligne > Cumul-L2
Then res := false
Else
   {Boucle de contrôle des cumuls de colonnes}
End-if ;
 
Controle-contrainte := Res ;
End ; {de controle-contrainte}
 
 
Main ;
 
Begin
 
{Génération des 126 modèles de lignes dans l'ordre lexicographique descendant -
 Stocke également dans L2(1:5) les indices des 5 lignes 2 possibles - cf Règle 4}
Generer-modeles ;
 
{Règle 1}
Ajouter (1, 1) ;
 
{Règle 4}
For i := 1 to 5
   Begin
   Ajouter (2, L2(i)) ;
   cumul-L2 = Matrice(2,2) + Matrice (2,3) + Matrice(2,4) + Matrice (2,5)
   Explorer (2, L2(i)) ;
   Retirer (2) ;
   End ;
End.

On peut remplacer Afficher par la gestion des permutations d'une matrice génératrice (évidemment, là, on dégrade fortement les perfs, et pour les maintenir il faudrait peut-être arriver à générer ces permutations dans l'ordre lexicographique, mais je ne vois pas comment de prime abord :?).

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

06/11/2007, 00h48
Zavonen

Citation:

Attention Zanoven, on n'a pas démontré que deux lignes doivent nécessairement être différentes !

Oups !!!:oops:
Mais je n'ai pas fait l'erreur dans mon code

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