Ответ 1

Детерминированное решение для N > 1, K > 1

Для N групп K людей каждый.

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

В каждой группе каждый человек должен помнить наивысшее число среди этой группы, а человек с наивысшим числом (помеченный как leader) должен перемещаться по часовой стрелке по периметру, пока остальная часть группы остается.

После того, как leader каждой группы встретит следующую группу, они сравнивают свое число с предыдущим номером leader.

Если число лидеров выше, чем предыдущее число лидеров группы, тогда лидер и группа все продолжают по периметру парка. Если номер предыдущего лидера группы выше, то все они остаются на месте.

В конце концов leader с наибольшим номером будет продолжаться по всему периметру ровно на 1 оборот, собирая всю группу.

Детерминированное решение для N > 1, K = 1 (с одним разумным предположением о предвзятости знания)

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

В случае N = 2 это становится тривиально уменьшенным до одного человека, оставшегося на месте, а другого - по часовой стрелке.

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

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

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

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

Update

Для удовольствия я решил написать визуальную демонстрацию моих решений проблемы, используя d3. Не стесняйтесь играть с параметрами и перезапускать симуляцию с любым начальным состоянием. Здесь ссылка:

https://jsfiddle.net/patrob10114/c3d478ty/show/

Key

• черный - лидер
• белый - последователь
• при нажатии
  • синий - выбранный человек
  • зеленый - известный выбранный человек
  • красный - неизвестно выбранным человеком

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

Ответ 2

Они должны двигаться к самой северной точке парка.

Ответ 3

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

Ответ 4

невозможно с детерминированным алгоритмом, если

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

Доказательство. С помощью детерминированного алгоритма мы можем выводить конечные позиции из исходных позиций, но группы могут начинаться равномерно по периметру, и в этом случае проблема имеет вращательную симметрию, и поэтому решение не изменится на 1/n вращение, которое, однако, не имеет неподвижной точки по периметру.

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

• Недетерминированный. Как отмечали другие, различные недетерминированные алгоритмы предоставляют решение, вероятность завершения которого имеет тенденцию к определенности по мере того, как время стремится к бесконечности; Я подозреваю, что любая случайная прогулка будет делать. (Многие ответы)
• Точки неразличимы. Соглашайтесь с фиксированной точкой, в которой необходимо встретить: ответ flyxs.
• Индивидуумы неразличимы. Если существует идеальный алгоритм хеширования, выберите те, у которых самый низкий хеш, чтобы собрать других: решение Патрика Робертса.
• Тот же алгоритм: выберите один заблаговременно, чтобы собрать другие (адаптируя решение Патрика Робертса).

Другие предположения могут быть ослаблены:

• Некруглый периметр. Условие, что периметр является круговым, является довольно искусственным, но если периметр топологически эквивалентен кругу, эта эквивалентность может быть использована для преобразования любого решения в решение проблема окружности.
• Неограниченные начальные точки. Даже если начальные точки не могут быть равномерно распределены, пока некоторые точки различны, топологическая эквивалентность (как для некруглого периметра) уменьшает решение решения к круговому случаю, показывая, что решение не существует.

Я думаю, что этот вопрос действительно принадлежит Computer Science Stack Exchange.

Ответ 5

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

Парк представляет собой 2-мерное пространство, 2 группы расположены случайным образом, каждая группа имеет одинаковые права/слева (оба стоят перед парком). Оба имеют одинаковые операции, которые запрограммированы на то, чтобы делать абсолютно то же самое (ничего, что я делаю правильно, и вы идете налево, потому что это делает проблему очевидной). Таким образом, это операции: Идите вправо/влево/вправо на x единиц времени. Они также могут понять, что они прошли через свое первоначальное положение (тот, в котором они начали). И они могут быть запрограммированы в цикле.

Если у вас есть возможность использовать случайность - все просто. Вы можете найти множество решений. Например: с вероятностью 0,5 каждый из них решит, что они либо сделают 3 шага вправо, либо ждут. Или один шаг вправо и подождите. Если вы сделаете эту операцию в цикле, и они выберут разные варианты, то ясно, что они будут встречаться (один быстрее, чем другой, поэтому он достигнет более медленного человека). Если они оба выберут одну и ту же операцию, они сделают круг и оба достигнут своих начальных позиций. В этом случае бросьте кости еще раз. После N кругов вероятность того, что они будут встречаться, будет 1 - 0,5 ^ n (которая приближается к 1 очень быстро)

Ответ 6

Удивительно, но есть способ сделать это! Но сначала мы должны определить наши условия и предположения.

У нас есть N = 2 "команды" из K = 2 "агентов" за штуку. Каждый "агент" работает с той же программой. Они не могут сказать север с юга, но они могут сказать по часовой стрелке против часовой стрелки. Агенты в одном и том же месте могут разговаривать друг с другом; агенты в разных местах не могут.

Ваш предложенный частичный ответ был: "Если каждая группа разбивается на две части и идет, и когда они находят другого человека, продолжающего идти с этим человеком, все они будут сходиться по другую сторону парка..." Это означает, что наши агенты имеют некоторый (магический, аксиоматический) личный протокол решения, так что если Алиса и Боб находятся в одной команде и просыпаются в одной и той же точке круга, они могут (магически, аксиоматически) сами решать, что Алиса будет двигаться по часовой стрелке, а Боб возглавит против часовой стрелки (в отличие от Алисы и Боба, которые всегда идут точно в одном направлении, потому что по определению они точно так же реагируют на ситуацию, в которой они одинаково находятся).

Один из способов реализации этого магического решения - предоставить каждому агенту персональный генератор случайных чисел. Всякий раз, когда в какой-то момент собираются 2 или более агента, все они бросают миллионный штамп, и любой из них считается самым высоким, признается лидером. Таким образом, в вашем частичном решении Алиса и Боб могут катиться каждый: кто бы ни ролл выше ( "лидер" ) идет по часовой стрелке и отправляет другой агент ( "последователь" ) против часовой стрелки.

Хорошо, решив вопрос "как наши агенты принимают решения", разрешите реальную загадку!

Предположим, что наши команды (Алиса и Боб) и (Карл и Дейв). Алиса и Карл являются изначально избранными лидерами.

• Шаг 1: Каждая команда наматывает миллионную матрицу для создания случайного числа. Семантика этого номера: "Команда с большим номером - это Мастер-команда", но, конечно, ни одна команда не знает, кто получил большее число. Но Алиса и Боб оба знают, что их номер можно назвать 424202, и Карл и Дейв оба знают, что их число составляет 373287.

• Шаг 2: Каждая команда отправляет своего лидера по кругу по часовой стрелке, а последователь остается неподвижным. Каждый лидер останавливается, когда добирается туда, где ждет другой последователь команды. Итак, теперь в одной точке круга у нас есть Алиса и Дэйв, а в другом - Карл и Боб.

• Шаг 3: Алиса и Дейв сравнивают номера и понимают, что команда Алиса - это Мастер-команда. Аналогично, Боб и Карл сравнивают числа и понимают, что команда Боба - это Мастер-команда.

• Шаг 4: Алиса, являющаяся лидером Мастер-команды, берет Дэйва по часовой стрелке по кругу. Боб и Карл (будучи последователем и лидером не-мастер-команды, соответственно) просто остаются на месте. Когда Алиса и Дэйв достигают Боба и Карла, проблема решена!

Обратите внимание, что шаг 1 требует, чтобы обе команды катили миллионную грань в изоляции; если во время шага 3 все понимают, что есть галстук, им просто нужно отступить и попытаться снова. Поэтому это решение по-прежнему вероятностно... но вы можете сделать свое ожидаемое время сколь угодно маленьким, просто заменив все миллионные кости на триллионные, quintillion-sided, bazillion-sided... кости.

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

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

Протокол для K > 2 агентов в команде идентичен случаю K = 2: вы просто glom все последователи вместе на шаге 1. Алиса (лидер) идет по часовой стрелке, а Bob neric (последователи) остаются неподвижными; и т.д.

Протокол для K = 1 агентов для каждой команды... ну, это невозможно, потому что независимо от того, что вы делаете, вы не можете детерминистически гарантировать, что кто-нибудь когда-нибудь столкнется с другим агентом. Вам нужно, чтобы агенты обеспечили, не сообщая вообще, что они не все будут кругом по часовой стрелке вокруг парка навсегда.

Одна вещь, которая поможет (но не технически решить) случай K = 1, - это рассмотреть относительные скорости агентов. Возможно, вы знакомы с алгоритмом Floyd "Черепаха и Харе" для нахождения цикла в связанном списке, Ну, если агентам разрешено двигаться с нетождественными скоростями, то вы, безусловно, можете сделать "непрерывную, многозадачную" версию этого алгоритма:

• Шаг 1: Каждый агент переворачивает миллионную матрицу для генерации случайного числа S и начинает работать по часовой стрелке вокруг парка со скоростью S.

• Шаг 2: когда один агент подхватывает другой, оба агента сверкают вместе и начинают работать по часовой стрелке с новой случайной скоростью.

• Шаг 3: В конце концов, , предполагая, что никто не выбрал точно такие же случайные скорости, все будут встречаться.

Этот протокол требует, чтобы Алиса и Карл не свернули одинаковые номера на своих миллионных играх, даже когда они находятся через парк друг от друга. ИМХО, это совсем другое предположение из другого протокола, предполагающего, что Алиса и Боб могли катить разные цифры на своих миллионных играх, когда они были в одном и том же месте. С K = 1 мы никогда не гарантируем, что два агента будут находиться в одном месте.

Во всяком случае, я надеюсь, что это поможет. Решение для N > 2 команд осталось в качестве упражнения для читателя, но моя интуиция заключается в том, что будет легко свести случай N > 2 к случаю N = 2.

Ответ 7

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

• Если имя скаута более раннее в алфавитном порядке: группа следует за ним.
• Если имя скаута позже: он присоединяется к группе и отказывается от своего первоначального идентификатора группы.

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

Ответ 8

Предположим, что парк - это круг. (для ясности)

Группа A

• Лицо A.1
• Лицо A.2

Группа B

• Лицо B.1
• Лицо B.2

Мы (группа A) находимся в нижней части круга (90 градусов). Мы соглашаемся идти в направлении 0 градусов в противоположных направлениях. Я человек A.1, и я иду по часовой стрелке. Я отправляю личность А .2. против часовой стрелки.

В любом возможном сценарии (B разбивает, B не разбивается, B имеет ту же схему, B имеет некоторую сложную схему), каждая группа может иметь противоречивую информацию. Поэтому, если у Группы А нет оружия, чтобы заставить Группу В подчиняться, новые группы могут сделать конфликтующие выборы при встрече.

Скажем, например, A.1. соответствует B.1 и A.2. соответствует B.2. Что мы делаем (A.1 и B.1), если B имеет одну и ту же схему? Поскольку новые группы не могут знать, что решает другая группа (независимо от того, следует ли использовать схему A или схему B), каждая группа может принять другое решение.

И мы закончим там, где мы начали... (т.е. два человека в 0 градусов и два человека на 90 градусов). Позвольте называть этот контрольный пункт "Первая итерация".

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

Каждая итерация имеет 50% -ный шанс не работать.

Это означает, что после x итераций ваши шансы не встречаться в общей точке не более 1- (0.5 ^ x)

N.B. Я подумал о множестве сценариев, таких как группа А, соглашающаяся вернуться к своей первоначальной точке и общаясь друг с другом, что планирует сделать группа Б. Но никакая сигара не получается даже с очень умными схемами, всегда возникает конфликтная информация.

Ответ 9

Интересная проблема. Я хотел бы предложить мою версию решения:

0 Каждая группа выбирает лидера.
1: Лидер и последователи идут в противоположных направлениях.

2: Они встречаются с другими лидерами или последователями группы.

3: Они продолжают двигаться в том же направлении, что и раньше, 90 градусов

4: К этому времени все группы совершили полукруг по периметру и неизменно встречали лидеров снова, своих или других.

5: Все лидеры меняют направление следующего шага на шаг последователей и приказывают им следовать.

6: Единицы из всех групп встречаются в одной точке.

Для подробного объяснения обратитесь к прилагаемому файлу. Для просмотра вам понадобится MS Office Powerpoint 2007 или новее. Если у вас его нет, используйте pptx. viewer (Powerpoint viewer) в качестве бесплатной альтернативы.

Анимированное решение (.pptx)

EDIT: я сделал опечатку на первом слайде. Он гласит: "Желтый и красный выбраны", в то время как он должен быть "Синим и красным".

Ответ 10

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

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

• Один из вас отправляется в парк. Другой стоит на месте, скажем, в позиции X. Это гарантирует, что: (а) вы будете встречаться друг с другом периодически в X, скажем, каждые T секунд; и (б) для каждого члена другой команды, независимо от того, как они перемещаются по периметру парка, они должны встречаться хотя бы с одной из ваших команд, по крайней мере, каждые T секунд.

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

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

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

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

Как пример, если команда, следуя этой стратегии, встречает команду (неразумно), следуя вашей стратегии, тогда одна из моих команд согласится пойти вместе с одной из вашей команды, которую они встречают, а другая откажется (с тех пор это потребовало бы, чтобы они сделали запретное движение выше). Это означает, что когда ваша команда встретится вместе, у них будет одна из моей команды с группой из трех человек. Свободный член моей команды находится на курсе столкновения с этой группой из трех человек, если ваша команда не делает ничего извращенного.

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

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

Ответ 11

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

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

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

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

В конце, направление наибольшего числа приведет их всех к одной точке.

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

Изменить: извините, я просто вижу, что это очень близко к решению Патрика Робертса

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

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

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

Есть ли решение для этого?