Discussion :

[nathieb]

Bonjour,

J'ai un ensemble d'éléments A, B, C, D ....
chaque éléments est soumis à une ou plusieurs conditions

A ne peut être à côté de B
B ne peut être à côté de J et H
etc


la solution doit être disposée sur une carte dont les dimensions sont n*n
Il peut y avoir plusieurs A ou B ou C ...

Je cherche des pistes de réflexion sur le sujet, des bases Arbres de décision, etc ...

Avez-vous des pistes que je pourrais exploiter ?

Olivier

[AbsoluteLogic]

Bonjour,
En données du problème, tu as le nombre de chaque élément que tu veux placer ?
En réponse au problème, tu veux une répartition quelconque des éléments ? L'ensemble des possibilités ?
On considère que ces contraintes sont sous forme d'un graphe ?

[nathieb]

Bonjour,


Oui normalement j'ai le nombre d'éléments de départ et le nombre de cases prévues.
Effectivement, j'ai pensé à un arbre pour les contraintes, il existe les algos
de programmation par contraintes.

Est ce que cela peut correspondre ?

Olivier

[tbc92]

Prenons un exemple précis, ça permettra de mieux dialoguer.
On a une grille 10x10,
A : 25 éléments, ne peut pas être à côté de B C E ni H
B : 18 éléments, ne peut pas être à côté de D F ni J
C : 12 éléments, ne peut pas être à coté de E ni F
D : 10 éléments, ne peut pas être à coté de E F ni G
E : 8 éléments, ne peut pas être à coté de E F ni J
F : 8 éléments, ne peut pas être à coté de F ni G ni H
G : 7 éléments, ne peut pas être à coté de H ni I
H : 6 éléments, ne peut pas être à coté de H ni J
I : 3 éléments, pas de contrainte
J : 3 éléments, pas de contrainte

1er point, Les éléments J n'ont pas de contrainte, mais en fait, ils en ont. Les éléments J ne peuvent pas être à côté des éléments B E ou H.

Si l'objectif est de recenser toutes les combinaisons possibles, c'est ""facile"". C'est du parcours d'arbre. Mais qu'on prenne l'arbre par un bout ou par l'autre, peu importe, il faudra de toutes façons parcourir tout l'arbre.

Le cas le plus intéressant est si on cherche une solution.

Pour chaque élément , on calcule son nombre de voisins possible (99 - nombre d'interdits) Pour chaque élément de type J, on a donc 99-18-8-6=67 voisins possibles. Et on va ordonner les éléments : du plus contraint au moins contraint. On va d'abord essayer de caser les éléments incasables, et on va garder les éléments faciles à caser pour la fin. Comme ça, si un scénario conduit à une impasse, on devrait le détecter assez tôt.

L'autre piste, c'est de parcourir la grille en spirale : on essaie de remplir le milieu de la grille, et on finit par les coins. Ainsi, on commence par les case avec 4 voisins ( lles plus copliquées à gérer, car 4 contraintes, puis les cases des bords, et enfin, les 4 coins. Là aussi, l'idée, c'est de détecter au plu vite les scénarios qui mènent à des impasses.

En faisant du parcours d'arbre, et en combinant ces 2 règles, tu devrais avoir une solution optimale.
Eventuellement, il faut recalculer la fonction 'nombre de contraintes' à chaque étape, mais je ne pense pas que ce soit utile.

[wiwaxia]

Bonjour,

Je crois que deux outils de type tableau sont indispensables:

a) la liste des éléments disponibles, soit ici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
CONST Ne = 10;
TYPE ListeE = ARRAY[1..Ne] OF Byte;
NombreE: ListeE;

initialsée aux valeurs indiquées:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
CONST NiniE: ListeE = (25, 18, 12, 10, 8, 8, 7, 6, 3, 3);
NombreE:= NiniE;

b) la matrice de non-adjacence, où sont consignées touts les proximités interdites:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
TYPE TabNN = ARRAY[1..Ne, 1..Ne] OF Bool;
VAR A: TabNN;

Cette matrice est symétrique en raison de la réciprocité des interdictions; on aura ainsi:
A ne peut pas être à côté de B C E ni H

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
A[1, 2]:= False; A[2, 1]:= False;
A[1, 3]:= False; A[3, 1]:= False;
A[1, 5]:= False; A[5, 1]:= False; 
A[1, 8]:= False; A[8, 1]:= False;

Un remplissage de la grille ne pourrait-il résulter simplement d'un remplissage aléatoire ligne par ligne, ou colonne par colonne ?
On aurait ainsi pour tout élément interne (i, j) , en progressant de la gauche vers la droite, quelque chose comme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
TYPE Grille = ARRAY[1..Ne, 1..Ne] OF Byte;
VAR G: Grille; 
      h: Byte; Test1, Test2: Bool;
...
h:= Random(Ne) + 1;       
Test1:= A[G[i, j - 1], h]; Test2:= A[G[i - 1, j], h]; 
IF (Test1 AND Test2) THEN G[i, j];= h;

L'emplacement des cases à remplir pourrait lui-même faire l'objet d'un tirage aléatoire, en plus de leur contenu, après initialisation de celui-ci à zéro.

[johnlobs]

Bonjour,

Très intéressant comme sujet.J'ai malheureusement pas pu tout lire par contrainte de temps mais cela me rappelle le problème des neufs reines que j'avais résolu grâce au fameux "backtraking" algo(ou retour sur trace)
Tu pourras même trouver toutes les combinaisons possibles existantes.

C'est parti pour une bonne session de recherches et de boulot.....
Bon courage!!

N'oublie pas les diagonales dans ta matrice M[i,i] ...
Bonne chance.