Discussion :

[betauser]

Bonjour,

J’espère être dans le bon forum.

Ci-dessous mon problème. Les recherches que j’ai faites m’on conduit vers le « problème du voyageur de commerce » mais je ne vois pas de lien évident.

Je connais la superficie d’un pays (ex : Finlande = 338 145 km2).
Je connais le nb de villes à visiter (ex : 7 villes). Mais je ne connais pas les villes ni leur situation géographique exacte. Je prends donc pour hypothèse que les villes sont uniformément réparties dans le pays.

A partir de ces infos, peut-on connaître la distance moyenne entre les 7 points ?
Est-ce qu’un outil de simulation existe (ex : feuille excel pour faire simple)?

Merci par avance pour toute information.

Cordialement,

[pseudocode]

bonjour,

hypothèse que les villes sont uniformément réparties dans le pays.

Le coeur de ton problème réside dans cette phrase. Les termes de Répartition, Distribution, Placement et ceux d' homogène, uniforme, équitable sont trompeurs.

Tel que tu décris ton problème, je vois plutot la recherche du plus grand rayon R permettant de placer, sans recouvrement, 7 cercles dans un carré/polygone de surface 338 145 km2

[Invité]

Bonjour,
La seule chose que l'on connaisse vraiment est le pays. Ce que je veux dire est que la forme du pays est une paramètre très important. Imaginez la différence de résultat en étudiant un pays comme le Chili et l'Allemagne.
Donc, dans votre formule, il doit y avoir un paramètre de "forme" qui peut être homogène à racine(aire)/périmètre.
Comme la méthode que vous adopterez est en partie subjective, le résultat sera toujours "à moitié juste ou à moitié faux", mais si les paramètres sont bien étudiés, les résultats seront toujours comparables entre eux.

[betauser]

Aie, moi qui pensais être clair...

Si je comprends bien ta reformulation, cela signifie qu'une zone de la surface ne sera sans doute pas couverte (cf mon dessin).

Alors si j'ai bien compris ta reformulation, je cherche effectivement le rayon le plus grand qui permet de placer les 7 cercles dans la surface de superficie donnée.

Et donc, un tel outil de calcul existe-t-il? Je renseigne l'aire de la surface et le nb de points et il me sort tout seul, comme un grand, le rayon des cercles?

PS: effectivement la "forme" de la surface a sans doute son importance. Dans un 1er temps, partons de l'hypothèse que nous avons un carré. En parallèle, est-ce toujours possible d'obtenir le rayon R si je décide de paramétrer la forme du rectangle (je définie 2 longeurs)?

Encore merci pour l'aide et la compréhension du sujet.

[pseudocode]

Et donc, un tel outil de calcul existe-t-il? Je renseigne l'aire de la surface et le nb de points et il me sort tout seul, comme un grand, le rayon des cercles?

A ma connaissance, il n'y a pas de formule exacte. Par contre il existe des approximations, voir meme des valeurs connues pour certains cas simples.

Cela s'appelle du Circle Packing

[Invité]

Pour m'expliquer, je vais donner un exemple:
Le lac de Genève (aussi appelé lac Léman) est sur la frontière entre la France et la Suisse. La définition de cette frontière (à part les extrémités) est que tout point de celle-ci, est le centre d'un cercle tangent aux rives françaises et suisses. Il se trouve que cette définition a été jugée un peu compliquée à appliquer et cette ligne a été remplacée par une ligne brisée de 4 ou 5 sommets.
Dans le cas qui nous intéresse, les villes sont uniformément réparties, cela peut-il se traduire "les villes sont les centres de cercles, tangents entre eux et tangent aux limites", non, je ne crois pas.
De toute façon, je ne crois pas qu'il puisse y avoir une formule.
Voila ce que le ferais.
J'appliquerais un maillage régulier à mailles carrées sur la surface. Le nombre de carrés sera N (compte tenu des bouts de carrés - cad N=S/s)
le nombre de carrés relatifs à une vile sera C=N/7 (cas présent).
Donc, en première approximation, la distance du centre d'un bloc de carrés à son bord sera 0.5 * racine(C).
Je pense que quelques essais permettront d'affiner le facteur 0.5, par exemple en tenant compte des "trous" entre les cercles, de la forme etc. D'ailleurs il est probable que ce paramètre puisse être fixé de façon très précise. Autrement dit, je suis presque sûr que sa valeur converge lorsqu'on diminue la taille des cases.

PS Très amusant les liens de pseudocode.

[Champialex]

Juste un détail, à propos de ton image, les cercles ne sont pas nécessairement entièrement dans le pays, seul leurs centres doivent l'être. Sinon, moi intuitivement j'aurais un fait un algo approximatif, genre un truc physique. Tu dis que tes n villes, c'est n particules qui se repoussent avec une force en 1/d²,
tu leur donnent une vitesse initiale aléatoire, tu met une force de frottement (pour que ton algo s'arrete) , et quand plus rien ne bouge, tu prend la distance moyenne que t'observe entre les villes, ca doit être pas trop loin de la vérité... Sinon regarde du coté de la cristallographie, ya surement des trucs qui ont déja été fait!

[pseudocode]

Juste un détail, à propos de ton image, les cercles ne sont pas nécessairement entièrement dans le pays, seul leurs centres doivent l'être. Sinon, moi intuitivement j'aurais un fait un algo approximatif, genre un truc physique. Tu dis que tes n villes, c'est n particules qui se repoussent avec une force en 1/d²,
tu leur donnent une vitesse initiale aléatoire, tu met une force de frottement (pour que ton algo s'arrete) , et quand plus rien ne bouge, tu prend la distance moyenne que t'observe entre les villes, ca doit être pas trop loin de la vérité... Sinon regarde du coté de la cristallographie, ya surement des trucs qui ont déja été fait!

Oui, construire un programme de simulation n'est pas très compliqué. Il faut voir si ca répond au problème initial qu'on ne connait pas.

Parce que le plus simple c'est quand meme de récupérer les coordonnées GPS des grandes villes d''un pays et de faire la moyenne des interdistances.