Bonjour a tous,
Je travail sur un projet de fin d'étude dont il est question d'utiliser des méthodes d'optimisations.
Le projet en question consiste a partitionner une grille de dimensions N X M en grilles de dimensions 3 X 3 dans la mesure du possible.
J'ai réussi a faire l'algorithme mais c'est pas optimal, j'aimerais savoir s'il existe des techniques de partitionnement mathématique relative a ce genre de problèmes pour une meilleure optimisation.
Je vous remercie.
Techniques de partitionnements
13 messages
- Page 1 sur 1
par fatal_error » 11 Aoû 2012, 11:54
salut,
pourrais tu etre plus explicite.
Tu veux dire partitionner une grille comme celle du sudoku? Sauf que t'as pas 9x9 mais NxM?
Tu connais les dimensions de ta grille à l'avance?
N et M sont multiples de 3?
Comment est stockée ta grille, un vecteur de vecteur?
Quel est le but du partitionnement? car on peut tres bien imaginer acceder a la grille 5, et l'acces a la case i,j de cette grille par 5*9+(i-1)*3+j (quelquechose dans le genre)
pourrais tu etre plus explicite.
Tu veux dire partitionner une grille comme celle du sudoku? Sauf que t'as pas 9x9 mais NxM?
Tu connais les dimensions de ta grille à l'avance?
N et M sont multiples de 3?
Comment est stockée ta grille, un vecteur de vecteur?
Quel est le but du partitionnement? car on peut tres bien imaginer acceder a la grille 5, et l'acces a la case i,j de cette grille par 5*9+(i-1)*3+j (quelquechose dans le genre)
la vie est une fête 
par laaziz » 11 Aoû 2012, 12:10
Salut,
La dimension N X M est connue d'avance. c'est pas tout a fait comme sudoku :zen: même si il y a une légère ressemblance .
N et M peuvent être des multiples de 3 !
Au fait il s'agit d'un premier temps de trouver les grilles de dimensions 3 X 3 (9 cases carrées) indépendantes i.e des grilles qui ne partagent aucune case, puis trouver les grilles dépendantes de dimensions 3 X 3 ( qui partages des cases avec les grilles indépendantes).
Le but du partitionnement est de choisir la case au centre comme leader de chaque grille de dimensions 3 X 3 .
La dimension N X M est connue d'avance. c'est pas tout a fait comme sudoku :zen: même si il y a une légère ressemblance .
N et M peuvent être des multiples de 3 !
Au fait il s'agit d'un premier temps de trouver les grilles de dimensions 3 X 3 (9 cases carrées) indépendantes i.e des grilles qui ne partagent aucune case, puis trouver les grilles dépendantes de dimensions 3 X 3 ( qui partages des cases avec les grilles indépendantes).
Le but du partitionnement est de choisir la case au centre comme leader de chaque grille de dimensions 3 X 3 .
par fatal_error » 11 Aoû 2012, 12:53
bah au risque de paraitre bete, est-ce que tu aurais un exemple?
parce que je comprends pas à quoi ressemble ta grille principale, et si tu connais tes sous-grilles ou pas, si tes sous-grilles sont composées de cellules adjacentes ou pas...
parce que je comprends pas à quoi ressemble ta grille principale, et si tu connais tes sous-grilles ou pas, si tes sous-grilles sont composées de cellules adjacentes ou pas...
la vie est une fête
par laaziz » 11 Aoû 2012, 13:01
Prenons un exemple de grille de dimensions 4 X 4 ie une grille composée de 16 cases de même taille pour fixer les idées.
On se fixe une orientation, disons le coin du bas a gauche. On commence a chercher les grilles de dimensions 3 X 3. on en trouve une uniquement. On cherche après des grilles de dimensions 3 X 3 dépendantes de celle trouvé.
J'espère que j'ai été clair.
On se fixe une orientation, disons le coin du bas a gauche. On commence a chercher les grilles de dimensions 3 X 3. on en trouve une uniquement. On cherche après des grilles de dimensions 3 X 3 dépendantes de celle trouvé.
J'espère que j'ai été clair.
par laaziz » 11 Aoû 2012, 13:03
Prenons un exemple de grille de dimensions 4 X 4 ie une grille composée de 16 cases de même taille pour fixer les idées.
On se fixe une orientation, disons le coin du bas a gauche. On commence a chercher les grilles de dimensions 3 X 3. on en trouve une uniquement. On cherche après des grilles de dimensions 3 X 3 dépendantes de celle trouvé.
J'ai trouvé un lien qui contient un exemple de grille, un dessin vaut mieux qu'un beau discours :we:
J'espère que j'ai été clair.
On se fixe une orientation, disons le coin du bas a gauche. On commence a chercher les grilles de dimensions 3 X 3. on en trouve une uniquement. On cherche après des grilles de dimensions 3 X 3 dépendantes de celle trouvé.
J'ai trouvé un lien qui contient un exemple de grille, un dessin vaut mieux qu'un beau discours :we:
J'espère que j'ai été clair.
par laaziz » 11 Aoû 2012, 13:11
oops pardon j'ai oublié le lien, le voici :http://www.confortvisuel.com/media//grille-amsler_1.png
par C.Ret » 11 Aoû 2012, 14:23
C'est une grille de calibration très courament utilisée en microscopie !
En plus, c'est un mauvais exemple, cette grille est carrée (NxN) et de ce fait ne ressemble donc pas aux grilles NxM de ton projet.
Ce que je n'ai pas compris c'est comment on doit partitionner avec des sous-grille de 3x3 !
Quelles sont les éventuelles contraintes ?
Que faut-il optimiser ?
En effet, faut-il optimiser le taux de recouvrement, minimiser un nombre de cellules particulières, ... ???
En plus, c'est un mauvais exemple, cette grille est carrée (NxN) et de ce fait ne ressemble donc pas aux grilles NxM de ton projet.
Ce que je n'ai pas compris c'est comment on doit partitionner avec des sous-grille de 3x3 !
Quelles sont les éventuelles contraintes ?
Que faut-il optimiser ?
En effet, faut-il optimiser le taux de recouvrement, minimiser un nombre de cellules particulières, ... ???
par laaziz » 11 Aoû 2012, 14:55
L'exemple de la grille que j'ai posté est juste pour éclairer fatal_error :).
Au fait quelque soit les dimensions N et M ( (N>3 et N-k) ou M>3 et M-k )) peuvent être des multiples de 3 :)) donc dans N X M il existe des sous grilles de dimensions 3 X 3.
Les contraintes sont:
- Les grilles 3 X 3 formées ne doivent pas partagées des cellules entres elles.(grilles indépendantes )
Il faudra optimiser le taux du recouvrement et minimiser les cellules partagées entres les sous grilles 3 X 3 indépendantes et les sous grilles 3 X 3 qu'on peut former aussi.
Au fait quelque soit les dimensions N et M ( (N>3 et N-k) ou M>3 et M-k )) peuvent être des multiples de 3 :)) donc dans N X M il existe des sous grilles de dimensions 3 X 3.
Les contraintes sont:
- Les grilles 3 X 3 formées ne doivent pas partagées des cellules entres elles.(grilles indépendantes )
Il faudra optimiser le taux du recouvrement et minimiser les cellules partagées entres les sous grilles 3 X 3 indépendantes et les sous grilles 3 X 3 qu'on peut former aussi.
par C.Ret » 11 Aoû 2012, 15:50
Bon, voyons si j'ai compris:
Etape 1°) Je prend une grille de NxM cellules (ici de 10x7 )
Etape 2°) Je dispose de grilles de 3x3 sur cette première grille :
Etape 3°) J'optimise le taux de recouvrement et à limiter le taux de cellules partagées entre deux sous-grilles.
L'optimisation du taux de recouvrement; je n'y peux rien la forme de ma grille initiale impose le nombre de sous-grilles et donc le taux de recouvrement.
Mais j'imagine qu'il ne faut pas laisser de cellules non-couvertes !
Il me reste donc à placer les 6 sous-grilles de façon à limiter le nombre de cellules partagées entre deux (ou plus) sous-grilles. Tout en veillant à ne pas les découvrir !
Ca va la ? :zen:
Etape 1°) Je prend une grille de NxM cellules (ici de 10x7 )
Etape 2°) Je dispose de grilles de 3x3 sur cette première grille :
Etape 3°) J'optimise le taux de recouvrement et à limiter le taux de cellules partagées entre deux sous-grilles.
L'optimisation du taux de recouvrement; je n'y peux rien la forme de ma grille initiale impose le nombre de sous-grilles et donc le taux de recouvrement.
Mais j'imagine qu'il ne faut pas laisser de cellules non-couvertes !
Il me reste donc à placer les 6 sous-grilles de façon à limiter le nombre de cellules partagées entre deux (ou plus) sous-grilles. Tout en veillant à ne pas les découvrir !
Ca va la ? :zen:
par fatal_error » 11 Aoû 2012, 16:13
salut, je pense avoir compris.
En fait, N et M sont quelconques et non forcément multiples de 3. (sinon le probleme est trivial).
C'est plus quelquechose comme
N=4 et M=3.
On peut recouvrir avec deux grilles. une définie par la diago (0,0), (2,2) et l'autre définie par la diago (1,1) (3,3)
avec les lignes 1 et 2 qui se recouvrent.
De manière général, puisqu'on autorise le recouvrement de cellules, j'imagine qu'il faut recouvrir la grille entièrement en minimisant le nombre de grillent qui se superposent.
sinon une recherche hative sur google m'a mené avec le 2D packing
si je suis ce que je pense avoir compris, j'aurais tendance à compacter tous les carrés puisque pour une hauteur donnée, on pourra pas mettre plus de carrés quelque soit l'arrangement.
edit2: en lisant C.ret si les sous grilles sont rectangulaires c'est un peu plus complexe :zen:
En fait, N et M sont quelconques et non forcément multiples de 3. (sinon le probleme est trivial).
C'est plus quelquechose comme
N=4 et M=3.
On peut recouvrir avec deux grilles. une définie par la diago (0,0), (2,2) et l'autre définie par la diago (1,1) (3,3)
avec les lignes 1 et 2 qui se recouvrent.
De manière général, puisqu'on autorise le recouvrement de cellules, j'imagine qu'il faut recouvrir la grille entièrement en minimisant le nombre de grillent qui se superposent.
sinon une recherche hative sur google m'a mené avec le 2D packing
si je suis ce que je pense avoir compris, j'aurais tendance à compacter tous les carrés puisque pour une hauteur donnée, on pourra pas mettre plus de carrés quelque soit l'arrangement.
edit2: en lisant C.ret si les sous grilles sont rectangulaires c'est un peu plus complexe :zen:
la vie est une fête
par Dlzlogic » 11 Aoû 2012, 17:21
Bonjour,
J'ai pas vraiment compris le problème.
Soit, c'est un problème théorique pour lequel l'optimisation est le seul but, alors optimisation par rapport à quoi ?
Soit l'optimisation est dans l'utilisation. Et cela me fait peser à l'étude de rasters.
Dans ce dernier cas, un tableau de 3x3 me parait petit. Pour ce genre de chose je dois avoir, de mémoire, 5x5 et 9x9.
Pour moi, l'optimisation la plus simple consisterait à faire un tableau à 3.ou 4 dimensions, mais optimisation de stockage, on peut pas faire mieux que NxM, sauf s'ils sont très grands, et encore, ça dépend du langage, optimisation d'utilisation, alors il manque des infos.
J'ai pas vraiment compris le problème.
Soit, c'est un problème théorique pour lequel l'optimisation est le seul but, alors optimisation par rapport à quoi ?
Soit l'optimisation est dans l'utilisation. Et cela me fait peser à l'étude de rasters.
Dans ce dernier cas, un tableau de 3x3 me parait petit. Pour ce genre de chose je dois avoir, de mémoire, 5x5 et 9x9.
Pour moi, l'optimisation la plus simple consisterait à faire un tableau à 3.ou 4 dimensions, mais optimisation de stockage, on peut pas faire mieux que NxM, sauf s'ils sont très grands, et encore, ça dépend du langage, optimisation d'utilisation, alors il manque des infos.
par laaziz » 11 Aoû 2012, 19:16
C.Ret : C'est exactement ça.Tu as tout compris.
Je vous remercie les gars pour vos précieuses analyses et votre bon sens sans vous je n'aurais pas avancé dans mon projet.
Au fait pour répondre rapidement a Dlzlogic, les dimensions des grilles a construire peuvent très bien être supérieurs a 3 X 3 et c'est là que ça devient intéressant dans la mesure où il faudra trouver les configurations i.e les grilles de dimensions a X b de telle sorte que les grilles qu'on va placer leurs centre soient le plus proches possible des une des autres! au fait c'est une modélisation 2-SAT ( problème de satisfaction de contraintes !!!!) dont il s'agira de recouvrir le maximum de cellules, minimiser la distance entre le centre de chaque configuration.
Merci encore.
Je vous remercie les gars pour vos précieuses analyses et votre bon sens sans vous je n'aurais pas avancé dans mon projet.
Au fait pour répondre rapidement a Dlzlogic, les dimensions des grilles a construire peuvent très bien être supérieurs a 3 X 3 et c'est là que ça devient intéressant dans la mesure où il faudra trouver les configurations i.e les grilles de dimensions a X b de telle sorte que les grilles qu'on va placer leurs centre soient le plus proches possible des une des autres! au fait c'est une modélisation 2-SAT ( problème de satisfaction de contraintes !!!!) dont il s'agira de recouvrir le maximum de cellules, minimiser la distance entre le centre de chaque configuration.
Merci encore.
13 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 57 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :