Оглавление
Проблема с местом встречи
-
Дилемма встречи
- Если оба ждут, встреча невозможна.
- Если оба идут, вероятность встречи есть, но не гарантирована.
- Если один ждет, а другой идет, встреча гарантирована, но может занять много времени.
- Вопрос: как выбрать стратегии для максимизации вероятности встречи?
-
Примеры и исследования
- Задачи о рандеву были впервые представлены Стивом Альперном в 1976 году.
- В 1995 году Альперн формализовал непрерывную версию задачи.
- Исследования в области поиска встреч активизировались после формализации задачи.
- Задача о симметричном рандеву в n местах оказалась сложной, но была решена для n = 3 в 2012 году.
- Асимметричное рандеву имеет простое оптимальное решение: один игрок остается, другой посещает случайную перестановку локаций.
-
Прикладное значение
- Задачи рандеву имеют теоретический интерес и применяются в синхронизации, проектировании ОС, исследовании операций и планировании поисково-спасательных операций.
-
Проблема детерминированного сближения
- Вариант задачи о рандеву, где роботы следуют детерминированным инструкциям с уникальными метками для нарушения симметрии.
-
Дополнительные темы
- Упомянуты координационная игра, проблема обедающих философов, вероятностный алгоритм, поисковые игры, проблема спящего парикмахера и сверхрациональность.
Полный текст статьи: