Задачи о камерах-ловушках

Для наблюдения за дикими животными, необходимого, в частности, для изучения популяционной динамики, используются камеры-ловушки. Существуют аргументы о пользе их периодической перестановки, откуда возникают три задачи. Первая состоит в преобразовании данных карты о размещении карты в расстояния между ними — требуется учитывать рельеф местности; мы не будем рассматривать эту задачу. Вторая состоит в определении оптимального маршрута перестановки N (натуральное число) камер на N новых мест, где возникает естественное ограничение на перемещения: нельзя посещать место, куда полагается установить камеру, не имея "в рюзкаке" ни одной снятой со старого места, за счет чего сложность решения задачи методом динамического программирования снижается по отношению к "обыкновенной" задаче коммивояжера той же размерности 2N. Третья задача — запланировать перестановки камер на возможно длительное время. Между двумя "расстановками" камер (множество N координат установленных камер и множество N координат мест, куда их надлежит переставить) возникает естественное "расстояние" — стоимость перестановки камер, с учетом начала маршрута в особом городе — базе, где камер не стоит, и требованием возвращаться на базу по завершении перестановки. В такой задаче уместно рассматривать не аддитивный минисуммный критерий качества, а минимаксный, откуда получаем задачу коммивояжера на узкие места.