Как стать мастером Путешественника
КРАТКО: Путешественник просит вас посетить каждый город ровно один раз и вернуться домой по самой короткой петле. Нажимайте на города в порядке, нажимайте Проверка, когда все будут на маршруте, и выигрывайте только тогда, когда ваше расстояние совпадает с истинным оптимумом. Игра показывает оптимальный маршрут, когда вы проигрываете, так что изучайте его - самопересекающиеся маршруты почти всегда являются виновниками, и их развязывание сокращает тур.
То, что вы действительно решаете
Путешественник - это мини-версия одной из самых знаменитых проблем в области компьютерных наук. Вы начинаете на маркере дома на рассеянной карте городов. Ваша задача проста в заявлении и действительно сложна в решении: посетите каждый город ровно один раз, а затем вернитесь домой, используя самую короткую возможную общую дистанцию. Нет формулы, нет сокращений - вы должны напрямую размышлять о геометрии и сравнивать целые маршруты друг с другом, пока не найдете тот, который не может быть превзойден.
Игра показывает вам расстояние вашего текущего тура в режиме реального времени, когда вы нажимаете. Как только все города посещены, нажмите Проверка. Если ваша петля совпадает с истинным оптимальным решением, вы выигрываете и переходите на следующий уровень. Если она длиннее, вы увидите истинный самый короткий маршрут, наложенный на ваш собственный - самый ценный момент в игре. Это мгновенное визуальное сравнение показывает вам точно, где вы ошиблись.
То, что делает игру свежей, - это рост. Каждые несколько уровней карта получает еще один город. Пять городов становятся шестью, а затем семерыми. Каждое добавление кажется небольшим, но количество возможных порядков умножается драматически. То, что вы могли бы угадать на уровне один, становится настоящей проблемой оптимизации к уровню десять.
Правила в полном объеме
Начните с изучения карты. Вы увидите маркер дома (вашу точку начала и окончания) и другие города, рассеянные вокруг него. Ваш маршрут всегда начинается и заканчивается дома - вы нажимаете только на недомашние города, которые образуют петлю.
Нажимайте на города в том порядке, в котором вы бы посетили их. Маршрут рисует себя как линия, соединяющая каждый нажатие. Счетчик дистанции обновляется в режиме реального времени с вашим общим текущим значением. Если вы допустили ошибку, используйте Отменить, чтобы удалить последний город с маршрута, или Очистить, чтобы полностью стереть маршрут и начать заново.
Как только все города нажаты, нажмите Проверка. Игра сравнивает вашу петлю с истинным оптимумом, вычисленным проверкой всех возможных порядков. Если они совпадают, вы выигрываете. Если ваша длина больше, вы увидите оба маршрута, отображаемых бок о бок, чтобы вы могли диагностировать, где вы ошиблись.
Правила строгие: каждый город ровно один раз, петля должна вернуться домой, и ваша дистанция должна совпадать с оптимумом, чтобы выиграть. Нет частичного кредита или “близко достаточно”.
Самый важный шаблон: самопересекающиеся маршруты
Самое главное, что нужно узнать, - это как замечать и избегать самопересекающиеся маршруты. Большинство неоптимальных туров терпят неудачу из-за того, что путь пересекает сам себя. Когда два сегмента вашего маршрута пересекаются, вы тратите дистанцию - и развязывание их почти всегда сокращает тур.
Вот почему: представьте четыре города, образующие грубый квадрат. Если вы посетите их в порядке, создающем форму креста - где маршрут идет от верхнего левого угла к нижнему правому, а затем от верхнего правого к нижнему левому, - эти два сегмента пересекаются. Оптимальный тур следует по периметру вместо этого: верхний левый, верхний правый, нижний правый, нижний левый. Те же города, никаких пересечений, более короткая общая дистанция.
Когда игра показывает вам оптимальный маршрут после проигрыша, первое, на что нужно обратить внимание, - это где ваш маршрут пересекал сам себя. Оптимальное решение не будет иметь этих пересечений. Часто, перестановка положения всего двух городов в вашем порядке удаляет пересечение полностью и приводит вашу дистанцию к оптимуму.
После каждого проигрыша считайте пересечения в вашем маршруте, прежде чем смотреть на оптимальный. Сколько пересечений вы можете увидеть? Оптимальный маршрут удалит все их. Затем идентифицируйте, какая перестановка города устранит худшее пересечение. Это сравнение - это место, где происходит большинство обучения - не от выигрыша, а от диагностированного проигрыша.
Прогулка по периметру. На новой карте мысленно проследите внешнюю границу - города, образующие выпуклую оболочку (наиболее внешнюю форму). Оптимальный маршрут часто следует по этому периметру, посещая внешние города в часовой или против часовой стрелке, прежде чем вставлять внутренние города. Постройте свой тур вокруг края сначала, а затем вставьте внутренние города в промежутки, где они вызывают наименьшее дополнительное расстояние.
Систематическое построение маршрута
Не нажимайте на города случайным образом и не надеяться. Постройте свой маршрут шаг за шагом, принимая местные решения, которые минимизируют обратный отсчет.
Начните дома и спросите: какой город я должен посетить первым? Обычно это один из ближайших или один, расположенный в направлении, которое позволяет вам перемещаться по карте без обратного отсчета. Нажмите на него.
От каждого города задайте тот же вопрос - какой непосещенный город минимизирует дополнительное расстояние, которое вы проезжаете отсюда? Этот алчный подход (всегда идущий к самому близкому или самому разумному следующему пункту назначения) не всегда приводит к оптимуму, но строит разумный первый тур, который затем можно усовершенствовать.
Как только у вас есть первый попытка маршрута, мысленно пройдитесь по нему. Где дистанция кажется расточительной? Есть ли длинный сегмент, растягивающийся через карту, где два города, которые находятся далеко друг от друга, находятся рядом в вашем туре? Могла бы перестановка двух городов в порядке устранить пересечение или устранить этот длинный прыжок? Эти небольшие локальные улучшения часто превращают хороший тур в оптимальный.
Ближайший сосед, затем усовершенствовать. Нажимайте на города алчно, всегда направляясь к следующему непосещенному пункту назначения. Заметьте свою дистанцию. Затем мысленно пройдитесь по маршруту и найдите одно пересечение, одну обратную дорогу или одну неэффективность. Переставьте два города, вовлеченных в эту неэффективность, перезапустите маршрут с перестановкой и проверьте, улучшится ли он. Повторяйте, пока не достигнете оптимума или не исчерпаете очевидные исправления.
Алчный не оптимален. Подход “ближайший сосед” кажется естественным, но часто оставляет дистанцию на столе. Ранние уровни могут простить его, но по мере роста числа городов алчные туры систематически не дотягивают до оптимума. Используйте подход “ближайший сосед” как быстрый стартовый пункт, а затем усовершенствуйте - не полагайтесь на него как на окончательный ответ.
Общие ошибки и способы их избежать
Нажатие в случайном порядке и надежда. Геометрия карты имеет значение. Города, близкие друг к другу, должны появляться друг за другом в вашем туре. Кластеры должны быть пройдены как группа, прежде чем переходить к следующему кластеру. Случайный порядок почти всегда включает дорогостоящие длинные прыжки, которые осознанный геометрический порядок избегает.
Зацикливание на своем первом туре после проигрыша. Когда вы проигрываете, не просто отменяйте один город и перезапустите. Изучите оптимальный маршрут, который показывает игра. Где он фундаментально отличается от вашего? Какой принцип порядка он не следует, которого ваш не следовал? Это метавью - сравнение целых стратегий, а не отдельных городов - это место, где происходит реальное улучшение.
Очень длинный сегмент - это подсказка, а не совпадение. Если ваш тур имеет один сегмент, который растягивается через большую часть карты, это почти всегда сигнализирует о плохом порядке. В оптимальном маршруте нет такого сегмента, который был бы значительно длиннее остальных - дистанции должны быть сбалансированы. Одинокий длинный прыжок обычно означает, что два города, которые находятся далеко друг от друга, находятся рядом в вашем туре, когда они не должны быть.
Чувство, что вы застряли после нескольких нажатий. Используйте Отменить и Очистить свободно. Если маршрут кажется неправильным после пяти городов, сотрите его и попробуйте другое начальное направление. Итерация быстрее, чем борьба с фундаментально неправильным подходом.
Поиск формулы для запоминания. Каждая карта уникальна. “Всегда идите по часовой стрелке” или “всегда посещайте верхний город первым” не сработает на разных картах. Оптимальная стратегия зависит от этой конкретной геометрии. Научитесь читать каждую новую карту свежо, а не применяя запомненное правило.
Посвятите 10 секунд изучению карты, прежде чем нажимать что-либо. Где находятся кластеры? Какой город является изолированным? Каковаrough форма карты - она распростерта или компактна? Есть ли один город, который находится далеко от всех остальных, и который потребует дорогостоящий обход? Эти наблюдения руководят вашими первыми несколькими нажатиями и часто направляют вас к оптимальному маршруту, прежде чем вы затратите какое-либо расстояние.
По мере роста сложности
Ранние уровни имеют четыре или пять городов. Количество возможных порядков достаточно мало, чтобы угадать. На этом этапе вы часто можете увидеть ответ, прежде чем нажимать - просто просканируйте карту, идентифицируйте самый естественный маршрут и выполните его.
На уровне шесть или семь появляется шестой город. Количество возможных маршрутов увеличивается драматически. Угадывание больше не работает надежно. На этом этапе необходима стратегическая способность. Вы должны размышлять о геометрии, замечать пересечения и сравнивать стратегии, а не просто угадывать.
Каждые несколько уровней добавляется еще один город. К уровням двенадцать-пятнадцать вы управляете семью-восемью городами. Количество возможных маршрутов исчисляется сотнями тысяч. Вы не можете мысленно проверить их все. Вы должны мыслить структурно - использовать шаблоны, доверять инстинкту пространства и подходить к каждой карте как к геометрической проблеме, которую нужно решить, а не к последовательности, которую нужно запомнить.
Разделяй и властвуй на больших картах. Мысленно разбейте города на кластеры или регионы. Постройте эффективный подмаршрут в каждом регионе, а затем соедините регионы в порядке, который минимизирует межрегиональную дистанцию. Решение меньших подпроблем и затем их комбинирование - это надежный подход, когда количество городов превышает шесть или семь.
Регулярные занятия
Три сосредоточенных занятия в неделю по примерно 10 минут каждое достаточно для быстрого прогресса.
Занятие 1 - наблюдение геометрии. Играйте три раунда без спешки. Перед нажатием на любой город потратьте 15 секунд, описывая форму карты себе: “города образуют грубую овальную форму с одним выбросом слева”. Пусть эта форма руководит вашим туром. Тренируйтесь читать структуру карты, прежде чем тратить дистанцию.
Занятие 2 - устранение пересечений. Играйте три раунда. После каждого проигрыша потратьте целую минуту, сравнивая свой маршрут с оптимальным. Считайте каждое пересечение в вашем туре. Спросите: какая перестановка устранит худшее пересечение? Это целенаправленное изучение - это место, где строится долгосрочная интуиция.
Занятие 3 - скорость и постоянство. Играйте пять раундов и попробуйте выиграть три подряд. К третьему раунду вы должны почувствовать прогресс - построение маршрута быстрее, замечание пересечений более инстинктивно, и ваши дистанции ближе к оптимуму чаще.
Маркер прогресса. Вы улучшаетесь, когда выигрываете раунд с первой попытки - когда вы можете предсказать оптимальный маршрут из геометрии карты и выполнить его, не нуждаясь в отображении обратной связи. Ранние игроки проигрывают часто; игроки среднего уровня выигрывают большинство раундов, но все еще не дотягивают до более высоких счетов городов; продвинутые игроки выигрывают систематически на уровне десять и выше.
Вести мысленный журнал шаблонов. После каждого раунда отмечайте, что сработало: “первый шаг по периметру сработал здесь” или “изолированный город в верхнем левом углу нужно было посетить последним”. Со временем эти наблюдения накапливаются в интуицию пространства, которая применяется ко всем будущим картам, даже если вы никогда не видели их раньше.
Последние мысли
Путешественник тренирует навык, который переносится далеко за пределы игр: способность размышлять о пространственном расположении и оптимизации без формулы. Вы тренируетесь в том же мышлении, которое инженеры используют для проектирования маршрутов доставки, хирурги используют для планирования этапов операции и архитекторы используют для эффективного размещения пространств.
Игра разработана для роста с вами. Ранние раунды учат основам - нажимайте на города, замечайте пересечения, проверяйте свою дистанцию. Более поздние раунды требуют более глубокой размышления - балансировать несколько ограничений, видеть общую картину, доверять инстинкту пространства, когда количество возможностей взрывается.
Начните с того, где вы есть. Играйте раунды, которые находятся на грани вашей способности. Тратьте время на изучение каждого проигрыша. Оптимальный маршрут всегда там, ждет, чтобы его увидели. Ваша задача - научиться видеть его быстрее.
Коммивояжёр
Найдите кратчайший маршрут, проходящий через каждый город один раз · классическая задача коммивояжёра
Играть сейчас - бесплатноБез регистрации. Работает на любом устройстве.
