Преследование-уклонение

Существует бесчисленно много вариантов преследования-уклонения, хотя они стремятся разделять многие элементы. Типичный базовый пример такой задачи - игра полицейские и грабители. Преследователи и преследуемые занимают вершины графа. Противники ходят поочерёдно, и каждый ход состоит либо из отказа от движения, либо из движения вдоль ребра в соседний узел. Если преследователь занимает тот же узел, что и преследуемый, тот считается схваченным и удаляется из игры. Вопрос обычно ставится так: как много преследователей необходимо для захвата всех преследуемых. Если преследование завершается успехом, граф называется выигрышным графом полицейского. В этом случае, один преследуемый может быть всегда захвачен за линейное время от числа вершин n графа. Захват r преследуемых k преследуемыми происходит за время порядка rn, но точные границы для более чем одного преследователя не известны.

Часто правила движения меняются путём изменения скорости преследуемых. Скорость — это максимальное число рёбер, на которые преследуемый может пройти за один ход. В примере выше преследуемый имеет скорость равную единице. Другим экстремумом является концепция бесконечной скорости, которая позволяет преследуемому двигаться в любой узел, в который существует путь между начальной и конечной позицией, который не содержит узлов с преследователями. Аналогично некоторые варианты снабжают преследователей «вертолётами», которые позволяют сделать ход на любую вершину.

Другие варианты игнорируют ограничения, что преследователи и преследуемые должны находиться в узле и позволяют находиться где-то внутри ребра. Эти варианты часто упоминаются как задачи выметания, в то время как предыдущие варианты тогда попадают в категорию задач поиска.

Некоторые варианты эквивалентны важным параметрам графа. В частности, нахождение числа преследователей, необходимых для захвата одного преследуемого с бесконечной скоростью на графе G (когда преследователи и преследуемый не ограничены передвижениями ход за ходом, а могут двигаться одновременно), эквивалентно нахождению древесной ширины графа G, а выигрышную стратегию для преследуемого можно описать в терминах укрытия в графе G. Если этот преследуемый невидим для преследователей, то задача эквивалентна нахождению путевой ширины или разделения вершин[3]. Нахождение числа преследователей необходимых для захвата одного невидимого преследуемого в графе G за один ход эквивалентно нахождению числа наименьшего доминирующего множества графа G, в предположении, что преследователи могут изначально находиться в любом месте, где захотят.

Настольная игра «Скотланд-Ярд» является вариантом задачи преследования-уклонения.

Сложность некоторых вариантов задач преследования-уклонения, а именно, сколько преследователей необходимо для очистки данного графа и как данное число преследователей должны двигаться по графу, чтобы очистить его либо с минимальной суммой их пройденных расстояний, либо с минимальным временем завершения игры, изучали Нимрод Мегиддо, С. Л. Хакими, Майкл Р. Гарей, Дэвид С. Джонсон и Христос Х. Пападимитриу и Р. Бори, К. Тови и С. Кёниг[4].

Решение игр преследования-уклонения с несколькими игроками также получает возрастающее внимание. См. статьи Р. Видаля и др.[5], Чанга и Фурукавы[6], Еспании, Кима и Састри[7] и ссылки в этих статьях. Маркос А. М. Виейра, Рамеш Говиндан и Гаурав С. Сукатми[8] предложили алгоритм, который вычисляет стратегию с минимальным временем выполнения для преследователей, чтобы схватить всех преследуемых, когда все игроки делают оптимальное решение, основанное на полном знании. Этот алгоритм можно применять также в случаях, когда преследуемые существенно быстрее преследователей. К сожалению этот алгоритм не масштабируется далее, чем на небольшое число роботов. Чтобы преодолеть эту проблему, Маркос А. М. Виейра, Рамеш Говиндан и Гаурав С. Сукатми разработали и реализовали алгоритм разбиения, где преследователи захватывают преследуемых путём разложения игры на игры с одним преследуемым и несколькими преследователями.