Введение

Логическая дилемма

Дилемма о свидании — это логическая дилемма, обычно формулируемая следующим образом: два человека договорились о встрече в парке, в котором они никогда раньше не были. Прибыв в парк по отдельности, оба удивленно обнаруживают, что это огромная территория, и, следовательно, не могут найти друг друга. В этой ситуации каждый человек должен выбрать между ожиданием в определенном месте, надеясь, что другой его найдет, или начать поиск другого, надеясь, что тот решил подождать где-то. Если оба выберут ожидание, они никогда не встретятся. Если оба решат начать поиск, есть шанс, что они встретятся, и шанс, что нет. Если один решит ждать, а другой — искать, то теоретически можно быть уверенным, что они в конечном итоге встретятся; однако на практике это может занять слишком много времени, чтобы быть гарантированным. Таким образом, возникает вопрос: какие стратегии им следует выбрать, чтобы максимизировать вероятность встречи? Задачи этого класса известны как задачи встречи (rendezvous problems). Эти проблемы были впервые неофициально представлены Стивеном Альперном в 1976 году, а он формализовал непрерывную версию проблемы в 1995 году. Это привело к активным современным исследованиям в области поиска места встречи. Даже симметричная задача встречи, проводимая в n различных местах (иногда называемая задачей встречи в кафе Моцарта), оказалась очень сложной для решения, и в 1990 году Ричард Вебер и Эдди Андерсон выдвинули предположение об оптимальной стратегии. В 2012 году Ричард Вебер доказал это предположение для n = 3. Это была первая нетривиальная симметричная задача поиска места встречи, которая была полностью решена. Соответствующая асимметричная задача встречи имеет простое оптимальное решение: один игрок остается на месте, а другой посещает случайную перестановку мест. Помимо теоретического интереса, задачи встречи включают в себя реальные проблемы с применением в таких областях, как синхронизация, проектирование операционных систем, исследования операций и даже планирование поисково-спасательных операций.

Детерминированная проблема с места встречи

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