Discussion :

[Nemerle]

Allez, j'ai un tableau que je représente ici comme une partie X de N^n. J'aimerais trouver la plus petite "partition" P1,P2...,Pm de X, au sens où

1. Chaque Pi est produit d'ensembles de N: P=A1xA2x...xAn (les Aj variant pour chaque Pi)
2. X est réunion disjointe des Pi.

What is le meilleur algo?

[pseudocode]

1. Chaque Pi est produit d'ensembles de N: P=A1xA2x...xAn (les Aj variant pour chaque Pi)

Je n'ai pas bien compris le probleme. C'est quoi les Ai, des elements de N ? Et la notation A1 x A2, c'est la multiplication ?

Hum... ca ne doit pas etre ca, car dans ce cas je ne vois pas de "contrainte" pour le partitionement.

[Nemerle]

Je n'ai pas bien compris le probleme. C'est quoi les Ai, des elements de N ? Et la notation A1 x A2, c'est la multiplication ?

Les Ai sont des sous-ensembles de N. A1xA2 est le produit cartésien.

Plus simplement, par exemple P1 = {1,2,4}x{2,3}x{5,7}. L'élément (2,3,7) par exemple appartient à P1.

[pseudocode]

Je me disais aussi que c'était trop facile.

Hum... ça m'a tout l'air d'un problème de MCSC (Minimum Consistent Subset Cover).

Bon, alors on a toujours l'approche Greedy qui est simple mais qui ne donne pas forcement la solution optimale, a moins de faire une exploration exhaustive (et d'acheter un Cray).

Sinon, il y a les algorithmes CAG (Clustered AGgregation) qui semblent être des bon candidats pour les problèmes de MCSC. Il faut voir ce qu'en pense mon ami google, avec les mots clés MCSC et CAG.

[Nemerle]

Je me disais aussi que c'était trop facile.

Hum... ça m'a tout l'air d'un problème de MCSC (Minimum Consistent Subset Cover).

.

Oui, c''est bien cela pseudocode. Le problème est que ma contrainte n'est pas consistante, ni même "pivot"-consistante. MCSC et CAG ne s'appliquent donc pas.

Ici, il faut donc essayer de faire "au mieux".... la taille du tableau n'est pas trop grande, maximum 10 colonnes pour 200-300 lignes.

L'objectif est en fait de présenter dans une IHM des paramètres administrateurs par "paquets". Exemple:

Filiale Département Profil_User droits

L'objectif est d'obtenir par exemple

{f1,f3,f5}-{d2,d4}-{p3,p5,p6}-{droit1,droit3,droit5} indiquant que toutes les combinaisons possibles par "produit" sont ok (par exemple (f3,d4,p5,droit3)).


Donc ce que je cherche ici, c'est de comparer des idées afin de "maîtriser" autant que faire se peut les temps de calcul...

Je donnerais ma vision demain ou après-demain.

[Nemerle]

Bon, on a X dans N^n, notons (x1,...,xn) les composantes de tout x dans X.

1. Disons que pour deux éléments distincts x,y de X, x~y si toutes les composantes de x et y sont égales SAUF une.

2. On considère le graphe (non orienté) de sommets les x de X; un arrête relie x et y ssi x~y.

3. On fait alors une recherche heuristique en regardant les cycles du graphe.....

Qu'en pensez-vous?


Un exemple:

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
x	x1	x2	x3	x4
1	1	4	7	9
2	1	4	8	9
3	1	5	7	9
4	1	5	8	9
5	1	6	7	9
6	1	6	8	9
7	2	4	7	9
8	2	4	8	9
9	2	5	7	9
10	2	5	8	9
11	2	6	7	9
12	2	6	8	9
13	3	4	7	9
14	3	4	8	9
15	3	5	7	9
16	3	5	8	9
17	3	6	7	9
18	3	6	8	9

Le cycle 1->13->17->18->16->14->8->2->6->4->10->12->11->5->3->15->9->7->1
montre que X={1,2,3}x{4,5,6}x{7,8}x{9}.

[pseudocode]

Ca me parrait bien. C'est un algo Greedy, avec une exploration exhaustive (enfin il me semble que c'est exhaustif ) . Comment tu geres les eventuels croisements entre 2 cycles ?

Edit: rien a voir avec l'algorithmie, mais en tant qu'admin systeme, je me demande si c'est pas mieux de présenter les cas generaux + les exceptions, plutot que de montrer tous les cas disjoints... Mais bon, c'est personnel.

[FrancisSourd]

Petite remarque qui n'aide sans doute pas vraiment pour la résolution...

Lorsque n=2, c'est équivalent à faire un décomposition d'un graphe biparti en bicliques. C'est déjà NP-complet.
http://dx.doi.org/10.1016/S0166-218X(98)00039-0

Le graphe biparti est construit entre N et N. On met une arête (x1,x2) pour tout élément de X.

Le cycle 1->13->17->18->16->14->8->2->6->4->10->12->11->5->3->15->9->7->1
montre que X={1,2,3}x{4,5,6}x{7,8}x{9}.

Il me semble que ceci n'est vrai que parce que le cycle contient 18 éléments distincts comme X. J'ai l'impression que tout cycle ne donne pas lieu à quelque chose qu'on peut écrire comme un produit cartésien.

[Nemerle]

Il me semble que ceci n'est vrai que parce que le cycle contient 18 éléments distincts comme X. J'ai l'impression que tout cycle ne donne pas lieu à quelque chose qu'on peut écrire comme un produit cartésien.

Bien sûr. Il faut tester le cycle, mais c'est facile: tu construis les ensembles P1,P2... et si le produit de leurs cardinaux vaut le nombre de noeuds du cycle, c'est gagné. Lors de cette construction, un "morceau" du cycle peut aussi suffire si le cycle complet est ko.

J'ai l'intuition qu'il ne faut pas systématiquement commencer par les cycles hamiltoniens: la clé de base est vraiment cette notion de x~y --> plus le cycle est long, plus effectivement tu peux obtenir un gros Pi, mais plus la probabilité de succès diminue... c'est pour cela que je veux laisser faire le hasard... avec condition de succès (dès que le Pi a une taille sympa, on passe au graphe résiduel).

Pseudocode:
> a priori je me tape des croisements de cycle (en excluant toutefois les loops "infinis"). Mais je verrai ça à l'usage...
>> l'algo recherché sera utilisé pour d'autres trucs que la MAJ de paramètres Admin... mais c'est bien de le signaler.

[FrancisSourd]

Personnellement je travaillerais par agrégations comme le suggérait pseudocode.

Au départ, on considère les éléments de X, c'est facile deux éléments qui peuvent être assemblés (il ne différent que par une coordonnées).

À une étape de l'algo, on a donc un certain nombre de produits cartésiens
(P^i_1 x ..... x P^i_n)

Pour deux produits cartésiens d'indices i et j, il est facile de voir si l'on peut fusionner (P^i_1 x ..... x P^i_n) et (P^j_1 x ..... x P^j_n). Il suffit de regarder les produits cartésiens inclus dans Y=(P^i_1 U P^i_1) x ..... x (P^i_n U P^j_n): si on réussit à couvrir Y, on agrège tous les produits cartésiens en Y.

[Nemerle]

Personnellement, je pense qu'un tel algo de type CAG sera... trop gourmand en temps de calcul.

J'espère ici simplement qu'une heuristique (hasard sur les loops + conditions de satisfactions) sera plus... performante dans la plupart des cas.

Je vous tiendrai au courant d'ici quelques semaines (quand les gentils geeks que j'ai enchainé à leurs bureaux auront le temps de passer à ce problème ).


Pas d'autres idées???

[FrancisSourd]

Au fait, quel est (ordre de grandeur) la taille de X et la dimension n?
Et le temps de calcul autorisé?

[Nemerle]

2 cas:

des tables de 5-6 colonnes, 200 lignes

des tables de 10 colonnes, 10000 lignes.

Temps de calcul autorisé? A voir...