Проблема шофёра-убийцы
В теории игр задача о шофёре-убийце — это математическая задача преследования , в которой гипотетический бегун, который может двигаться лишь медленно, но обладает высокой маневренностью, противостоит водителю автомобиля, который намного быстрее, но гораздо менее маневренен и пытается чтобы сбить его. Предполагается, что и бегун, и водитель никогда не устают. Вопрос, который необходимо решить, заключается в следующем: при каких обстоятельствах и с помощью какой стратегии водитель автомобиля может гарантировать, что он всегда сможет догнать пешехода, или пешеход может гарантировать, что он сможет неопределенно долго ускользать от автомобиля?
Эта проблема часто используется в качестве несекретного косвенного доказательства противоракетной обороны и других военных целей, что позволяет ученым публиковать информацию по ней без каких-либо последствий для безопасности. [1]
Проблема была предложена Руфусом Айзексом в отчете 1951 года. [2] для корпорации RAND и в книге «Дифференциальные игры» . [3]
Проблема шофера-убийцы является классическим примером дифференциальной игры, в которую играют в непрерывном времени в непрерывном пространстве состояний . Вариационное исчисление и методы множества уровней могут использоваться в качестве математической основы для исследования решений проблемы. Хотя эта проблема сформулирована как развлекательная задача, она является важной модельной задачей математики, используемой в ряде реальных приложений.
Дискретная версия проблемы была описана Мартином Гарднером (в его книге «Математический карнавал» , глава 16), где патрульная машина со скоростью 2 преследует мошенника со скоростью 1 на прямоугольной сетке, где патрульная машина, но не мошенник, ограничена не совершать левых поворотов или разворотов.
См. также
[ редактировать ]- Вариационное исчисление
- Метод установки уровня
- Задача преследования Аполлония
- Конвея Задача ангела — еще одна математическая игра, в которой мощный и маневренный противник противостоит очень изобретательному, но менее мощному противнику.
- Игра Принцесса и монстр
Ссылки
[ редактировать ]- ^ Беккер, А.Т., и Гарсия, Дж. (22 января 2018 г.). Демонстрационный проект Wolfram . Проблема шофера-убийцы. https://demonstrations.wolfram.com/TheHomicidalChauffeurProblem/
- ^ Р. Айзекс, Игры преследования , RAND Corporation (1951)
- ^ Р. Айзекс, Дифференциальные игры: математическая теория с приложениями к войне и преследованию, контролю и оптимизации , John Wiley & Sons, Нью-Йорк (1965), стр. 349–350.
Внешние ссылки
[ редактировать ]- История проблемы шофёров-убийц , доклад на коллоквиуме, посвящённом 60-летию профессора Пьера Бернара.
- Аналитическое исследование случая игровой задачи «шофер-убийца»
- Игра «Шофер-убийца». Вычисление наборов уровней функции значения
- Проблема шофера-убийцы