Bonjour tout le monde,
avant de lancer mon concours j'aimerai juste faire un sondage pour voir si des personnes sont intéressées.
 
Voila juste une explication grossière.
Le but n'est pas très compliqué, il consiste à placer des étiquettes sur une surface en deux dimensions de taille définie (cf. carte géographique) en minimisant les collisions. chaque étiquettes est décrite comment un rectangle (l, h) attaché à un point (x, y), elle peut être placée à quatre endroits différents par rapport au point : en haut à gauche, en haut à droite, en bas à gauche et en bas à droite.
 
La solution doit décrire la place de chaque étiquette par rapport à son point. Quelques Fichiers de données seront fournit pour pouvoir élaborer  son algorithme, au bout d'un certain temps (par exemple 3 semaines) un fichier de données correspondant au concours sera mis à disposition, vous aurez alors un délai avant de rendre vos solutions (par exemple 5 jours).
 
Celui qui a la solution ayant le moins de chevauchement gagne ^_^ (on verra pour la prise en compte du temps de calcul et de la mémoire utilisée dans la solution), le langage est libre.
 
Voici un exemple :
Placement initial (aléatoire):

 
Placement final (dans ce cas il n'y a plus de collision, mais en général il en reste):

 
Voila, ce n'est qu'un aperçu grossier, dites-moi ce que vous en pensez.

c'est tes devoirs en gros ?

Absolument pas (je ne suis pas étudiant), simplement comme j'ai vu qu'il y avait de l'intérêt pour les concours je me suis dit que ca serait sympa d'en lancer un. Il me semble, de plus, assez intéressant.
D'ailleurs, libre à vous de faire des propositions au sujet de la donnée.
 
SVP, évitez les posts non constructif (cf. le deuxième).

alors pourquoi tu veux pas qu'on le fasse en ruby ?
 
d'ailleurs, c'est purement un problème d'algo, on s'en tamponne bien que l'implémentation soit en C+
+

J'ai écrit : "le langage est libre", c'est effectivement un problème d'algo.

Cat. Algo

Le chevauchement se calcule comment ? C'est la surface de chaque etiquette qui chevauche une autre etiquette ?

Détecter le chevauchement de surfaces rectengulaires alignées n'est pas tres compliqué ....

Oui mais il y a plusieurs façon de le faire. Soit au nombre de surface qui se chevauchent soit avec la surface des surface qui se chevauchent donc je voulais savoir ...

Ok, je cromprends! Evaluer le niveau de chevauchement par la surface recouverte donnerait une estimation fine du resultat.

En fait c'est soit il y a chevauchement soit pas, le but étant de minimiser le nombre de chevauchement, il n'y a pas de calcul de surface.

Oui c'est bon, j'ai modifié, dsl.

Manque un "oui mais je ne sais pas où je vais trouver le temps" dans ton sondage

Si ça va pas trop vite je m'essaierais bien.
Une idée pour le format du fichier de données ?
 
Ah oui et aussi je pense qu'il vaudrait mieux prendre en compte la surface de chevauchement : plusieurs petits chevauchements (genre 5% de la surface du cadre) ça reste plus lisible qu'un gros (genre 50 %)

Le but est quand même de garder une donnée la plus simple possible, on ne comptera que le nombre de chevauchement et nous n'entreront pas dans des calculs de surface (après ca devient le bordel  ).

Format de sortie : un bitmap n/b ?

bmp, t'es fou, pnm ou un truc simple

Ca me parait intéressant dans le sens où ce problème NP-complet, donc on peut pas espérer avoir la solution exacte (enfin sauf si le nombre de points est très faible); à partir de là tout l'intérêt réside dans la recherche de la meilleure solution approchée !
 
PS : ceux qui ne voient pas l'intérêt du problème ne doivent pas connaitre grand chose en algorithmique

Le format de sortie n'est pas obligatoirement du bitmap, tu peux très bien donner la solution sous la forme d'une série de positions (texte).
Je donnerai touts le détail lorsque, éventuellement, je lancerai le concours pour de vrai  

Ouais moi je serais plus pour générer un fichier texte contenant la position de chaque cadre par rapport à son point (en haut à gauche, en bas à droite...). Combiné au fichier de données qui contient la position des points et la taille des cadres, ce sera facile de faire un petit prog indépendant pour afficher le résultat.

j'ai réalisé un tel algo dans un projet. il etait question d'une cible, sur laquelle des points étaient placés aléatoirement autour de leur valeur en %
 
cela dit, il n'est bien sûr pas toujours possible de placer toutes les étiquettes convenablement (trop de points proches)
 
le langage est C# --> XML/SVG
 
sujet intéressant en effet

 
Ca ressemble en effet à un problème d'optimisation à résoudre avec l'algo de Métropolis.

tu pourrais filer la doc de ton TD au moins :
 
http://pifou.myftp.org/~bordel/TD/cga-PFLP.pdf
 

Bein ne te gène pas, tu peux la prendre (je pense que t'es quand même capable d'utiliser google pour trouver de la doc par toi même  ).
 
Bon vu le faible intérêt que mon problème à suscité, je ne pense pas lancer ce concours. N'hésiter pas à voter si vous êtes interessé, on ne sais jamais.

Bah, moi ca m'aurait amusé qu'il soit lancé ce concours.
 
Le premier pb est que ce genre d'algo est traité en long en large et en travers par de nombreux bouquins. J'en ai un d'ailleurs dont le nom est "algorithmes en langage C", qui en parle et évalue différentes solutions (si jme rapelle bien). Donc, on va dire que les voies classiques sont dejà explorées et connues.
 
Le second pb est le temps ...

je ne comprends pas...
tu as ta carte et tes rectangles, et tu veux les re-répartir?

>moktar1er
tu as des points dont tu connais les coordonnées à étiqueter. les étiquettes sont representées sous la forme de rectangle (pour simplifier).
Le but est de placer chaque étiquette autour de son point de façon judicieuse pour minimiser le nombre de chevauchement global.
L'étiquette peut être placé en haut à gauche ou en haut à droite ou en bas à gauche ou en bas à droite par rapport à son point.
 
Peut-être que c'est plus facile si tu te représenter les points comme des villes sur une carte routière et les étiquettes comme les noms de ces villes. Le but est de faire un algo qui fait la carte routière la plus lisible.

mouais OK je vois
et le but du concours? faire au plus rapide?

Relit peut-être le premier post, le but premier n'est pas la rapidité mais la qualité de la solution.

je préfère reformuler en posant des questions simple pour comprendre au mieux
j'ai cru comprendre que tu voulais classer les solutions au moindre chevauchement mais... ne vaut-il pas plusieurs petits chevauchements minimes, insignifiants, qu'un seul où 2 boîtes se supperposent?

Bon, vu qu'il y a quand même des motivés, je lancerai ce concours le week-end prochain

on a le droit d'utiliser ton code source en vb6 ?

J'ai essayé de le faire avec un algorithme génétique
Ben ça marche plutôt bien

oui

 
  ... une petite recherche en depth-first, tu lances ca avec LA plus grosse machine que tu trouves sur la terre, et tu as la solution optimale  

 
+ 10²² ! . Suffit de lire un bon pdf, et tu as l'algo   . Aucun merite, aucun interet.  
 
c'est un "stupide" probleme de permutation. Sachant la place que peut prendre chacun des rectangles, le but consiste a trouve la permutation (placement de chaque rectangle) qui minimise le taux de chevauchement. Bref...des probleme de permutation (comme le fameux voyageur de commerce) y'en a a la pele !  

c'est de la recherche operationnelle quoi

Moi je peux pas, j'ai déjà des tas de trucs à faire
 
Mais je trouve de problème sympa, donc je vote pour quand même