Проблема встречи
Дилемма встречи — это логическая дилемма, обычно формулируемая следующим образом:
- Два человека встречаются в парке, где они никогда раньше не были. Придя по отдельности в парк, они оба с удивлением обнаруживают, что это огромная территория и поэтому они не могут найти друг друга. В этой ситуации каждый человек должен выбирать между ожиданием в фиксированном месте в надежде, что другой его найдет, или же началом поиска другого в надежде, что он решил где-то ждать.
Если они оба решат подождать, они никогда не встретятся. Если они оба решат пойти пешком, есть вероятность, что они встретятся, и вероятность, что они не встретятся. Если один решит подождать, а другой решит идти, то существует теоретическая уверенность, что в конце концов они встретятся; однако на практике для того, чтобы это гарантировать, может потребоваться слишком много времени. В таком случае возникает вопрос: какие стратегии им следует выбрать, чтобы максимизировать вероятность встречи?
Примеры этого класса проблем известны как проблемы рандеву . Эти проблемы впервые были неофициально предложены Стивом Альперном в 1976 году. [1] и он формализовал непрерывную версию проблемы в 1995 году. [2] Это привело к большому количеству недавних исследований в области поиска рандеву. [3] Даже задача симметричного рандеву, разыгрываемая в n отдельных местах (иногда называемая проблемой рандеву в кафе Моцарта ) [4] оказалось очень трудно решить, и в 1990 году Ричард Вебер и Эдди Андерсон предложили оптимальную стратегию. [5] В 2012 году гипотезу для n = 3 доказал Ричард Вебер . [6] Это была первая нетривиальная задача симметричного поиска, которая была полностью решена. Соответствующая асимметричная задача встречи имеет простое оптимальное решение: один игрок остается на месте, а другой игрок посещает случайную перестановку локаций.
Помимо проблем, представляющих теоретический интерес, проблемы рандеву включают в себя реальные проблемы с приложениями в области синхронизации , операционных систем проектирования , исследования операций и даже планирования поисково-спасательных операций.
встречи Детерминированная задача
Детерминированная задача встречи — это вариант задачи встречи, в которой игроки или роботы должны найти друг друга, следуя детерминированной последовательности инструкций. используется уникальная метка, присвоенная каждому роботу Хотя каждый робот выполняет одну и ту же последовательность команд, для нарушения симметрии . [7]
См. также [ править ]
- Координационная игра
- Проблема обедающих философов
- Вероятностный алгоритм
- Поиск игр
- Проблема со спящим парикмахером
- Сверхрациональность
- Нарушение симметрии
- Координатор , место встречи по умолчанию
Ссылки [ править ]
- ^ Альперн, Стив (1976), Игры в прятки , семинар, Институт перспективных исследований, Вена, 26 июля .
- ^ Альперн, Стив (1995), «Проблема поиска рандеву», SIAM Journal on Control and Optimization , 33 (3): 673–683, doi : 10.1137/S0363012993249195 , MR 1327232
- ^ Альперн, Стив ; Гал, Шмуэль (2003), Теория поисковых игр и рандеву , Международная серия по исследованию операций и науке управления, том. 55, Бостон, Массачусетс: Kluwer Academic Publishers, ISBN 0-7923-7468-1 , МР 2005053 .
- ^ Альперн, Стив (2011), «Игры поиска рандеву», в Кохране, Джеймс Дж. (редактор), Энциклопедия исследований операций и науки управления Wiley, Wiley, doi : 10.1002/9780470400531.eorms0720 .
- ^ Андерсон, Э.Дж.; Вебер, Р.Р. (1990), «Проблема встречи в дискретных местоположениях» , Journal of Applied Probability , 27 (4): 839–851, doi : 10.2307/3214827 , JSTOR 3214827 , MR 1077533 , S2CID 122587972 .
- ^ Вебер, Ричард (2012), «Оптимальный симметричный поиск рандеву в трех местах» (PDF) , Mathematics of Operations Research , 37 (1): 111–122, doi : 10.1287/moor.1110.0528 , MR 2891149 .
- ^ Та-Шма, Амнон; Цвик, Ури (апрель 2014 г.). «Детерминированные встречи, охота за сокровищами и универсальные последовательности исследований». Транзакции ACM на алгоритмах . 10 (3). 12. дои : 10.1145/2601068 . S2CID 10718957 .