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

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!

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

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.

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.

Wygląda na to, że Google już to wymyślił, Święty Mikołaj! W tej chwili powinieneś być w Azji!

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

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