Сложность задач оптимизации преследования на плоскости

Abstract

Розглянуто диференційні ігри переслідування на площині, в яких для кожного втікача утворюється група переслідувачів. Доведено теореми про NP-повноту та NP-трудність задач оптимізації груп переслідування.The differential pursuit-evasion games on a plane, in which a group of pursuers is created for every evader, are considered. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved.