Problème du point central

Merci KX pour ta réponse ! Ta méthode récursive me parait simple et efficace ! Mais est-elle juste ? Difficile de le démontrer... Ça fait mal à la tête ! ;)

En fait j'ai compris ta méthode, et elle est juste. Elle revient à utiliser le principe des barycentres, comme l'avait suggéré Eric.
Sauf que l'on est pas obligé de prendre la ville la plus éloignée pour faire le milieu du trajet comme tu l'as dit.

Il suffit de prendre le milieu de chaque segment (trajet) entre chaque couple de points initiaux (villes initiales). On réitère l'opération pour chaque nouveau couple de points (milieux des segments précédents) juste qu'à ce qu'il ne reste plus qu'un seul milieu, qui est le point central.
Attention, le nombre de points ne sera pas toujours pair (forme 2n+1). Il y a donc le risque de considérer qu'un milieu (regroupant 2 personnes) vaille autant qu'un point initial (ville initiale de 1 personne). D'où l'utilité d'utiliser la méthode des barycentres, c'est à dire pondérer chaque point initial, et les additionner à chaque fois qu'un milieu est créé. Ainsi, les étapes suivantes ne prendront pas toujours le milieu du segment, mais calculeront en fonction du "poids" de chaque point.

"est-elle juste ?"

À chaque itération on ressert l'enveloppe convexe en s'aidant des milieux, donc l'algorithme devrait converger et se terminer (peut-être pas sur une seule ville, mais éventuellement plusieurs villes voisines)

Après au niveau de la correction, c'est vrai que c'est un peu flou, mais puisque l'enveloppe convexe est resserré sur les milieux de ses "diagonales" (les plus longues distances entre deux individus), on va se retrouver récursivement avec une sous-enveloppe convexe au centre de la première, et donc atteindre un "milieu" (un petit exemple vite fait : centre.png)

Mais c'est plus un consensus de décision (chaque individu décide de se déplacer à mi-chemin de celui qui est le plus loin, et on recommence jusqu'à être tous ensemble), qu'un véritable calcul d'optimisation.

Re,

Tu sais, sauf pour le fun et le plaisir de chercher, je pense que tu n'as pas besoin d'exactitude.

Une fois déterminé déterminé le centre de toute façon tu n'organiseras pas ça dans un village de 300 habitants. Mais plutôt dans une ville de 10-20000 habitants pour y avoir des autoroutes proches, une gare mieux desservie que 2 fois par jour, du choix dans l'hébergement et peut-être un peu d'activité le soir. Ce qui peut t'emmener à 50 km du centre...

eric

"Il suffit de prendre le milieu de chaque segment (trajet) entre chaque couple de points initiaux (villes initiales). On réitère l'opération pour chaque nouveau couple de points (milieux des segments précédents) juste qu'à ce qu'il ne reste plus qu'un seul milieu, qui est le point central."

Si tu as n points initiaux, tu vas avoir n² couples (n²-n en fait), donc potentiellement n² milieux à l'étape suivante, puis n^4, etc. Donc certes les villes vont être de plus en plus proches, et à un moment le nombre de collisions va devenir important et diminuer le nombre de villes, mais tu risques quand même d'exploser le nombre de villes intermédiaires. C'est pour cela que j'avais considéré "la ville la plus loin", ça permettait de conserver n villes à chaque itération.

Remarque : tu parles de "milieux des segments précédents", c'est à dire que tu réfléchis géométrie, moi je pensais au milieu du plus court chemin obtenu avec Dijkstra, c'est à dire la ville qui est kilométriquement à mi-chemin des deux, pas géométriquement...

Re,
Je savais que c'était compliqué les échecs mais à ce point je n'imaginais pas... ;-)
eric

@eriiic : Quel rapport avec les échec ? ^^

@ccm81 : C'est exactement ce que j'essaie de transposer sur Google Map ! Merci

@eriiic : Quel rapport avec les échec ? ^^
Oulaaaa, arrête de réfléchir, tu es en surchauffe là ;-)
C'était dans ta question :
Ex : j'organise un weekend entre pote. Le but du weekend est de jouer aux échecs

eric

Merci encore pour tes idées Mamiemando !
Grâce à toi, je serai sans doute le premier homme de l'histoire et du web à coder l'algorithme du point central ! Tellement excitant ! ;) Je te tiens au jus.
Je laisse le sujet ouvert une semaine au cas où quelqu'un aurait enfin le nom de ce problème.