Знакомство с задачей коммивояжера на примере британских пабов

Когда-то в феврале я делала пост про то, как показать плотность точек на карте, и для него вспомнила примеры карт, которые утопали в символах точек. Один из них – рисунок, который встречается в интернете с подписью "карта всех пабов Великобритании" (внизу).

Когда я искала оригинал этой карты пабов, видела перепосты, под которым шотландцы писали, что для "карты всех пабов" на севере точек подозрительно мало. Когда я дошла до оригинала, оказалось, что здесь не все пабы Великобритании, как говорит подпись. Здесь меньше половины!

Оригинальную ошибку совершили авторы статьи The Guardian, откуда карта и разлетелась повсюду с неправильной подписью про "все пабы Великобритании". Потом автор статьи исправил ошибку, но смешной вид карты сделал свое дело.

А оригинал гораздо интереснее, чем просто карта пабов. Это решение математической проблемы — задачи коммивояжера.

Цель задачи коммивояжера — определить самый короткий маршрут между любым количеством точек и вернуться в начало. Такую проблему мы можем представить не только в абстрактной математике, но и в реальной жизни — например, когда курьеру нужно доставить товар поочередно в 20 домов и вернуться на склад.

Именно для того, чтобы решить такую проблему в невероятно большом масштабе, авторы исследования про пабы в 2016 году составили кратчайший маршрут между 24727 пабами Великобритании. Вот оригинальный маршрут без красных точек:

В 2015 году команда исследователей нанесла на карту координаты 24727 пабов с сайта "Pubs Galore" и начала считать кратчайший маршрут между ними, который возвращается в начальную точку. После "тонны математики и 10 месяцев работы" (слова авторов) получился оптимальный маршрут, который они опубликовали на интерактивной карте Google Maps. Это линия длиной 45 495 239 метров, и нет ни одного маршрута хотя бы на метр короче. На тот день это было одно из самых масштабных решений задачи коммивояжера. Впечатляет!

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

Дело в том, что когда авторы собирали данные, они рассчитали, что лучше ограничиться разумным количеством: 25 000 точек, а иначе их алгоритмы и компьютеры не потянут эту задачу. Поэтому они отфильтровали базу "Pubs Galore" и отбросили все заведения с "Hotel" или "Inn" в названии. Фильтрация особенно сказалась на Шотландии.

В ответ на многочисленные жалобы исследователи сказали: "вызов принят", и начали еще более масштабную работу, теперь уже со всеми пабами страны. Им потребовалось еще полтора года работы, и теперь для всех желающих хорошо провести время есть самый короткий пеший тур по 49 687 пабам Великобритании. Его протяженность — 63 739 687 метров, и не существует более короткого решения.

Как вообще решаются такие проблемы? Нельзя проверить расстояния всех маршрутов вручную: комбинаторика подсказывает, что для 25000 точек их количество приближается к безбожным масштабам. По оценке Washington Post даже для задачи с 22 точками обычный компьютер не в состоянии перебрать все маршруты один за другим в течение человеческой жизни.

Но посмотрим на проблему иначе: если нам нужно расставить 50 слов в алфавитном порядке, мы не перебираем все возможные варианты подряд, а сортируем слова по группам. Для задачи коммивояжера мы не можем так же сортировать локации, и тем не менее математика может помочь. Например, мы можем выбрать пару пабов и рассматривать сначала только варианты, в которых эти два паба посещаются последовательно, а затем только те, в которых есть хотя бы один другой паб между ними. Такой выбор делит множество всех маршрутов на два подмножества, и таким образом мы можем сократить общее количество маршрутов до тех, в которых есть "оптимальные" кусочки.

На самом деле алгоритмы сложнее и я не берусь про них писать подробнее, но такое начало уже делает часть математики понятнее. Чтобы узнать больше, читайте ссылки внизу статьи :)

Задача коммивояжера с британскими пабами — это далеко не бесполезный проект. Она важна как средство для разработки и тестирования методов оптимизации, которые применяются в разных науках, промышленности и торговле. При переходе от ~25000 точек к ~50000 точек исследователи сами обнаружили новые алгоритмы оптимизации, которые продолжили применять и в других работах.

Конечно же, они не остановились на пабах и продолжили решать и другие подобные задачи, например, задачу исторического тура по США с 49603 остановками. А потом продолжили исследования в трехмерном пространстве и взялись за вычисления кратчайшего расстояния между миллионами звезд. Математики могут и такое!

Оставляю здесь и источники информации, и дополнительные ссылки, которые понравились мне, но не вошли в статью: