Bagaimana cara menghitung rute paling efisien melewati semua rumah di dunia?

52

Saya baru mengenal GIS.

Saya butuh bantuan dalam menentukan rute terbaik atau paling efisien, menggunakan giring terbang, melalui semua rumah di dunia. Salah satu rekan kerja saya mengatakan kepada saya bahwa situs ini akan menjadi tempat terbaik untuk bertanya, karena saya akan menemukan banyak pakar SIG yang membantu.

Saya akan memerlukan beberapa panduan tentang perangkat lunak apa yang digunakan, di mana mendapatkan data, dan bagaimana memprosesnya. Karena saya memiliki beberapa pengeluaran tambahan bulan ini, saya lebih suka beberapa solusi Open Source.

Terima kasih semua!

PS: Saya agak terburu-buru, karena saya butuh ini untuk besok!

Sinterklas
sumber
20
Ini pada dasarnya adalah Traveling Salesman Problem yang kecuali Anda mau menggunakan heuristik, tidak ada! kompleksitas begitu semoga beruntung menemukan solusi apa pun untuk sebanyak itu sebelum alam semesta berakhir ...
Smalltown2k
7
Tunggu, sejak kapan hanya anak-anak Kristen yang mendapat kunjungan Santa?
Steve Bennett
4
Mari kita asumsikan bahwa Pak Claus memiliki daftar ibu rumah tangga untuk dikunjungi dan menjaganya agar tidak bersifat denominasi. Terima kasih :)
blah238
9
Apakah rute ini juga dibatasi untuk memulai di kutub Utara? Kutub geografis utara, atau kutub magnet utara?
Spacedman
3
Begitu. Langkah pertama adalah mengumpulkan dataset untuk semua lokasi tempat tinggal untuk Dunia. Adakah yang mau memposting tautan dropbox?
Simon

Jawaban:

25

Tunggu sebentar, Rudolph tahu ke mana harus pergi. Dia sudah melakukannya selama bertahun-tahun.

Andrew
sumber
16

Seringkali lebih baik untuk menjawab kebutuhan yang dinyatakan daripada menjawab pertanyaan yang diajukan. Saya hanya ingin menunjukkan bahwa ada solusi paralel yang terkenal yang dengan rapi menghindari semua masalah komputasi teknis: Santa memiliki pembantu. Agen-agen ini bekerja secara sinkron dan independen untuk mengidentifikasi rumah-rumah yang perlu dikunjungi dan melakukan pengiriman. Tidak diperlukan perhitungan GIS khusus pada bagian Santa.

Sungguh luar biasa bahwa teknologi ini berskala, sehingga ketika populasi dunia (Kristen) telah bertambah beberapa kali lipat selama ribuan tahun, kemampuan Santa untuk melaksanakan tugasnya tidak pernah secara serius diragukan: jumlah pembantu yang tersedia telah bertambah di proporsi langsung dengan jumlah rumah yang perlu dikunjungi.


Ada demonstrasi fisik tentang keberadaan para pembantu ini. Jika, untuk mengasumsikan sebaliknya, hanya satu orang yang mencoba mengirimkan hadiah kepada, katakanlah, satu miliar tempat tinggal selama satu hari kalender (yang mencakup 48 jam, dengan memperhitungkan zona waktu), mereka harus mengunjungi hampir 6000 tempat tinggal per detik . Batas bawah untuk jarak rata-rata antara tempat tinggal diberikan oleh kepadatan kota-kota besar di dunia, di mana orang dapat hidup hanya sekitar 10 meter. Ini akan membutuhkan kecepatan rata - rata 6000 * 10 = 60.000 meter per detik, jauh melampaui penghalang suara (menciptakan ledakan sonik yang tidakterdengar pada Natal) dan menciptakan gesekan atmosfer yang begitu banyak sehingga giring akan menjadi bola api yang menghancurkan segala sesuatu di dekatnya. Meskipun ini memberi kita pemahaman baru tentang asal-usul sinar merah di hidung Rudolph, itu jelas menunjukkan bahwa hanya solusi paralel yang mungkin dilakukan, QED.

whuber
sumber
1
Jika Anda tidak percaya pada pembantu, inilah buktinya: en.wikipedia.org/wiki/Prep_%26_Landing
Tobias Kienzler
6

Ini adalah sesuatu yang Anda mungkin dapat memecahkan dengan menggunakan Warshal ini atau Dijkstra algoritma

Meskipun jumlah rumah di dunia terlalu besar, butuh waktu lama untuk menghitungnya, saya pikir ini adalah titik awal yang baik. Sekarang saya tidak punya waktu untuk menjelaskannya tetapi saya memberi Anda poin awal. Saya akan pergi dengan keluarga saya sekarang dan mungkin saya akan kembali ke pertanyaan ini tahun depan.

Roger
sumber
4
Terima kasih atas kata-kata baiknya. Tetapi: (1) Bagaimana salah satu dari algoritma tersebut akan menyelesaikan masalah salesman keliling ini? (2) Algoritma Dijkstra (untuk menemukan jalur terpendek antara dua titik yang diberikan dalam jaringan tertentu ) cepat. Menerapkannya ke set data dari semua tempat tinggal di dunia, jika dipangkas dengan tepat memasukkan tepi hanya ke beberapa tetangga terdekat dari masing-masing tempat tinggal, tidak hanya layak, tetapi cukup cepat - mungkin hanya membutuhkan hitungan detik atau menit perhitungan.
Whuber
0

Dengan dataset yang berisi garis lintang dan bujur dari setiap hunian (data sensus?), Saya mungkin akan menggunakan rumus Haversine dalam satu bahasa pemrograman atau lainnya. Tapi sekali lagi, aku bukan peri.

Formula Haversine

Natrix
sumber
Jika Anda berada di udara, Anda tentu harus mempertimbangkan kebulatan bumi dan ketinggian Anda.
Natrix