Wie berechnet man die effizienteste Route, die durch alle Häuser der Welt führt?

52

Ich bin neu bei GIS.

Ich brauche Hilfe bei der Ermittlung der besten oder effizientesten Route mit einem fliegenden Schlitten durch alle Häuser der Welt. Einer meiner Mitarbeiter sagte mir, dass diese Seite der beste Ort für Fragen sei, da ich viele hilfreiche GIS-Experten finden würde.

Ich benötige eine Anleitung, welche Software verwendet werden soll, woher die Daten stammen und wie sie verarbeitet werden. Da ich diesen Monat einige zusätzliche Ausgaben hatte, würde ich einige Open Source-Lösungen vorziehen.

Danke euch allen!

PS: Ich habe es eilig, ich brauche das für morgen!

Weihnachtsmann
quelle
20
Dies ist im Grunde Travelling Salesman Problem, das, wenn Sie nicht bereit sind, eine Heuristik zu verwenden, hat n! Komplexität so viel Glück bei der Suche nach einer Lösung für so viele n, bevor das Universum endet ...
Smalltown2k
7
Warten Sie, seit wann bekommen nur christliche Kinder Besuche vom Weihnachtsmann?
Steve Bennett
4
Nehmen wir nur an, dass Herr Claus eine Liste von Hausschwellen hat, die zu besuchen sind und die konfessionslos bleibt. Danke :)
blah238
9
Muss diese Route auch am Nordpol beginnen? Geografischer Nordpol oder magnetischer Nordpol?
Spacedman
3
Damit. Der erste Schritt besteht darin, einen Datensatz für alle Wohnorte der Welt zu sammeln. Möchte jemand einen Dropbox-Link posten?
Simon

Antworten:

25

Warte, Rudolph weiß bestimmt, wohin er gehen muss. Er macht das schon seit Jahren.

Andrew
quelle
16

Oft ist es gut, auf das angegebene Bedürfnis einzugehen, anstatt die gestellte Frage zu beantworten. Ich möchte nur darauf hinweisen, dass es eine bekannte parallele Lösung gibt, die alle Probleme mit der technischen Datenverarbeitung übersichtlich umgeht: Der Weihnachtsmann hat Helfer. Diese Agenten arbeiten asynchron und unabhängig voneinander, um die zu besuchenden Häuser zu identifizieren und die Lieferungen durchzuführen. Es ist keine spezielle GIS-Berechnung von Seiten des Weihnachtsmanns erforderlich.

Es ist wunderbar, dass diese Technologie skaliert, so dass die (christliche) Weltbevölkerung im Laufe der Jahrtausende um mehrere Größenordnungen gewachsen ist und Santas Fähigkeit, seine Aufgaben zu erfüllen, nie ernsthaft in Zweifel gezogen wurde: Die Anzahl der verfügbaren Helfer ist gewachsen direkter Anteil an der Anzahl der Häuser, die besucht werden müssen.


Es gibt eine physische Demonstration der Existenz dieser Helfer. Wenn im Gegenteil nur eine Person versucht hätte, Geschenke an beispielsweise eine Milliarde Wohnungen im Laufe eines Kalendertages (48 Stunden in Zeitzonen) auszuliefern , müssten sie fast 6000 Wohnungen pro Sekunde besuchen . Eine Untergrenze für den mittleren Abstand zwischen Wohnungen ergibt sich aus der Dichte der größeren Städte der Welt, in denen die Menschen möglicherweise nur etwa 10 Meter voneinander entfernt leben. Dies würde eine Durchschnittsgeschwindigkeit von 6000 * 10 = 60.000 Meter pro Sekunde erfordern , die die Schallmauer bei weitem übertrifft (was zu Überschallknallen führt, die es nicht sind)Weihnachten gehört) und so viel atmosphärische Reibung erzeugt, dass der Schlitten zu einem lodernden Feuerball wird, der alles in seiner Nähe zerstört. Dies gibt uns zwar ein neues Verständnis für den Ursprung des roten Schimmers in Rudolphs Nase, zeigt jedoch deutlich, dass nur eine parallele Lösung möglich ist, QED.

whuber
quelle
1
Falls Sie nicht an die Helfer glauben, finden Sie hier den Beweis: en.wikipedia.org/wiki/Prep_%26_Landing
Tobias Kienzler
6

Dies können Sie wahrscheinlich mit dem Algorithmus von Warshal oder Dijkstra lösen

Obwohl die Anzahl der Häuser auf der Welt viel zu groß ist, würde es lange dauern, dies zu berechnen. Ich denke, dies ist ein guter Ausgangspunkt. Jetzt habe ich keine Zeit, sie zu erklären, aber ich gebe Ihnen einen ersten Punkt. Ich gehe jetzt mit meiner Familie aus und werde im nächsten Jahr vielleicht auf diese Frage zurückkommen.

Roger
quelle
4
Wir danken Ihnen für die freundlichen Worte. Aber: (1) Wie würde einer dieser Algorithmen das Problem des Handlungsreisenden lösen? (2) Der Dijkstra-Algorithmus (um kürzeste Wege zwischen zwei gegebenen Punkten in einem gegebenen Netzwerk zu finden ) ist schnell. Die Anwendung auf einen Datensatz aller Wohnungen der Welt wäre nicht nur machbar, sondern auch relativ schnell - und würde wahrscheinlich nur Sekunden oder Minuten dauern.
whuber
2

Sieht so aus, als hätte Google es bereits für Sie herausgefunden, Santa! Eigentlich solltest du gerade in Asien sein!

http://www.google.com/santatracker/

Matt
quelle
0

Mit einem Datensatz, der den Breiten- und Längengrad jeder Wohnung enthält (Volkszählungsdaten?), Würde ich möglicherweise die Haversine-Formel in der einen oder anderen Programmiersprache verwenden. Aber andererseits bin ich kein Elf.

Haversine-Formel

Natrix
quelle
Wenn Sie in der Luft sind, müssen Sie sicherlich die Rundheit der Erde und Ihre Höhe berücksichtigen.
Natrix