Математическая магия — решение задачи о путешествующем волшебнике [закрыто]

Отчасти это результат неудачного обмена на Worldbuilding Meta :

@ HDE226868 хахахаха. Математика запрещена. - Джеймс вчера

Я найду способ! – HDE 226868 вчера

Я думаю, что у меня есть.

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

Сценарий:

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

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

Как он может понять, по какому маршруту идти? Он использует приближение: отправляйтесь в ближайшую деревню, в которой он еще не был.

Некоторые ограничения:

  • Ему приходится идти пешком.
  • Он забыл, как использовать свои силы, за исключением одной: способности парить в воздухе на десять футов в течение примерно семи секунд.

Примечание: я не хотел, чтобы магия была разрешена. Тем не менее, я изначально не уточнил это, поэтому я буду считать ответ Корта Аммона прекрасным, тем более что он довольно умный. Будущие ответы: Пожалуйста, не используйте магию! Спасибо.

Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .

Ответы (4)

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

После того, как вы дружелюбно относитесь ко всем, кого встретите (по крайней мере, к тем немногим, кто подойдет к вам), и в целом попытаетесь заработать хорошую карму, вы можете обнаружить, что к вам подходит природный волшебник. Он вежливо спрашивает, почему ты продолжаешь прыгать на 10 футов в воздух, потому что это беспокоит бурундуков. Если они не подготовятся к зиме, они умрут с голоду.

Вы объясняете свое желание пути между всеми деревнями волшебнику природы. Он начинает чертить карту и какие-то цифры, но ты качаешь головой. Вы объясняете, что не знаете почему, но совершенно уверены, что вам не разрешено использовать математику. Он поднимает бровь и спрашивает: «Все по математике?» Вы пожимаете плечами и упоминаете, что, по-вашему, это достаточно сложная задача, чтобы допустить один математический подход. Вы полагаете, что ничего страшного, если мы немного смошенничаем и воспользуемся циркулем и линейкой, которые у вас всегда под рукой, чтобы возвести круг в квадрат, если это поможет как часть решения, но это все, что вы можете допустить. Увы, вы забыли, как возводить круг в квадрат, так что чит может оказаться не таким уж полезным.

Волшебник природы хлопает в ладоши и улыбается! «Природа делает множество удивительных вещей без математики!» — восклицает он. Он вызывает магию, и муравьи выползают из нескольких муравейников. Он объясняет проблему муравьям и дает им задание найти для вас кратчайший путь!

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

Муравьи удивительно хорошо находят путь в евклидовых пространствах. На самом деле, они настолько хороши, что мы часто подражаем их подходу, основанному на феромонах, в наших алгоритмах оптимизации; они так хорошо работают!

Разве это не обман?
@ HDE226868 Я не понимаю, как это обман. Он отвечает на заданный вами вопрос, используя вполне жизнеспособное решение: магию. В конце концов, вы никогда не указывали, что рассматриваемый мастер не может использовать ресурсы.
Хорошо, я оставлю это. Я думал, что смысл в том, что магия запрещена, ясен, но я ошибался. Я возьму это на заметку. +1 за изобретательность.
Этот подход работает просто отлично, без магии. Создайте масштабную модель и бросьте муравьев на модель. Я видел похожее решение, использующее воду с матрицами в масштабной модели (правда, я не помню, как предотвратить смешивание матриц).
@Jim2B Муравьи все еще очарованы магией ... Если только вы не соберете муравьев вручную и каким-то образом не уговорите их достичь целей вашей модели в линейном порядке ... (Есть ли сахар в красителях? Откуда они знают, где идти дальше, или где "дом" в этом отношении?)
Я думаю, что слизевики работают лучше , чем муравьи. Потом он может просто вырастить его на самой карте, чтобы найти кратчайший путь . Но этот ответ на самом деле не имеет ничего общего с тем, что этот парень волшебник, или с единственной силой, которой он обладает. Вы обманули, сказав, что появился другой волшебник с большими способностями.
В водном методе муравьи вообще не используются. Это был прозрачный пластик с прорезанными в нем каналами, представляющими разные пути. Канал, на котором вода вышла первой, был оптимальным решением, но я не могу найти видео, которое я смотрел на нем. По сути, это было аналогичное решение для TWP, которое работало элегантно, но его было сложно настроить для большого количества остановок.
Что касается муравьев, то их не нужно очаровывать. Просто создайте масштабную копию, поместите еду в места, представляющие города, и не позволяйте им вернуться туда, откуда они пришли. Есть даже литература по методу :) - Это "штука" en.wikipedia.org/wiki/…

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

С этим из пути с шоу:

Используя карту (он заходит в местный магазин карт, сельский житель убегает, он берет карту) он находит все деревни, которые ему нужно посетить.

Поместите английскую булавку, петлю или крючок на каждую деревню. (Я использовал английские булавки, так как они были под рукой)

Протяните веревку вдоль дорог или тропинок между каждой деревней. Привяжите каждый конец к английской булавке/петле/крючку.

Добавьте метку к каждой булавке с названием деревни. Причина этого станет ясна.

На вашей карте должно быть что-то вроде этого:Деревни со строкой

Теперь выберите самый длинный путь. Держите его так, чтобы две английские булавки на каждом конце были на одном уровне.

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

Повторяйте эту операцию, пока не останется минимальное количество строк.

Отсоедините нити, которые вы держите над линией, от сетки. Было немного сложно держать их всех распутанными.

Теперь у вас должна остаться одна линия английских булавок, соединяющая каждый город.Пройденный путь

Недостатки этого метода:
установка занимает довольно много времени.
Вам нужно украсть карту.
Очень легко получить сетку в полный узел.
Я не уверен, что это всегда даст вам правильный ответ. (Но вроде близко)

Я не уверен, что это сработает, но +1 за создание чего-то, чтобы попробовать это.
Эта великолепная идея! Теперь, чтобы превратить его в псевдокод.

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

Допустим, есть четыре деревни, каждая из которых имеет три пути разной длины между ними.

В первый раз мастер выберет наугад: AB1 -> BC2 -> CD3 -> DA1

В следующий раз он выбирает другие маршруты: AB2 -> BD3 -> DC1 -> CA2.

И третий раз: AC3 -> CD2 -> DB3 -> BA1

Теперь он достает все свои заметки и то, сколько времени у него ушло на каждый путь, и начинает комбинировать и смешивать лучшие маршруты. Он отбрасывает те, которые заняли слишком много времени, и сохраняет и смешивает только те шаблоны, которые были относительно быстрее. Затем он начинает сначала с шага 1, но уже со своими новыми смешанными узорами, и повторяет все это несколько раз.

В конце концов у него будет набор очень хороших путей — они не обязательно будут оптимальными, но они будут близки.

Пункт, для которого я почти написал полный ответ: мастеру на самом деле не нужен оптимальный путь, даже если он существует. Всегда проверять точки в одном и том же порядке и примерно с одинаковой скоростью — плохая идея при патрулировании в течение длительного периода времени. Это делает вас менее внимательным, позволяет разумным врагам предугадывать вас и может вызывать странные взаимодействия с другими вещами с регулярным периодом. Таким образом, иметь несколько хороших путей и варьировать их или их комбинации на самом деле лучше , чем оптимальный путь. Если вы всегда будете ходить по одному и тому же пути, вы будете выглядеть довольно странно для жителей деревни.

Простой алгоритм, который я использую для относительно небольшого количества остановок, таков:

  1. Найдите расстояние от каждого города до любого другого города.
  2. Возьмите город, кратчайшее расстояние которого до другого является самым большим в группе, — обозначьте его как город 1.
  3. Выберите его кратчайший путь к следующему городу - обозначьте этот город 2.
  4. Из города 2 выберите маршрут до ближайшего непосещенного города.
  5. Повторите шаг 4 по мере необходимости

Это не дает оптимального ответа , но дает хороший. Если количество городов меньше (скажем, <10), то иногда очевидно, как сократить маршрут.

Получается, что мой самостоятельно разработанный подход — это вариант подхода с минимальным связующим деревом .

Математическая магия — решение задачи о путешествующем волшебнике [закрыто]
СпросиСетьПолитика конфиденциальности1y, 1v