В теории игр задача о водителе-убийце — это математическая задача преследования[en], в которой гипотетический убегающий, который может двигаться медленно, но маневренно, пытается уйти от водителя, ведущего машину куда быстрее, но существенно ограниченного в маневре. Предполагается, что оба, убегающий и водитель, никогда не устают. Вопрос ставится так: при каких обстоятельствах и используя какую стратегию водителю удастся догнать убегающего или убегающий сможет избегать встречи бесконечно долго?
Задача предложена Руфусом Айзексом в его книге Дифференциальные игры[1].
Задача о водителе-убийце является классическим примером дифференциальной игры, которая играется в непрерывное время[en] в непрерывном пространстве состояний. Методы вариационного исчисления и уровня[en] можно использовать в качестве математического каркаса для исследования решений задачи. Хотя задача декларируется занимательной, для математиков она является важной задачей моделирования и применяется во многих задачах реального мира.
Надо отметить, что сам Айзекс вместо «водителя» и «пешехода» подразумевал торпеду и увёртывающийся от неё небольшой катер[2].
Дискретная версия задачи описана Мартином Гарднером в его книге Математические новеллы (глава 18). В этой постановке квадратный автомобиль на прямоугольной решётке со скоростью 2 преследует бандита, имеющего скорость 1, но автомобиль не имеет право делать левые повороты или переходить к движению в противоположном направлении (поворот на 180 градусов)[3].
См. также
- Вариационное исчисление
- Метод уровней[en]
- Задача преследования Аполлония[en]
- Задача ангела (задача Конвея) — ещё одна математическая игра, в которой могущественный и маневренный игрок пытается уйти от крайне изобретательного, но менее могущественного противника
- Принцесса и чудовище
Примечания
- ↑ R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York: John Wiley & Sons, 1965. — P. 349-350. (Р. Айзекс. Дифференциальные игры. Москва, Мир, 1967.)
- ↑ Игра «Шофер-убийца» и её модификации, Математика 2008. Вып.2 УДК 62-50 c В. С. Пацко, В. Л. Турова, Выпуск Удмуртского университета
- ↑ М. Гарднер. Глава 18. Оптимальные стратегии для игр с двумя участниками // Математические новеллы. — М.: Мир, 1974. — С. 225.
Ссылки
- История задачи о водителе-убийце, презентация на коллоквиуме, посвящённом 60-летию профессора Пьера Бернхарда.
- Аналитическое изучение задачи о водителе-убийце
- Задача о водителе-убийце. Вычисление уровней значений функции
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .