Discussion :

[Heimdall]

Salut, je cherche des idées ou des références sur des algo efficaces permettant de résoudre le problème suivant :

Vous avez un rectangle d'une certaine longueur (disons L) et largeur (disons D). Ce rectangle délimite un domaine à l'intérieur duquel vous devez faire un calcul.

Par exemple, pour fixer les idées, disons qu'il s'agit d'une pièce dans laquelle vous devez suivre le déplacement de plein de personnes.

Puisqu'il y a énormément de personnes, je veux diviser le rectangle en N sous-rectangles (N étant fixé à l'avance, il s'agit en fait du nombre de processeurs qui feront le calcul) comportant a peu près le même poids de calcul.

Dans mon exemple, le "poids" de calcul attribué à un sous-rectangle est simplement représenté par le nombre de personnes dans le sous-rectangle.

Pour se faire, j'adopte une méthode de bisection récursive : il s'agit de découper le rectangle principal en 2 sous rectangle... ensuite de découper chacun des sous-rectangles en deux sous-rectangles de poids a peu près égaux... A la fin on obtient N sous-rectangles de poids a peu près égaux.


J'ai besoin, pour chacun des sous-rectangles, de connaitre les sous-rectangles "voisins". Je construit donc, à chaque division, un lien entre chaque sous-rectangle, le tout donnant au final un graphe.


pour fixer les idées voici ce que ça peut donner (en oubliant les couleurs) :




Bon ok... maintenant les personnes bougent et j'ai besoin, parfois, de redimensionner les rectangles, tout en conservant leur nombre, afin de ré-équilibrer leur charge.

Auriez vous un conseil pour un algo qui permettrait de faire ça de manière efficace (plus rapide que de refaire le découpage entier) ?

Merci

[pseudocode]

Auriez vous un conseil pour un algo qui permettrait de faire ça de manière efficace (plus rapide que de refaire le découpage entier) ?

Merci

Si tu modélises ton découpage comme un kd-tree, ca ne te fait que quelques points à bouger pour équilibrer les zones.



Par contre, il y aura surement des cas où il faudra recalculer des parties de l'arbre.

[Heimdall]

Si tu modélises ton découpage comme un kd-tree, ca ne te fait que quelques points à bouger pour équilibrer les zones.



Par contre, il y aura surement des cas où il faudra recalculer des parties de l'arbre.

Est-ce que je peux construire un kd-tree a partir d'un découpage pré-existant ou est-ce que je dois utiliser un kd-tree lors du premier découpage également (c'est à dire abandonner ma méthode de découpage et mon graphe).

Les élements d'un kd-tree sont les coupes, est-ce que je peux facilement obtenir a partir de cet arbre le graphe liant chacun des rectangles à ses voisins ?

[pseudocode]

Est-ce que je peux construire un kd-tree a partir d'un découpage pré-existant ou est-ce que je dois utiliser un kd-tree lors du premier découpage également (c'est à dire abandonner ma méthode de découpage et mon graphe).

A mon avis, ca ira plus vite d'utiliser un kd-tree dés le départ. Et ca irait encore plus vite de trouver sur le net une implémentation d'un kd-tree dynamique

Les élements d'un kd-tree sont les coupes, est-ce que je peux facilement obtenir a partir de cet arbre le graphe liant chacun des rectangles à ses voisins ?

Facilement, non. Il faut construire et maintenir le RAG (region adjacency graph) en plus du kd-tree.

Mais peut-être devrais-tu regarder s'il y a d'autres structures plus adaptées a ton problème de départ.

[Heimdall]

Ok merci, c'est bien ce que je pensais.

En fait je pense que je préfère continuer à découper mes domaines selon ma méthode. C'est une variante de la méthode 'orthogonal recursive bisection'. La seule difference est que je ne découpe pas en alternant les directions, mais toujours selon la direction perpendiculaire à la longueur du rectangle... et ce afin de diminuer les surfaces de mes domaines. Diminuer les surfaces permet de diminuer les communications entre domaines.

Je vais regarder un peu mieux les autres structures que tu m'indiques.

Juste pour le principe, en gros en découpant en deux chaque rectangle, la balance de charge se fera plutôt sur un arbre binaire (lequel ?) et les voisins se trouverons toujours en maintenant un graphe à coté. vrai ?

[pseudocode]

Juste pour le principe, en gros en découpant en deux chaque rectangle, la balance de charge se fera plutôt sur un arbre binaire (lequel ?)

Je n'ai pas compris la question.

et les voisins se trouverons toujours en maintenant un graphe à coté. vrai ?

heu.. oui. C'est le principe meme du RAG que de savoir quels sont les voisins.

[Heimdall]

Je n'ai pas compris la question.

Je demandais si parce que je découpe les rectangles en deux à chaque fois, l'algo qui me permettra de changer les frontières de sorte à équilibrer la charge sur chaque rectangle sera toujours basé sur un arbre binaire à équilibrer ?