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