Преследование-уклонение (варианты которого называются cops and grabs и graph search ) — это семейство задач в математике и информатике , в которых одна группа пытается выследить членов другой группы в окружающей среде. Ранние работы над задачами этого типа моделировали окружающую среду геометрически. [1] В 1976 году Торренс Парсонс ввел формулировку, в которой движение ограничивается графом . [ 2] Геометрическую формулировку иногда называют непрерывным преследованием-уклонением , а графовую формулировку — дискретным преследованием-уклонением (также называемым поиском графа ). Текущие исследования обычно ограничиваются одной из этих двух формулировок.
В дискретной формулировке задачи преследования-уклонения окружающая среда моделируется в виде графа .
Существует бесчисленное множество возможных вариантов преследования-уклонения, хотя они, как правило, имеют много общих элементов. Типичный, базовый пример выглядит следующим образом (игры «полицейские и грабители»). Преследователи и уклоняющиеся занимают узлы графа. Обе стороны делают поочередные ходы, в ходе которых каждый участник либо остается на месте, либо перемещается по ребру к соседнему узлу. Если преследователь занимает тот же узел, что и уклоняющийся, уклоняющийся захватывается и удаляется из графа. Обычно задается вопрос, сколько преследователей необходимо для обеспечения возможного захвата всех уклоняющихся. Если достаточно одного преследователя, граф называется графом «полицейский-победитель» . В этом случае один уклоняющийся всегда может быть пойман за время, линейное количеству n узлов графа. Поимка r уклоняющихся с k преследователями также может занять порядка r n времени, но точные границы для более чем одного преследователя пока неизвестны .
Часто правила движения изменяются путем изменения скорости убегающих. Эта скорость — максимальное количество ребер, по которым убегающий может двигаться за один ход. В приведенном выше примере убегающие имеют скорость, равную единице. На другом полюсе находится концепция бесконечной скорости, которая позволяет убегающему двигаться в любой узел графа, пока между его исходным и конечным положением есть путь , не содержащий узлов, занятых преследователем. Аналогично некоторые варианты вооружают преследователей «вертолетами», которые позволяют им двигаться в любую вершину за свой ход.
Другие варианты игнорируют ограничение, что преследователи и убегающие должны всегда занимать узел, и допускают возможность того, что они расположены где-то вдоль ребра. Эти варианты часто называют задачами подметания , в то время как предыдущие варианты подпадают под категорию задач поиска .
Несколько вариантов эквивалентны важным параметрам графа. В частности, нахождение числа преследователей, необходимых для поимки одного убегающего с бесконечной скоростью в графе G (когда преследователи и убегающий не ограничены в движении по очереди, а движутся одновременно) эквивалентно нахождению ширины дерева G , а выигрышная стратегия для убегающего может быть описана в терминах убежища в G . Если этот убегающий невидим для преследователей, то задача эквивалентна нахождению ширины пути или разделения вершин. [3] Нахождение числа преследователей, необходимых для поимки одного невидимого убегающего в графе G за один ход (то есть одно перемещение преследователей от их первоначального развертывания) эквивалентно нахождению размера минимального доминирующего множества G , предполагая, что преследователи могут изначально развертываться где угодно (это более позднее предположение справедливо, когда предполагается, что преследователи и убегающий движутся по очереди).
Настольная игра «Скотленд-Ярд» представляет собой вариант задачи преследования-уклонения.
Сложность нескольких вариантов преследования-уклонения, а именно, сколько преследователей необходимо для очистки заданного графа и как заданное количество преследователей должно двигаться по графу, чтобы очистить его либо с минимальной суммой их расстояний, либо с минимальным временем выполнения задачи, изучалась Нимродом Мегиддо , С. Л. Хакими , Майклом Р. Гари , Дэвидом С. Джонсоном и Христосом Х. Пападимитриу (J. ACM 1988), а также Р. Бори, К. Тови и С. Кенигом. [4]
Решение многопользовательских игр преследования-уклонения также привлекло повышенное внимание; см. R Vidal et al., Chung and Furukawa [1], Hespanha et al. и ссылки в них. Маркос AM Vieira и Рамеш Говиндан и Гаурав С. Сукхатме предоставили алгоритм, который вычисляет минимальное время завершения стратегии для преследователей, чтобы поймать всех убегающих, когда все игроки принимают оптимальные решения на основе полных знаний. Этот алгоритм также может быть применен, когда убегающие значительно быстрее преследователей. К сожалению, эти алгоритмы не масштабируются за пределами небольшого количества роботов. Чтобы преодолеть эту проблему, Маркос AM Vieira и Рамеш Говиндан и Гаурав С. Сукхатме разработали и реализовали алгоритм разбиения, в котором преследователи ловят убегающих, разложив игру на несколько игр с несколькими преследователями и одним убегающим.
В непрерывной формулировке игр преследования-уклонения окружающая среда моделируется геометрически, обычно принимая форму евклидовой плоскости или другого многообразия . Варианты игры могут накладывать ограничения на маневренность игроков, такие как ограниченный диапазон скорости или ускорения. Также могут использоваться препятствия.
Если лев преследует человека с одинаковой скоростью, то ясно, что человек может убежать на плоскости или сфере, всегда двигаясь по прямой линии от льва. Когда оба заключены в круговой диск, то лев, скорее всего, поймает человека. Безикович доказал в 1952 году, что у человека есть стратегия, позволяющая уклоняться от поимки бесконечно долго против любой стратегии. [5]
Одним из первых приложений задачи преследования-уклонения были системы наведения ракет , разработанные Руфусом Айзексом в корпорации RAND . [1]