Traveling Salesman
Найдите кратчайший маршрут, проходящий через каждый город один раз · классическая задача коммивояжёра
О задаче коммивояжера
«Задача коммивояжера» · это небольшая головоломка по оптимизации маршрута, основанная на одной из самых известных проблем в информатике · задаче коммивояжера (TSP). Несколько городов разбросаны по карте, и вы начинаете из дома. Ваша задача · спланировать маршрут, который посетит каждый город ровно один раз и вернется домой, используя кратчайшее возможное общее расстояние. Нажимайте на города в том порядке, в котором вы бы их проехали, и маршрут будет строиться сам; счетчик расстояния в реальном времени покажет длину вашего маршрута.
Почему это тренирует ваш мозг. Нахождение кратчайшего маршрута · это чистое пространственное мышление и планирование · вам нужно сравнивать целые порядки друг с другом, замечать, когда маршрут пересекается сам с собой и тратит лишнее расстояние, и искать такое расположение, которое невозможно превзойти. Нет формулы для применения; вы рассуждаете о геометрии напрямую, что является именно тем видом оптимизационного мышления, которым прославилась TSP.
Совпадение с оптимумом для победы. Каждая карта решается точно за кулисами, поэтому раунд считается выигрышем только тогда, когда ваш маршрут совпадает с истинным кратчайшим путем · одинаково короткие маршруты все засчитываются. Если ваш маршрут длиннее, игра покажет оптимальный маршрут поверх вашего, чтобы вы могли увидеть пересечение, которое вы должны были распутать.
Карта растет по мере вашего продвижения. Ранние раунды состоят из четырех или пяти городов · достаточно короткие, чтобы их можно было оценить на глаз. Каждые несколько уровней на карте появляется еще один город, и каждая дополнительная остановка умножает количество возможных маршрутов, поэтому найти кратчайший маршрут становится сложнее по мере увеличения вашей серии побед.
Часть семейства игр для тренировки мозга PlayMemorize. Полностью работает в вашем браузере, работает в автономном режиме как прогрессивное веб-приложение.
FAQ
-
Как играть в «Задачу коммивояжера»?
Вы начинаете с домашней отметки. Нажимайте на другие города один за другим в том порядке, в котором вы бы их посетили · маршрут строится по мере вашего продвижения, и счетчик расстояния обновляется. Как только каждый город будет на маршруте, нажмите «Проверить». Если ваш маршрут совпадает с кратчайшим возможным маршрутом, вы выигрываете раунд. -
Что такое задача коммивояжера?
Это классическая задача оптимизации: имея набор городов, найти кратчайший возможный маршрут, который посещает каждый из них ровно один раз и возвращается к началу. Она известна своей сложностью, потому что количество возможных маршрутов экспоненциально увеличивается с добавлением городов · эта игра позволяет вам решать небольшие, разрешимые экземпляры вручную. -
Как игра узнает, что маршрут оптимален?
Каждая карта достаточно мала, чтобы игра вычисляла точный кратчайший маршрут, проверяя все возможные порядки. Ваш маршрут выигрывает, когда его длина совпадает с этим оптимумом. Если два разных маршрута имеют одинаковую кратчайшую длину, любой из них считается выигрышем. -
Что произойдет, если мой маршрут не является кратчайшим?
Раунд засчитывается как проигрыш, и игра рисует истинный оптимальный маршрут поверх вашего, чтобы вы могли сравнить. Ищите места, где ваш маршрут пересекается сам с собой · распутывание почти всегда сокращает маршрут. Используйте «Отменить», чтобы удалить последний город, или «Очистить», чтобы начать маршрут заново. -
Становится ли игра сложнее по мере прохождения?
Да. Каждый успешный раунд повышает ваш уровень, и каждые несколько уровней на карте появляется еще один город. Поскольку каждая дополнительная остановка резко увеличивает количество возможных маршрутов, кратчайший маршрут становится все труднее найти по мере увеличения вашей серии побед. -
Работает ли игра в автономном режиме?
Да. PlayMemorize · это прогрессивное веб-приложение. Установите один раз, и «Задача коммивояжера» будет работать где угодно без подключения к интернету.