Bonjour,

Avec mon frère on s'est posé un petit exercice. On part du principe qu'on a 7 personnes dans la famille, et on cherchait la date de l'année qui serait la plus proche de tous les anniversaires des 7.

Soucis, comment on fait ça ? On a fait un algo un peu naïf en disant : Pour chaque jour de l'année, on calcule la distance des 7 anniversaires par rapport à ce jour, et on les additionne. Et au final on prend le jour dont la somme est la plus faible.

Sauf que techniquement, c'est pas forcément ce qu'on veut.

Exemple avec 3 dates d'anniversaires, qui sont les jours 10, 10, et 40 de l'année.

Le jour de l'année dont la somme des différences par rapport aux 3 dates sera le jour 10. En effet, le jour 11, on ajoute 1j à la somme (+2j car on s'éloigne du jour 10, -1j car on se rapproche du jour 40). Sauf que nous on voudrait plutôt une solution qui nous sorte le jour 20 (moyenne/barycentre entre les 3 dates).

Sur la papier, ça se calcule bien, sauf que le soucis, c'est que une année, ça se voit pas comme une simple droite, mais comme un cercle. En effet, le 01/01 est le lendemain du 31/12. La différence entre les 2 jour est donc 1 et pas 364.

Donc si je prend 2 dates, le 01/01 et le 30/12 (c'est à dire les jours 1 et 364), je voudrais que ca me ressorte le jour 365, le 31/12, et pas le 30/06 ou le 01/07.

Une idée de comment aborder le sujet ?

Merci

Le 1er problème que tu soulèves : Best(10,10,40) doit donner 20. 

Cette partie-là, c'est classique, c'est la méthode des moindres carrés. dist(k) = (k-10)²+(k-10)² +(k-40)²  et on cherche le jour k pour lequel cette somme est minimale. On dérive, etc,  et on trouve 20.

L'autre partie est plus problématique... mais à peine.

Si on a 7 anniversaires, on va faire le calcul précédent 7 fois (on va voir comment), Dans chaque cas, on trouvera un jour optimal et une distance dist(k) associée. Et au final, parmi ces 7 solutions, on gardera celle qui a la distance minimale.

7 fois le calcul précédent... 

Imaginons que la 1ère personne soit née le jour 20. Au lieu de compter les dates anniversaires entre 0 et 365, on les comptera entre 20+1 et 365+20.

Donc notre 1ère personne n'est pas née le jour 20, mais le jour 385.  Et on peut chercher le jour optimal , etc etc.

Exemple, avec 7 personnes nées les jours 20 40 60 200 250 300 et 350

On va en fait dire qu'elles sont nées les jours 385 40 60 200 250 300 et 350 pour le 1er calcul

Puis 385 405 60 200 250 300 et 350 pour le 2ème calcul 

Puis 385 405 425 200 250 300 et 350 pour le 3ème calcul etc etc. 

Merci pour ta réponse.

Je t'avoue que ce genre de méthode (pas forcément avec la méthode des moindres carrés, mais genre avec du bricolage à base de simples moyennes : (10+10+40)/3 = 20), on y avait pensé, mais on aurait voulu trouver une méthode universelle qui ne demande pas à calculer toutes les possibilités séparément pour ensuite choisir la meilleure solution.

Certes ça fonctionne, mais imaginons qu'on veuille faire le même calcul pour 150 personnes, la ça devient problématique, à moins de faire ça via un algo qui fera les calculs à notre place.

Edit : 

j'ajoute qu'on a pensé à une solution à base de de centre de gravité. En mettant tous nos points autour d'un cercle, on trouve facilement le centre de gravité, qui nous donne un vecteur, qui nous permet de définir un point du cercle à partir de ce vecteur. Sauf que ca ne nous convient pas non plus en fait.

Admettons qu'on ait 1 point en 0 et 2 points en Pi, on aura un vecteur final qui pointera vers le point en Pi. Ce qui ne fait pas une moyenne non plus dans le sens ou je l'entends.

-
Edité par Tiffado 27 novembre 2019 à 10:10:07

Ça c'est un problème intéressant ! Mais j'ai peur qu'il n'y ait pas toujours une solution.

Dans le plan, le barycentre de deux points A et B est l'unique point G tel que \( \vec{GA} + \vec{GB} = \vec{0} \). Sur le cercle, de façon analogue on peut chercher les points tels que GA + GB = 0, ou je note GA la longueur de l'arc orienté GA (je ne me souviens plus du symbole en LaTeX...). Il y en a toujours deux, diamétralement opposés. Si déjà avec deux points on n'a pas l'unicité du barycentre, j'ai peur que le problème reste vrai avec un nombre quelconque de points.

Après, peu importe : le but est de trouver une date qui minimise les distances, tant pis si elle n'est pas unique (voire de les trouver toutes).

Par analogie, on pourrait utiliser la formule \( OG = \dfrac{OA_1 + OA_2 + \cdots + OA_n}{n} \) où les \( OA_i \) désignent la longueur de l'arc orienté et O est un point quelconque. Dans le plan, le point G est unique, peu importe O. Là ce ne sera pas le cas à mon avis.

-
Edité par robun 27 novembre 2019 à 21:00:41

robun a écrit:

Par analogie, on pourrait utiliser la formule \( OG = \dfrac{OA_1 + OA_2 + \cdots + OA_n}{n} \) où les \( OA_i \) désignent la longueur de l'arc orienté et O est un point quelconque. Dans le plan, le point G est unique, peu importe O. Là ce ne sera pas le cas à mon avis.

Bonjour robun, pour le coup, c'est un peu comme notre algo naïf qui, pour chaque jour de l'année, calculait la somme des différences de jours entre le jour en question et les différentes dates.

Avec ce principe avec 2 points A et B sur le cercle, ce calcul donnera le même résultat pour tous les points qui se situe sur l'arc de cercle le plus petit entre les 2 points. Et dans le cas où ces 2 points formeraient un diamètre du cercle, alors n'importe quel point du cercle conviendrait.

Après pas mal de recherches, on est arrivé à une conclusion : c'est pas qu'il n'y a pas de solutions, c'est qu'il y en a plusieurs suivant la façon dont on procède, reste à voir quelle est la solution qui nous convient le plus.

Dans notre cas, l'algo naïf nous donne comme réponse le 14 Janvier, alors qu'en passant par le centre de gravité, on trouve le 7 Janvier. Pas si éloigné que ça dans un sens, mais pas la même date tout de même.

-
Edité par Tiffado 28 novembre 2019 à 10:16:41