Discussion :

[Nesbit]

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 !

[Aleph69]

Bonjour,

les parités de n et N tu distingueras, des solutions tu trouveras!

[Nesbit]

Bonjour,

Pourrais-tu être plus précis ?

Prenons un exemple: choisir 73 points parmi 100 points

[Aleph69]

Tout d'abord, quelle est la définition d'un "choix équitable" selon toi?

[prgasp77]

Bonjour,

Donner N points parfaitement répartis sur un cercle (équidistant).

Les solutions de sont N points répartis sur le cercle unité (ils forment un N-polygone régulier).

Trouver un algorithme pour choisir de manière la plus équitable possible n points (n < N) à partir de ces N points.

Une définition d'équitabilité s'impose.

[Nesbit]

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.

Bonjour,

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).

[prgasp77]

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,

[Aleph69]

Bonjour,

de quelle distance parle-tu? Je doute que ce soit de la distance euclidienne...

[prgasp77]

De la distance usuelle de Z/nZ. Ou la distance telle que définie dans le jeu de société wanted xD

[Nesbit]

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,

Merci prgasp77, ça me paraît... correct Mais peux-tu démontrer que cette solution est optimale ?

de quelle distance parle-tu? Je doute que ce soit de la distance euclidienne...

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).

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.

T'as mal lu la définition peut-être ?

[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.

[pseudocode]

Merci prgasp77, ça me paraît... correct Mais peux-tu démontrer que cette solution est optimale ?

Elle est optimale au sens de l'erreur quadratique moyenne (EQM) sur la distance entre 2 échantillons.

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.