Version imprimable
Bonjour,
Quelqu'un peut m'aider SVP ?
Problème: Donner N points parfaitement répartis sur un cercle (équidistant). Trouver un algorithme pour choisir de manière la plus équitable possible n points (n < N) à partir de ces N points.
Par exemple, si j'ai 10 points {1,2,3,4,5,6,7,8,9,10} et je veux en prendre 5 points, alors la solution est {1,3,5,7,9}.
Merci et bonne soirée !
Bonjour,
les parités de n et N tu distingueras, des solutions tu trouveras! :mrgreen:
Bonjour,
Pourrais-tu être plus précis ?
Prenons un exemple: choisir 73 points parmi 100 points :ccool:
Tout d'abord, quelle est la définition d'un "choix équitable" selon toi?
Bonjour,
Les solutions de http://chart.apis.google.com/chart?c...imath\theta}=1 sont N points répartis sur le cercle unité (ils forment un N-polygone régulier).Citation:
Envoyé par Nesbit
Une définition d'équitabilité s'impose.Citation:
Envoyé par Nesbit
Bonjour,Citation:
Problème: Soit N points parfaitement répartis sur un cercle (équidistant). Trouver un algorithme pour choisir de manière la plus équitable possible n points (n < N) à partir de ces N points.
La notion "équitable" était un peu vague. Ce que je voulais dire, c'est que les n points (parmi les N) soient le plus uniformément répartis sur le cercle.
Je pense qu'on peut trouver différentes définitions formelles de ceci, par exemple (la mienne): si on note M la distance maximale et m la distance minimal entre deux points consécutifs des n points, la solution (le choix des n) optimal minimisera l'écart entre M et m (i.e. M - m).
Dans ce cas, je dirais naïvement que la solution optimale est :
le k-ième point sélectionné parmi les N points existants est le (k * N) div n-ième point, où div représente la division euclidienne.
Exemple :
Si je veux sélectionner 7 points parmi 19, les points
1 * 19 / 7 = 2
2 * 19 / 7 = 5
3 * 19 / 7 = 8
4 * 19 / 7 = 10
5 * 19 / 7 = 13
6 * 19 / 7 = 16
7 * 19 / 7 = 19
Soit M = 3 et m = 2 (dans un espace métrique particulier).
Cdlt,
Bonjour,
de quelle distance parle-tu? Je doute que ce soit de la distance euclidienne...
De la distance usuelle de Z/nZ. Ou la distance telle que définie dans le jeu de société wanted xD
Ah non pas les jeux de cartes, j'essaie d'arrêter! ;)
Pour l'instant la définition donnée de l'équitabilité me gêne un peu car elle ne tient compte que des points successifs. Si parmi N points (N très grand) uniformément répartis sur le cercle unité, je dois choisir 3 points, avec la définition donnée, il me suffit de prendre 3 points non consécutifs pour avoir un choix équitable. Or, intuitivement, j'aurais tendance à également vouloir avoir "3 parts" les plus égales possibles dans la mesure où on voit le cercle comme un gâteau... :mrgreen:
Merci prgasp77, ça me paraît... correct :D Mais peux-tu démontrer que cette solution est optimale ?Citation:
Envoyé par prgasp77
Il a utilisé ce que j'appelle distance curviligne: d(A,B) = | la - lb | avec la et lb sont respectivement les abscisses curvilignes de A et B sur le cercle (avec l'origine est un point quelconque sur le cercle).Citation:
Envoyé par Aleph69
T'as mal lu la définition peut-être ? :mouarf:Citation:
Envoyé par Aleph69
Oui effectivement, j'ai mal exprimé ma pensée.
J'aurais dû écrire qu'il suffit de prendre 3 points formant un triplet (p,q,r) dont aucune paire ne forme un ensemble de points consécutifs.
La démo est LAL: elle est assez simple, quelques règles d'arithmétique du lycée et c'est fait (cherche à borner la distance entre deux points consécutifs).Citation:
Envoyé par Nesbit
Non, lorsque Nesbit parle de point consécutifs pour sa définition d'équitabilité, il parle cette fois-ci de points sélectionnés (dans mon exemple, 5 et 8 sont consécutifs, mais ont une distance de 3).Citation:
Envoyé par Aleph69
Ah oui, effectivement j'ai très mal lu la définition : mea culpa!
On reprend à la source :
J'ai deux questions :Citation:
Je pense qu'on peut trouver différentes définitions formelles de ceci, par exemple (la mienne): si on note M la distance maximale et m la distance minimal entre deux points consécutifs des n points, la solution (le choix des n) optimal minimisera l'écart entre M et n (c.à.d M - n).
1. où intervient m dans la définition?
2. pourquoi ne pas se contenter de minimiser M?
Citation:
Envoyé par Aleph69
- je pense qu'il y a faute de frappe dans son message, il veut minimiser l'écart entre M et m (et non n)
- je suis d'accord, c'est d'ailleurs, je pense, équivalent.
Elle est optimale au sens de l'erreur quadratique moyenne (EQM) sur la distance entre 2 échantillons.Citation:
Envoyé par Nesbit
7 échantillons parmi 19 points
-> 7 intervalles espacés idéalement de (19-7)/7 = 1,71429...
* contrainte 1: les espacements Ei sont des entiers: Ei = 0, 1, 2, ...
* contrainte 2: la somme des espacements Ei vaut 12
* objectif: minimiser somme{ (Ei-1,71429)² }
Si Ei=0, alors (Ei-1,71429)² = 2,93877...
Si Ei=1, alors (Ei-1,71429)² = 0,51020...
Si Ei=2, alors (Ei-1,71429)² = 0,08163...
Si Ei=3, alors (Ei-1,71429)² = 1,65306...
La solution qui minimise l'objectif est 5 espacements de taille 2 et 2 espacements de taille 1.
Effectivement c'est une faute de frappe, m au lieu de n :ccool: C'est corrigé.Citation:
Envoyé par prgasp77
Citation:
Envoyé par Aleph69
Non je ne pense pas. Ce n'est pas la même chose.Citation:
Envoyé par prgasp77
Exemple: choisir 5 points à partir de 11 points (notons {1,2,3,...,11}).
Soit 2 solutions:
- {1,3,5,7,9}, ici M=d(1,9) = 3, m=d(1,3) (par exemple) =2.
- {1,4,5,7,9}, ici M=d(1,4) = d(1,9) = 3, m=d(4,5)=1.
Dans les deux cas, M = M_min = 3, pourtant la première est optimale alors que la deuxième ne l'est pas.
Oui. Je pense que ça équivaut à mon critère (minimiser M-n).Citation:
Envoyé par pseudocode
C'est plutôt 19/7 = 2.71429..., n'est-ce pas ? :mrgreen:Citation:
Envoyé par pseudocode
Donc
devrait être "5 espacements de taille 3 et 2 espacements de taille 2".Citation:
Envoyé par pseudocode
Et pour {1,4,6,8,10} c'est optimal? (discussion avec moi-même : la réponse est oui! :mouarf:)
C'est dommage l'algorithme est tout bête, je m'attendais à quelque chose de plus joli. :calim2:
Ca y est, problème résolu !
Tout d'abord on va reformuler le problème.
Si on associe chaque distance curviligne entre deux points consécutifs (ou un espacement, selon pseudocode. Il y en a n) par un entier, notons http://latex.codecogs.com/gif.latex?x_i, alors la somme des http://latex.codecogs.com/gif.latex?x_i est de N: http://latex.codecogs.com/gif.latex?x_1+x_2+...+x_n=N. On cherche à:
http://latex.codecogs.com/gif.latex?...t%C3%A8re)%20}
http://latex.codecogs.com/gif.latex?...seudocode)%20}
http://latex.codecogs.com/gif.latex?...=1}^n%20x_i^2}
http://latex.codecogs.com/gif.latex?...{i=1}^n%20x_i.
Les quatre critères sont équivalents.
J'ai trouvé le résultat suivant:
http://latex.codecogs.com/gif.latex?...20\%20(r%3Cn).
...l'heure de déjeuner... à suivre...
Bien sûr que "oui".Citation:
Envoyé par Aleph69
J'ai du mal à prouver ou réfuter l'algo donné par prgasp77. Je continue avec ça après manger. A toute.Citation:
Envoyé par Aleph69
Ca marche aussi. C'est simplement la définition de espacement qui n'est pas la même.Citation:
Envoyé par Nesbit
Moi je compte l'espace vide entre les échantillons.
1 2 3 4 5 6 7 8 9 X <-------> Y X: position = 2 Y: position = 8 Espacement entre X et Y = 5
:resolu: ?
Je continue...
Donc, pour rappeler, j'ai trouvé que la solution optimale contient et doit contenir (n-r) nombres de valeur q et r nombres de valeur (q+1) où q=N/n et r=N%n.
Reprenons l'exemple de prgasp77: choisir 7 parmi 19 points.
On a N=19, n=7, q=N/n=2, r=N%n=5. La solution contient donc deux (i.e. n-r) 'espacements' de 2 (i.e. q) et cinq (i.e. r) 'espacements' de 3 (i.e. q+1). On retrouve bien le résultat que pseudocode a confirmé.
Pour répondre donc à la question initiale, une solution optimale pour choisir n points parmi N points {1,2,...,N} est
{q, 2q, 3q,..., (n-r)q, (n-r)q+(q+1), (n-r)q+2(q+1),..., (n-r)q+r(q+1)}.
Maintenant, deux questions se posent:
1. La solution donné par prgasp77 est-elle optimale ?
Les 'espacements' donnés par celle-là sont:
https://lh6.googleusercontent.com/-P.../gif.latex.gif
Si on arrive à montrer que parmi les x_i, il y a (n-r) valeur de q et r valeur de q+1, alors elle est optimale.
2. On sait qu'une des solutions optimales est (exprimée avec la notion 'espacement'): q,q,..,q,q+1,q+1,...,q+1 (il y a n-r fois q et r fois q+1). Maintenant, si on ajoute une contrainte: il faut que les (q+1) soient le plus uniformément répartis possible, alors cette solution n'est plus optimale. Comment fait-on ?
Pour info, Stuart P. LLoyd a montré il y a plus de 50 ans que l'arrondi au plus proche voisin donnait un quantificateur régulier optimal (au sens de l'erreur quadratique moyenne). :D
Ça me dit quelque chose ... a-t-il été aidé dans sa tâche par un certain Marshal ? Il était question de minimiser l'erreur quadratique d'un quantificateur, n'est-ce pas ?Citation:
Envoyé par pseudocode
Ca ne me dit rien. Je faisais référence au papier "Least Squares Quantization in PCM" qui est à la base de l'algo Lloyd-Max.Citation:
Envoyé par prgasp77
C'est bien ce à quoi je faisais référence (en tout les cas, essayais de), le Marshal est sorti de mon imagination >_<