Discussion :

[tunidev]

Bonjour
j'ai un probleme que j'arrive pas a résoudre:
j'ai une salle d'examen de N tables , je dois y mettre X candidats avec X <= N
quand X <N je dois optimiser l'emplacement des candidants de telle sorte que la distribution des candidats soit equilibré
Merci

[Zavonen]

Il faut déja préciser comment sont disposées les tables.
Mettons que ce soit un rectangle.
On représente les places disponibles par une matrice.
Ensuite il faut introduire une distance.
Par exemple distance de la place (i,j) à la place (k,h) par exemple:
|i-k|+|j-h| logique vu la nature du problème.
Ensuite on a :
le nombre de places total m*n
le nombre de candidats à installer N
On essaye d'installer tous les candidats avec une distance donnée D entre les candidats.
Algo: Placer le premier en (1,1) puis le second à la première place libre à distance D puis le troisième à la première place libre à distance D des deux premiers et ainsi de suite.
Succès si on arrive à placer tout le monde
Si échec remplacer D par D-1 et recommencer
Tout le problème revient à déterminer le D de départ, on peut toujours prendre m+n, mais c'est loin d'être optimum.

[tunidev]

Merci de votre reponse
la disposition des tables est la suivante

[Zavonen]

Je suppose un candidat maximum par table
Alors va pour une matrice 8x3
On cherche à placer un nombre N <24 de candidats avec une distance d
On met des 0 sur toute la matrice pour initialiser.
Ensuite on met un 2 à la position (1,1) puis des 1 dans toutes les cases à une distance moindre que d de (1,1)
puis ensuite un second 2 dans la première case nulle et ainsi de suite tant qu'il y a des cases nulles.
A la fin on compte le nombre de 2, c'est le nombre de candidats placés.
Si ce nombre est < N on recommence avec d-1 au lieu de d.
On peut toujours commencer avec d=9, ou bien d=8 si N>2
Si deux candidats par table alors tout refaire avec une matrice 16x6

[ol9245]

calculer un tableau qui donne pour chaque table la distance D au candidat déja assis le plus proche. cette distance vaut zéro si la table est occupée.

Code :

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

1
2
3
4
5
6
7
8
pour tous les candidats faire :
    choisir une des tables qui a D le plus grand. Soit T cette table
    instaler le candidat en T
    pour toutes les tables B dont D==0 faire :
         calculer distance TB
         sit TB < D(B), actuliser : D(B)=TB
    suivant
suivant

[acx01b]

salut

il y a un algorithme (très simple) qui convergera assez rapidement :

mettre tout les élèves au hasard

tant que temps < 1 minute
prendre un élève au hasard
le déplacer au hasard
si situation pire que la précédante annuler le déplacement
fin tant que

a+

[ol9245]

Bonjour
j'ai un probleme que j'arrive pas a résoudre:
j'ai une salle d'examen de N tables , je dois y mettre X candidats avec X <= N
quand X <N je dois optimiser l'emplacement des candidants de telle sorte que la distribution des candidats soit equilibré
Merci

en repensant a ce probleme il est clair quil faut maximiser qq chose qui ressemble a l'espacement entre les eleves mais comment calculer cet espacement ? je m'explique : arrive a un certain taux de rempilissage, presque tous les eleves auront au moins un voisin proche. donc la distance au plus proche voisin n'est pas un bon critere : la plupart des solutions deviennent identiques au regard de ce critère.

a toi de trouver un critere "d'espace vital" pertienent que tu vas ensuite maximiser par une methode ou une autre. par exemple l'espace vital est la somme des places vides ponderes par l'inverse du carre de leur distance. Je crois qu'un critere de ce type est plus robuste que juste savoir ou est ton plus proche voisin.

autre prob : quand tu met qqun qqpart, tu modifie "l'espace vital" de tout le monde. c'est donc la somme globale des espavec vitaux de chacun que tu dois optimiser. ca devient trop lourd pour etre honete. il doit y avoir plus silple et plus elegant.

[Zavonen]

On peut aller plus vite.
Préalculer pour la distance choisie, la taille d'une 'boule' de rayon R au sens des espaces métriques.
Cela fait si l'on veut placer N candidats sur m*n places, faire le rapport m*n/N et choisir pour premier D dans l'algo que je suggère le rayon d'une boule de cette taille.