Время прочтения: 4 минуты
Когда-то в феврале я делала пост про то, как показать плотность точек на карте, и для него вспомнила примеры карт, которые утопали в символах точек. Один из них – рисунок, который встречается в интернете с подписью "карта всех пабов Великобритании" (внизу).
Когда я искала оригинал этой карты пабов, видела перепосты, под которым шотландцы писали, что для "карты всех пабов" на севере точек подозрительно мало. Когда я дошла до оригинала, оказалось, что здесь не все пабы Великобритании, как говорит подпись. Здесь меньше половины!
Оригинальную ошибку совершили авторы статьи The Guardian, откуда карта и разлетелась повсюду с неправильной подписью про "все пабы Великобритании". Потом автор статьи исправил ошибку, но смешной вид карты сделал свое дело.
А оригинал гораздо интереснее, чем просто карта пабов. Это решение математической проблемы — задачи коммивояжера.
Задача коммивояжера
Цель задачи коммивояжера — определить самый короткий маршрут между любым количеством точек и вернуться в начало. Такую проблему мы можем представить не только в абстрактной математике, но и в реальной жизни — например, когда курьеру нужно доставить товар поочередно в 20 домов и вернуться на склад.
Именно для того, чтобы решить такую проблему в невероятно большом масштабе, авторы исследования про пабы в 2016 году составили кратчайший маршрут между 24727 пабами Великобритании. Вот оригинальный маршрут без красных точек:
Полный размер по ссылке. Это не все пабы Великобритании, потому что со всеми не справился бы компьютер исследователей. Источник: math.uwaterloo.ca
В 2015 году команда исследователей нанесла на карту координаты 24727 пабов с сайта "Pubs Galore" и начала считать кратчайший маршрут между ними, который возвращается в начальную точку. После "тонны математики и 10 месяцев работы" (слова авторов) получился оптимальный маршрут, который они опубликовали на интерактивной карте Google Maps. Это линия длиной 45 495 239 метров, и нет ни одного маршрута хотя бы на метр короче. На тот день это было одно из самых масштабных решений задачи коммивояжера. Впечатляет!
Именно эта карта разлетелась в виде смешной картинки с кучей точек и подписью "карта всех пабов Великобритании", и сразу же после публикации авторам начали поступать тысячи комментариев и писем. В основном письма были о том, что ученые, похоже, налажали. Особенно негодовали шотландцы, потому что многих шотландских пабов на карте не оказалось.
Дело в том, что когда авторы собирали данные, они рассчитали, что лучше ограничиться разумным количеством: 25 000 точек, а иначе их алгоритмы и компьютеры не потянут эту задачу. Поэтому они отфильтровали базу "Pubs Galore" и отбросили все заведения с "Hotel" или "Inn" в названии. Фильтрация особенно сказалась на Шотландии.
В ответ на многочисленные жалобы исследователи сказали: "вызов принят", и начали еще более масштабную работу, теперь уже со всеми пабами страны. Им потребовалось еще полтора года работы, и теперь для всех желающих хорошо провести время есть самый короткий пеший тур по 49 687 пабам Великобритании. Его протяженность — 63 739 687 метров, и не существует более короткого решения.
Как посмотреть маршрут:
- Полная картинка маршрута и она же в хорошем качестве
- 39-секундное видео маршрута
- Интерактивная карта (осторожно, от большого количества точек у этой карты есть проблемы).
Оптимальность и математика
Как вообще решаются такие проблемы? Нельзя проверить расстояния всех маршрутов вручную: комбинаторика подсказывает, что для 25000 точек их количество приближается к безбожным масштабам. По оценке Washington Post даже для задачи с 22 точками обычный компьютер не в состоянии перебрать все маршруты один за другим в течение человеческой жизни.
Но посмотрим на проблему иначе: если нам нужно расставить 50 слов в алфавитном порядке, мы не перебираем все возможные варианты подряд, а сортируем слова по группам. Для задачи коммивояжера мы не можем так же сортировать локации, и тем не менее математика может помочь. Например, мы можем выбрать пару пабов и рассматривать сначала только варианты, в которых эти два паба посещаются последовательно, а затем только те, в которых есть хотя бы один другой паб между ними. Такой выбор делит множество всех маршрутов на два подмножества, и таким образом мы можем сократить общее количество маршрутов до тех, в которых есть "оптимальные" кусочки.
На самом деле алгоритмы сложнее и я не берусь про них писать подробнее, но такое начало уже делает часть математики понятнее. Чтобы узнать больше, читайте ссылки внизу статьи :)
Куда дальше?
Задача коммивояжера с британскими пабами — это далеко не бесполезный проект. Она важна как средство для разработки и тестирования методов оптимизации, которые применяются в разных науках, промышленности и торговле. При переходе от ~25000 точек к ~50000 точек исследователи сами обнаружили новые алгоритмы оптимизации, которые продолжили применять и в других работах.
Конечно же, они не остановились на пабах и продолжили решать и другие подобные задачи, например, задачу исторического тура по США с 49603 остановками. А потом продолжили исследования в трехмерном пространстве и взялись за вычисления кратчайшего расстояния между миллионами звезд. Математики могут и такое!
Источники информации и дополнительные ссылки
Оставляю здесь и источники информации, и дополнительные ссылки, которые понравились мне, но не вошли в статью:
- Описание решения задачи с 24727 пабами и обновленное описание решения задачи с 49687 пабами — это основные источники для статьи.
- Та самая статья The Guardian, которая изначально вышла с неправильной подписью.
- Information, Computation, Optimization: Connecting the Dots in the Traveling Salesman Problem — видео на тему математической оптимизации от одного из авторов исследования. Это ссылка для тех, кто хотел бы больше узнать про математику внутри итогового маршрута.
- Статья "Задача коммивояжера" на Википедии никак не вошла в этот пост, но там много информации для интересующихся.
- История решения задачи коммивояжера тоже не вошла в эту статью, но мне было очень интересно ее читать.
Материал подготовила Юлия Федорова