Проблема рандеву - Rendezvous problem

В дилемма рандеву это логическая дилемма, обычно формулируемая следующим образом:

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

Если они оба захотят подождать, они никогда не встретятся. Если они оба решат идти пешком, есть вероятность, что они встретятся, а есть вероятность, что нет. Если один предпочитает ждать, а другой - идти пешком, то есть теоретическая уверенность в том, что они рано или поздно встретятся; однако на практике получение гарантии может занять слишком много времени. Возникает вопрос: какие стратегии им следует выбрать, чтобы максимизировать вероятность встречи?

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

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

Детерминированная проблема рандеву

Основная статья: Детерминированная проблема рандеву

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

Смотрите также

Рекомендации

  1. ^ Альперн, Стив (1976), Игры в прятки, Семинар, Institut fur Hohere Studien, Вена, 26 июля.
  2. ^ Альперн, Стив (1995), "Задача поиска места встречи", SIAM Journal по управлению и оптимизации, 33 (3): 673–683, Дои:10.1137 / S0363012993249195, МИСТЕР  1327232
  3. ^ Альперн, Стив; Гал, Шмуэль (2003), Теория поисковых игр и рандеву, Международная серия исследований операций и менеджмента, 55, Бостон, Массачусетс: Kluwer Academic Publishers, ISBN  0-7923-7468-1, МИСТЕР  2005053.
  4. ^ Альперн, Стив (2011), «Игры на поиски рандеву», в Кокране, Джеймс Дж. (Ред.), Энциклопедия исследований операций и управления Wiley, Wiley, Дои:10.1002 / 9780470400531.eorms0720.
  5. ^ Андерсон, Э. Дж .; Вебер, Р. (1990), «Задача встречи в дискретных местах», Журнал прикладной теории вероятностей, 27 (4): 839–851, Дои:10.2307/3214827, JSTOR  3214827, МИСТЕР  1077533.
  6. ^ Вебер, Ричард (2012), «Оптимальный симметричный поиск рандеву в трех местах» (PDF), Математика исследования операций, 37 (1): 111–122, Дои:10.1287 / moor.1110.0528, МИСТЕР  2891149.
  7. ^ Та-Шма, Амнон; Цвик, Ури (Апрель 2014 г.). «Детерминистические встречи, поиски сокровищ и строго универсальные последовательности исследований». ACM-транзакции на алгоритмах. 10 (3). 12. Дои:10.1145/2601068. S2CID  10718957.