Как рассчитать наиболее эффективный маршрут, проходящий через все дома в мире?

52

Я новичок в ГИС.

Мне нужна помощь в определении лучшего или наиболее эффективного маршрута, используя летающие сани, через все дома в мире. Один из моих коллег сказал мне, что этот сайт будет лучшим местом, чтобы спросить, потому что я найду много полезных экспертов ГИС.

Мне понадобятся некоторые рекомендации о том, какое программное обеспечение использовать, где брать данные и как их обрабатывать. Поскольку в этом месяце у меня были некоторые дополнительные расходы, я бы предпочел некоторые решения с открытым исходным кодом.

Спасибо вам всем!

PS: я немного тороплюсь, так как мне нужно это на завтра!

Санта Клаус
источник
20
Это в основном проблема коммивояжера, которая, если вы не хотите использовать эвристику, имеет n! Сложность, так что удачи в поиске любого решения для такого большого числа n до конца вселенной ...
Smalltown2k
7
Подождите, с каких это пор только дети-христиане посещают Санту?
Стив Беннетт
4
Давайте просто предположим, что у мистера Клауса есть список домовладений, которые нужно посетить, и оставьте его неденоминационным. Спасибо :)
blah238
9
Этот маршрут также ограничен для начала на Северном полюсе? Северный географический полюс или северный магнитный полюс?
Spacedman
3
Так. Первый шаг - собрать набор данных для всех мест обитания в мире. Кто-нибудь хочет опубликовать ссылку в Dropbox?
Саймон

Ответы:

25

Держись, конечно, Рудольф знает, куда идти. Он делал это годами.

Андрей
источник
16

Часто полезно удовлетворить заявленную потребность, а не ответить на заданный вопрос. Я хотел бы только отметить, что существует хорошо известное параллельное решение, которое аккуратно обходит все технические вычислительные проблемы: у Санты есть помощники. Эти агенты работают асинхронно и независимо, идентифицируя дома, которые нуждаются в посещениях, и осуществляют доставку. Никаких специальных вычислений ГИС со стороны Санты не требуется.

Удивительно, что эта технология масштабируется, так что в течение тысячелетий мировое (христианское) население увеличилось на несколько порядков, способность Санты выполнять свои обязанности никогда не подвергалась серьезному сомнению: число доступных помощников росло в прямо пропорционально количеству домов, которые нужно посетить.


Существует физическая демонстрация существования этих помощников. Если предположить обратное, то только один человек пытался доставить подарки, скажем, одному миллиарду жилищ в течение календарного дня (который охватывает 48 часов, учитывая часовые пояса), ему пришлось бы посещать почти 6000 жилищ в секунду. , Нижняя граница для среднего расстояния между жилищами определяется плотностью крупных городов мира, в которых люди могут жить на расстоянии около 10 метров друг от друга. Для этого потребуется средняя скорость 6000 * 10 = 60000 метров в секунду, намного превосходящая звуковой барьер (создавая звуковые удары, которые неСлышно на Рождество) и создает настолько сильное атмосферное трение, что сани превращаются в пылающий огненный шар, разрушающий все вокруг. Хотя это дает нам новое понимание происхождения красного свечения в носу Рудольфа, оно ясно демонстрирует, что возможно только параллельное решение, КЭД.

Whuber
источник
1
Если вы не верите в помощников, вот доказательство: en.wikipedia.org/wiki/Prep_%26_Landing
Тобиас Кинцлер
6

Это то , что вы , вероятно , можно решить с помощью этого Warshal в или Дейкстры алгоритм

Хотя количество домов в мире слишком велико, для его вычисления потребовалось бы много времени, я думаю, что это хорошая начальная точка. Теперь у меня нет времени, чтобы объяснить их, но я дам вам начальную точку. Я сейчас пойду с семьей и, возможно, вернусь к этому вопросу в следующем году.

Роджер
источник
4
Спасибо за добрые слова. Но: (1) Как любой из этих алгоритмов решит эту проблему коммивояжера? (2) Алгоритм Дейкстры (чтобы найти кратчайшие пути между двумя заданными точками в данной сети ) является быстрым. Применение его к набору данных всех жилищ в мире, если бы оно было соответствующим образом сокращено, чтобы включать ребра только для нескольких ближайших соседей каждого жилища, было бы не только осуществимым, но и достаточно быстрым - вероятно, потребовав всего несколько секунд или минут вычислений.
whuber
0

С набором данных, содержащим широту и долготу каждого жилища (данные переписи?), Я бы, возможно, использовал формулу Хаверсайна в одном или другом языке программирования. Но опять же, я не эльф.

Формула Haversine

Natrix
источник
Если вы находитесь в воздухе, вам наверняка придется учитывать округлость Земли и вашу высоту.
Natrix