Problème d'ordonnancement en java

**kossistus** · 30/07/2007, 15h46

Bonjour à tous,
Voici mon problème : Je dispose d'un ensemble de figures géometriques(8000). Je dispose aussi d'un ensemble de points.Mon problème est de distribuer les figures aux points, chaque point aura ainsi un territoire constitué d'un ensemble de ces figures. Initialement j'attribue à chaque point une surface totale atteignable. Les allocations sont faites en fonctions des distances minimales des points au figures.Donc un point se voit attribuer une figure de surface S tant que sa surface allouable n'est pas atteinte.
Ma question :
-Je me demande s'il n'y a pas un algorithme qui fais proprement là même chose afin que je puisse l'appliquer dans mon cas. Je cherche encore....Une idée
-Quelqu'un voit il comment je devrais proceder sans réinventer la roue ?
Mon idée : J'ai pensé à associé a chaque point une liste temporaire des
figures , triée suivant la distance du point au aux figures.
Je mets tout çà dans un Map. Un ordonanceur qui detient la vrai liste des figures alloue chaque point et suprime de sa liste toute figure déja allouée. Qu'en pensez vous?
Merci de toutes vos suggestions.

**anadoncamille** · 04/08/2007, 03h53

Bonjour,

J'ai quelques questions :
- tu tries les figures ou les points?
- les distances figure-point sont calculées comment?

A prime abord, ta roue n'existe pas en entier mais dans la classe Collections tu as la méthode Colections.sort(MaCollection) qui trie un Vector ou la collection que tu choisis. Si tu choisis un tableau, utilise Arrays.sort(MonTableau)

**kossistus** · 04/08/2007, 22h42

Envoyé par anadoncamille

Bonjour,

J'ai quelques questions :
- tu tries les figures ou les points?
- les distances figure-point sont calculées comment?

A prime abord, ta roue n'existe pas en entier mais dans la classe Collections tu as la méthode Colections.sort(MaCollection) qui trie un Vector ou la collection que tu choisis. Si tu choisis un tableau, utilise Arrays.sort(MonTableau)

anadoncamille : je te remercie pour tes réponses.
1- Je trie les les figures suivant les distances par rapport au points.
2- La distance figure-point est connue car la methodé existe déja.
3-En effet dans mon algorithme j'utilise Collections.(sort, DistanceComparator) qui trie bien les figures.
==>Le problème est peut être un problème d'optimisation. Des milliers de figures à faire partager quleques centaines points. Je ne vois pas comment le faire pour que la complexité ne soit pas trop élevée.

**sinok** · 05/08/2007, 03h58

En fait là tu sort du domaine de la prog comme on a l'habitude de le faire pour rentrer dans celui de l'optimisation Combinatoire ou de la programmation par contrainte.

Donc autant se diriger vers les outils qui sont fait pour.

En java un solver connu et open source est choco: http://choco-solver.net/index.php?title=Main_Page.

Ce genre d'outil te demande de définir un modèle de contraintes à respecter, un résultat que l'on peut viser (genre maxmiser tel ou tel critère, dans ton cas maximiser la surface des points => utiliser un nombre minimal de points).
Puis tu laisse le solver travailler jusqu'à temps qu'il te fournisse une réponse (s'il existe une réponse bien sûr).
Ensuite pour obtimiser le temps de traitement il faut en général trier les contraintes par ordre d'importance (la contrainte éléminant le plus de cas devant venir en premier)

Enfin voilà des cours pour assimiler les concepts:

Recherche opérationnelle (aka optimisation combinatoire): http://www.librecours.org/cgi-bin/co...k=info&elt=183

PPC: http://bat710.univ-lyon1.fr/~csolnon/Site-PPC/e-miage-ppc-som.htm

**anadoncamille** · 05/08/2007, 16h59

Salut,

ton problème me fait penser à un problème de 3D, fais-tu un moteur 3D ou c'est autre chose? De la reconnaissance visuelle par exemple?

**kossistus** · 05/08/2007, 23h12

Envoyé par anadoncamille

Salut,

ton problème me fait penser à un problème de 3D, fais-tu un moteur 3D ou c'est autre chose? De la reconnaissance visuelle par exemple?

Salut,
Non, je fais de la simulation et les figures représentent en fait des polygones dans tous leurs états.

**anadoncamille** · 06/08/2007, 01h10

Salut,

J'ai du mal à me représenter ton problème, mais si tu arrives à écrire un algorithme qui fonctionne à coup sûr, peu importe le langage, l'optimisation et la complexité, il y aura moyen de l'optimiser sans casser les contraintes auxquelles tu dois répondre.