Преследование движущейся цели?

Предположим, что у вас есть мир с двумя игроками, преследователем и целью . Предположим, что преследователь движется немного быстрее цели. Если вы преследуете и точно знаете, что цель умен и старается не попасться, что будет хорошим подходом к преследованию и, в конечном итоге, поимке цели? (Я оставляю детали мира очень расплывчатыми, так как я надеюсь изучить общий алгоритм или семейство методов для решения этой проблемы, вместо того, чтобы слишком сильно оптимизировать структуру мира.)

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

Была ли эта проблема широко изучена? Если да, то есть ли здесь набор хорошо известных методов?

Спасибо!

(Приношу свои извинения, если это дубликат; похоже, я не нашел другого вопроса, подобного этому, но если он есть, я буду счастлив закрыть этот).

10
задан templatetypedef 23 January 2012 в 00:12
поделиться