Jak obliczyć najbardziej wydajną trasę przechodzącą przez wszystkie domy na świecie?

52

Jestem nowy w GIS.

Potrzebuję pomocy w określeniu najlepszej lub najbardziej wydajnej trasy, przy użyciu latających sań, przez wszystkie domy na świecie. Jeden z moich współpracowników powiedział mi, że ta strona będzie najlepszym miejscem do zapytania, ponieważ znajdę wielu pomocnych ekspertów GIS.

Potrzebuję wskazówek dotyczących tego, jakiego oprogramowania użyć, gdzie uzyskać dane i jak je przetwarzać. Ponieważ w tym miesiącu miałem dodatkowe wydatki, wolałbym niektóre rozwiązania Open Source.

Dziękuję wam wszystkim!

PS: Trochę mi się spieszy, bo potrzebuję tego na jutro!

Święty Mikołaj
źródło
20
Jest to w zasadzie problem Traveling Salesman, który, o ile nie chcesz użyć heurystyki, ma n! złożoność, więc powodzenia w znalezieniu rozwiązania dla tylu n, zanim wszechświat się skończy ...
Smalltown2k
7
Poczekaj, od kiedy tylko chrześcijańskie dzieci odwiedzają Świętego Mikołaja?
Steve Bennett,
4
Załóżmy po prostu, że Pan Mikołaj ma listę gospodarstw domowych do odwiedzenia i nie ma żadnej denominacji. Dzięki :)
blah238,
9
Czy ta trasa jest również ograniczona do startu na biegunie północnym? Północny biegun geograficzny czy północny biegun magnetyczny?
Spacedman
3
Więc. Pierwszym krokiem jest zebranie zestawu danych dla wszystkich lokalizacji mieszkaniowych na świecie. Czy ktoś chce opublikować link do Dropbox?
Simon

Odpowiedzi:

25

Poczekaj, na pewno Rudolph wie, gdzie iść. Robi to od lat.

Andrzej
źródło
16

Często dobrze jest odpowiedzieć na zgłoszoną potrzebę, a nie odpowiedzieć na zadane pytanie. Chciałbym tylko zaznaczyć, że istnieje dobrze znane równoległe rozwiązanie, które starannie omija wszystkie techniczne problemy komputerowe: Święty Mikołaj ma pomocników. Agenci ci pracują asynchronicznie i niezależnie, aby zidentyfikować domy wymagające wizyt i zrealizować dostawy. Żadne specjalne obliczenia GIS ze strony Świętego Mikołaja nie są potrzebne.

To cudowne, że technologia ta jest skalowana, tak że wraz z powiększaniem się populacji (chrześcijańskiej) o kilka rzędów wielkości w ciągu tysiącleci, zdolność Świętego Mikołaja do wykonywania swoich obowiązków nigdy nie była poważnie wątpliwa: liczba dostępnych pomocników wzrosła bezpośredni stosunek do liczby domów, które wymagają wizyt.


Istnieje fizyczna demonstracja istnienia tych pomocników. Jeśli przeciwnie, tylko jedna osoba próbowałaby dostarczyć prezenty, powiedzmy, miliardowi mieszkań w ciągu dnia kalendarzowego (który obejmuje 48 godzin, uwzględniając strefy czasowe), musieliby odwiedzić prawie 6000 mieszkań na sekundę . Dolną granicę średniej odległości między mieszkaniami zapewnia gęstość większych miast na świecie, w których ludzie mogą mieszkać w odległości około 10 metrów od siebie. Wymagałoby to średniej prędkości 6000 * 10 = 60 000 metrów na sekundę, znacznie przekraczając barierę dźwiękową (tworząc boom dźwiękowy, który nie jestsłyszane w Boże Narodzenie) i powodując tak duże tarcie atmosferyczne, że sanie zamieniłyby się w płonącą kulę ognia niszczącą wszystko w pobliżu. Chociaż daje nam to nowe zrozumienie pochodzenia czerwonej poświaty w nosie Rudolfa, wyraźnie pokazuje, że możliwe jest nawet równoległe rozwiązanie, QED.

Whuber
źródło
1
Jeśli nie wierzysz w pomocników, oto dowód: en.wikipedia.org/wiki/Prep_%26_Landing
Tobias Kienzler
6

Jest to coś, co prawdopodobnie można rozwiązać za pomocą algorytmu Warshal lub Dijkstry

Chociaż liczba domów na świecie jest o wiele za duża, obliczenie tego zajęłoby dużo czasu, ale myślę, że to dobry początek. Teraz nie mam czasu, aby je wyjaśnić, ale dam ci wstępny punkt. Wyjdę teraz z rodziną i może wrócę do tego pytania w przyszłym roku.

zrozumiałem
źródło
4
Dziękuję za miłe słowa. Ale: (1) W jaki sposób którykolwiek z tych algorytmów rozwiązałby ten problem podróżnego sprzedawcy? (2) Algorytm Dijkstry (znajdowanie najkrótszych ścieżek między dwoma danymi punktami w danej sieci ) jest szybki. Zastosowanie go do zbioru danych wszystkich mieszkań na świecie, gdyby odpowiednio przycięto, aby zawierało krawędzie tylko kilku najbliższych sąsiadów każdego mieszkania, byłoby nie tylko wykonalne, ale i dość szybkie - prawdopodobnie wymagałoby tylko kilku sekund lub minut obliczeń.
whuber
0

Z zestawem danych zawierającym szerokość i długość geograficzną każdego mieszkania (dane spisu?), Może użyłbym formuły Haversine w tym czy innym języku programowania. Ale z drugiej strony nie jestem elfem.

Formuła Haversine

Natrix
źródło
Jeśli jesteś w powietrzu, z pewnością musisz wziąć pod uwagę okrągłość ziemi i wysokość.
Natrix