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

[Aleph69]

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

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

[prgasp77]

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

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

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.

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

[Aleph69]

Ah oui, effectivement j'ai très mal lu la définition : mea culpa!
On reprend à la source :

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

J'ai deux questions :
1. où intervient m dans la définition?
2. pourquoi ne pas se contenter de minimiser M?

[prgasp77]

Ah oui, effectivement j'ai très mal lu la définition : mea culpa!
On reprend à la source :

J'ai deux questions :
1. où intervient m dans la définition?
2. pourquoi ne pas se contenter de minimiser M?

1. je pense qu'il y a faute de frappe dans son message, il veut minimiser l'écart entre M et m (et non n)
2. je suis d'accord, c'est d'ailleurs, je pense, équivalent.

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

[Nesbit]

1. je pense qu'il y a faute de frappe dans son message, il veut minimiser l'écart entre M et m (et non n)

Effectivement c'est une faute de frappe, m au lieu de n C'est corrigé.

2. pourquoi ne pas se contenter de minimiser M?

1. je suis d'accord, c'est d'ailleurs, je pense, équivalent.

Non je ne pense pas. Ce n'est pas la même chose.
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.

[Nesbit]

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

Oui. Je pense que ça équivaut à mon critère (minimiser M-n).

7 échantillons parmi 19 points
-> 7 intervalles espacés idéalement de (19-7)/7 = 1,71429...

C'est plutôt 19/7 = 2.71429..., n'est-ce pas ?
Donc

La solution qui minimise l'objectif est 5 espacements de taille 2 et 2 espacements de taille 1.

devrait être "5 espacements de taille 3 et 2 espacements de taille 2".

[Aleph69]

Et pour {1,4,6,8,10} c'est optimal? (discussion avec moi-même : la réponse est oui! )

C'est dommage l'algorithme est tout bête, je m'attendais à quelque chose de plus joli.

[Nesbit]

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 , alors la somme des est de N: . On cherche à:









Les quatre critères sont équivalents.

J'ai trouvé le résultat suivant:



...l'heure de déjeuner... à suivre...