Как мне найти свою жену в супермаркете?

27

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

Я думаю, что у этого алгоритма есть некоторые характеристики:

  • Каждый человек должен иметь возможность вывести его, используя логику, которая не делает никаких предположений о том, что решает другой человек, но, поскольку каждый человек знает, что другой находится в той же позиции, он может сделать выводы о том, что должен решать другой .
  • Один и тот же алгоритм должен быть выведен обоими людьми, поскольку в их ситуациях существует полная симметрия (ни один из них не знает о начальной позиции другого, а лабиринт имеет фиксированный размер и полностью отображается обоими). Обратите внимание, что алгоритм не обязан быть детерминированным: его можно рандомизировать.
jl6
источник
(Супермаркет может быть ввожу в заблуждении примера, так как есть пол-наблюдаемая зона выхода.) Теперь, если оба имели средства , чтобы отметить свой путь таким образом , что позволяет каждому сказать самостоятельно от друга , они могут повернуть вспять в утроении интервалов, проблемы, возникающие при встрече с собственным .
седобородый
7
Логичный ответ - позвонить по ее мобильному телефону;)
DavidPostill
2
Ответ, отличный от CS, состоит в том, чтобы перейти к точке Шеллинга . В супермаркете это может быть, например, служба поддержки клиентов или выход. Однако обратите внимание, что в человеческой жизни точки Шеллинга часто зависят в такой же степени от человеческого поведения и знаний, а не от алгоритмического анализа шаблонов связности, поэтому перспектива CS на самом деле не дает большого понимания, когда мы говорим о людях-агентах. Вы действительно хотите спросить о людях в реальной жизни, или вы хотите задать математический вопрос о роботизированных агентах в идеализированной обстановке?
DW

Ответы:

19

Это называется проблемой свиданий .

Как упоминалось в статье «Мобильный агент Рандеву: опрос» , эта проблема является оригинальной, предложенной Алперн: «Задача поиска Рандеву» :

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

В обзоре выше,

Аннотация: Обзор последних результатов по проблеме рандеву мобильных агентов в распределенных сетях с акцентом на изложение различных подходов, используемых исследователями в сообществе теоретических информатики.

Он охватывает как «Асимметричное свидание» (в разделе 4), так и «Симметричное свидание» (в разделе 5).


Для симметричного рандеву статья Альперна показывает:

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

Hengxin
источник
Отмеченный как лучший, поскольку это указывает мне на соответствующую область исследования. Если я правильно понял этот обзор, еще не известно, существует ли оптимальное решение для симметричного свидания.
JL6
-1

На самом деле подойдет любая согласованная заранее подготовленная схема.

Например:

  1. Поверните всегда налево
  2. Если в тупике вернуться к предыдущему повороту и повернуть направо
  3. Один должен будет идти вдвое быстрее (заранее скомпонованного) скорости другого (или в более теоретико-числовом выражении, скорости двух агентов должны быть относительно простыми или, как правило, линейно независимыми).

Или даже проще

  1. Один агент остается на том же месте
  2. В то время как другой использует непротиворечивую схему для исследования лабиринта (например, используя подход потока Ариадны ).
  3. В конце концов, в конечном итоге они встретятся.

Эта схема гарантирует, что люди встретятся в конечном итоге (но это может занять некоторое время)

Зачем? Потому что схема согласована для обоих и не ведет ни в тупик. Так как лабиринт конечен и связан, через конечное время они встретятся.

Если схема не согласована, нет гарантии, что они встретятся, так как они могут привести к замкнутым циклам.

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

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

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

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

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

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

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

  1. Каждый агент бросает монету на какую роль выбрать (например, оставаться на месте или исследовать лабиринт)
  2. Затем они действуют, как описано выше.

В среднем это приведет к тому, что люди в конечном итоге встретятся, но не гарантируется при всех случаях.

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

Проблема такого рода является примером глобальной оптимизации с использованием только локальной информации . Или, другими словами, способ сопоставить глобальные ограничения с локальными ограничениями . Эта, более общая проблема (которая включает проблему рандеву) рассматривается в этом посте math.se (и содержит ссылки на него) "Методы преобразования глобальных ограничений в локальные ограничения"

Никос М.
источник
«Один агент остается в том же месте» нарушает свойство симметрии, которое хочет OP. где оба агента следуют той же стратегии.
AndyG
@AndyG, да, на эту часть ответили ниже, используя ряд подходов. Плюс на это отвечали, отметив, что решение в этом случае не гарантировано
Никос М.
1
@NikosM. Я не верю, что какая-либо синхронизация необходима. Эту проблему можно смоделировать как сценарий уклонения от преследования, в котором оба агента считают других уклоняющимися. Существуют вероятностные подходы к решению этой проблемы, и в трехмерной среде можно показать минимальное количество преследователей, необходимое для гарантии захвата.
AndyG
1
«Всегда поворачивай налево» не работает. Предположим, что вы находитесь на проходе 2, а ваша жена - на проходе 5. Вы будете ходить вверх и вниз по проходам 2 и 3 (или 1 и 2, в зависимости от того, в каком направлении вы изначально были), и ваша жена будет подниматься и вниз 5 и 6 (или 4 и 5). В качестве альтернативы, если вы находитесь в небольшом супермаркете, чей график подключения представляет собой цикл, вы можете просто обойти цикл навсегда, в одном направлении и с одинаковой скоростью.
Дэвид Ричерби
1
«Один агент остается на том же месте, а другой делает что-то другое» не работает, так как оба агента могут предпочесть оставаться на месте и ждать другого вечно. Если агенты могут общаться, чтобы договориться, кто будет стоять на месте, они могут вместо этого сообщить, что один из них стоит у бананов.
Дэвид Ричерби