Problème du point central Résolu

Question

Bonjour, 

Existe-t-il une sorte d'algorithme de Dijkstra pour trouver le point le plus central entre deux lieux ? Et si oui, peut-on l'étendre à plusieurs lieux ? 

Ex : j'organise un weekend entre pote. Le but du weekend est de jouer aux échecs, donc on peut le faire n'importe où. Mais nous habitons tous très loin les uns des autres. Nous cherchons donc à trouver un point central où nous retrouver.

voilà ! Merci aux matheux qui trouverons son nom ! Ce problème a déjà été posé, c'est obligé.

eriiic · Accepted Answer

Bonsoir,   

je ne connaissais pas l'algorithme de Dijkstra.   
Mais toi j'ai l'impression que c'est plutôt le barycentre de plusieurs points que tu veux (ça sera à vol d'oiseau).   

eric   
    

Edit: à voir la définition de wikipedia tu es à la recherche du point G en fait... :-)  
https://fr.wikipedia.org/wiki/Barycentre_%28g%C3%A9om%C3%A9trie_affine%29 

Jamais tu ne répondras à un mp non sollicité...   
Bon, ça c'est fait.

mamiemando · Answer

Suite à la discussion amorcée ici :
https://forums.commentcamarche.net/forum/affich-15145342-chemin-minimale-entre-deux-ville#7 
 
En fait ce n'est pas vraiment un barycentre. Pour un barycentre on se place dans un espace continue (par exemple le plan) et par rapport aux coordonnées de différents points (ici les villes de départ) et à des poids (ici on prendrait des poids identique si personne ne doit être privilégié, donc ce serait même un isobarycentre), on déduit un barycentre (la ville d'arrivée). Si on suppose que les villes sont placées par des coordonnées géographiques et que le point de rendez-vous peut être dans la pampa ou dans un lieu géographiquement inaccessible, l'approche du barycentre marchera.

Si par contre, on cherche une ville d'arrivée, le problème est différent. Supposons que chaque ville soit modélisée par un sommet, et que les villes voisines soient connectées par une arête pondérée proportionnellement à la distance qui sépare les deux villes (en clair : si une ville A et B sont directement reliées par une route qui fait 10km, on relie les sommets A et B par une arête dont le poids vaut 10). Dans ce modèle de graphe on peut calculer un algorithme de Dijkstra, de Ford Bellman etc... En théorie des graphes on note un tel graphe traditionnellement G = (V,E) ou V (vertices) désigne les sommets (les villes) et E (edges) les arêtes (les routes).

On peut en outre calculer pour chaque ville de départ l'algorithme de Dijkstra, qui permettra de savoir de combien de kilomètres elle est séparée d'une autre ville via le chemin le plus court (arbre couvrant de plus courts chemin).
- Notons S l'ensemble des villes sources : S = {s1, s2, ... } c V.
- Soit t* (target) le sommet de V tel qu'il est le "plus proche" pour l'ensemble des villes sources.
- Soit |u, v| la distance qui sépare un sommet u du sommet v (via le plus court chemin de u à v).

En calculant pour tout s dans S l'arbre de plus courts chemins, on peut calculer l'ensemble des |si, t| ou t est un sommet quelconque. Le coût global pour joindre la ville t est comme dans un isobarycentre w(t) = sum(|si, t|, si in S). On pourrait diviser par le nombre de sources (card(S)) pour avoir le coût moyen mais ça ne change rien puisque ce facteur sera le même pour chaque calcul de coût. Il suffit donc de chercher t* le sommet qui minimise cette quantité :

t* in V | w(t*) = min(w(t), t in V)

Dans l'idée ça revient
1) à calculer Dijsktra depuis chaque sommet source
2) pour chaque sommet t candidat, calculer son coût (w(t))
3) chercher parmi ces éléments celui dont le coût est minimal

Et il y a sans doutes des approches plus efficaces que de calculer card(S) fois l'algorithme de Dijkstra.

Bonne chance

KX · Answer

Moi je me baserai (évidemment) sur un calcul de plus court chemin (Dijkstra ou autre) entre chaque couple de personnes (n personnes, n² chemins) pour trouver ceux qui sont le plus éloignés, vu que ce sont eux qui vont faire le plus de chemin, on peut prendre la ville qui est au milieu de ces deux extrêmes. 

Je pense aussi à une version récursive pour affiner le problème (pour prendre en compte la pondération par exemple)
À l'étape 0, on a n villes (car n personnes), pour chaque ville on détermine quelle est la ville la plus loin, et on considère son milieu. On se retrouve encore avec n villes milieux, mais de plus en plus proches les unes des autres. Donc au bout de quelques étapes on devrait se retrouver avec plusieurs fois la même ville, jusqu'à n'en avoir plus qu'une.La confiance n'exclut pas le contrôle

ccm81 · Answer

Bonjour à tous,

Une tentative d'approche graphique du point médian
Il est clair qu'il faudra peut être prendre des bottes pour se rendre sur les lieux!

https://www.cjoint.com/?3JuqitbJk7n 

bonne journée

Problème du point central

4 réponses

Votre réponse

Discussions similaires