Comment calculer l'itinéraire le plus efficace passant par toutes les maisons du monde?

52

Je suis nouveau dans les SIG.

J'ai besoin d'aide pour déterminer l'itinéraire le plus efficace ou le plus efficace, en traîneau volant, dans toutes les maisons du monde. Un de mes collègues m'a dit que ce site serait le meilleur endroit pour poser des questions, car je trouverais de nombreux experts en SIG utiles.

J'aurai besoin de conseils sur le logiciel à utiliser, où obtenir les données et comment les traiter. Depuis que j'ai eu des dépenses supplémentaires ce mois-ci, je préférerais des solutions Open Source.

Merci à tous!

PS: Je suis un peu pressé, car j'en ai besoin pour demain!

père Noël
la source
20
Il s’agit essentiellement d’un problème de voyageur de commerce qui, à moins que vous ne souhaitiez utiliser une heuristique, a n! complexité donc bonne chance pour trouver une solution pour que beaucoup n avant la fin de l'univers ...
Smalltown2k
7
Attendez, depuis quand seulement les enfants chrétiens ont-ils des visites du père Noël?
Steve Bennett
4
Supposons simplement que M. Claus a une liste de maisons à visiter et qu’elle reste non confessionnelle. Merci :)
blah238
9
Cette route est-elle également contrainte de commencer au pôle Nord? Pôle géographique nord ou pôle magnétique nord?
Spacedman
3
Alors. La première étape consiste à rassembler un ensemble de données pour tous les lieux d’habitation du monde. Quelqu'un veut-il publier un lien vers une boîte de dépôt?
Simon

Réponses:

25

Accrochez-vous bien Rudolph sait où aller. Il le fait depuis des années.

Andrew
la source
16

Il est souvent bon de répondre au besoin énoncé plutôt que de répondre à la question posée. Je voudrais seulement souligner qu’il existe une solution parallèle bien connue qui élimine parfaitement tous les problèmes techniques informatiques: le Père Noël a des aides. Ces agents travaillent de manière asynchrone et indépendante pour identifier les maisons qui ont besoin de visites et effectuer les livraisons. Aucun calcul SIG spécial de la part du père Noël n'est nécessaire.

Il est merveilleux que cette technologie évolue, de sorte qu'au fur et à mesure que la population (chrétienne) mondiale a augmenté de plusieurs ordres de grandeur au cours des millénaires, la capacité du Père Noël à exercer ses fonctions n'a jamais été sérieusement mise en doute: le nombre de collaborateurs disponibles a augmenté proportion directe avec le nombre de maisons ayant besoin de visites.


Il existe une démonstration physique de l'existence de ces aides. Si, à supposer le contraire, un seul individu essayait de donner des cadeaux à, par exemple, un milliard d'habitations au cours d'une journée calendaire (qui s'étend sur 48 heures, en tenant compte des fuseaux horaires), il devrait visiter près de 6000 habitations par seconde. . La densité inférieure des grandes villes du monde, dans laquelle les habitants ne vivent qu’à une dizaine de mètres de distance, offre une limite inférieure pour la distance moyenne entre les logements. Cela nécessiterait une vitesse moyenne de 6000 * 10 = 60 000 mètres par seconde, dépassant de loin le mur du son (créant des bangs soniques qui ne sont pasentendu à Noël) et créer tant de frictions atmosphériques que le traîneau deviendrait une boule de feu ardente détruisant tout ce qui se trouve à proximité. Bien que cela nous donne une nouvelle compréhension de l'origine de la lueur rouge dans le nez de Rudolph, cela démontre clairement que seule une solution parallèle est même possible, la QED.

whuber
la source
1
Au cas où vous ne croiriez pas aux assistants, voici la preuve: fr.wikipedia.org/wiki/Prep_%26_Landing
Tobias Kienzler
6

Ceci est quelque chose que vous pouvez probablement résoudre en utilisant les de Warshal ou de Dijkstra algorithme

Bien que le nombre de maisons dans le monde soit bien trop important, il faudrait beaucoup de temps pour le calculer, mais je pense que c'est un bon point de départ. Maintenant, je n'ai pas le temps de les expliquer, mais je vous donne un premier point. Je sors maintenant avec ma famille et je reviendrai peut-être sur cette question l'année prochaine.

Roger
la source
4
Merci pour les mots gentils. Mais: (1) Comment l'un ou l'autre de ces algorithmes résoudrait-il ce problème de voyageur voyageur? (2) L'algorithme de Dijkstra (pour trouver les chemins les plus courts entre deux points donnés d'un réseau donné ) est rapide. L’appliquer à un ensemble de données de toutes les habitations du monde, s’il était convenablement taillé de manière à n’inclure les arêtes que de plusieurs voisins proches de chaque habitation, serait non seulement faisable, mais raisonnablement rapide - ne nécessitant probablement que quelques secondes ou minutes de calcul.
whuber
0

Avec un jeu de données contenant la latitude et la longitude de chaque logement (données de recensement?), J'utiliserais peut-être la formule de Haversine dans un langage de programmation ou un autre. Mais là encore, je ne suis pas un elfe.

Formule Haversine

Natrix
la source
Si vous êtes dans les airs, vous devrez sûrement prendre en compte la rondeur de la terre et votre altitude.
Natrix