Проблема с местом встречи

• Дилемма встречи

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

• Примеры и исследования

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

• Прикладное значение

  • Задачи рандеву имеют теоретический интерес и применяются в синхронизации, проектировании ОС, исследовании операций и планировании поисково-спасательных операций. 

• Проблема детерминированного сближения

  • Вариант задачи о рандеву, где роботы следуют детерминированным инструкциям с уникальными метками для нарушения симметрии. 

• Дополнительные темы

  • Упомянуты координационная игра, проблема обедающих философов, вероятностный алгоритм, поисковые игры, проблема спящего парикмахера и сверхрациональность.