Abstract: На плоскости рассматривается отрезок прямой — барьер, мониторинг (покрытие) которого осуществляется одинаковыми мобильными сенсорами (дронами) с ограниченной длиной траектории. Каждый дрон стартует из своего депо к некоторой точке барьера, перемещается вдоль барьера и возвращается в своё депо, пройдя путь ограниченной длины. Часть барьера, вдоль которой двигался дрон, считается покрытой этим дроном. Барьер покрыт, если каждая его точка покрыта хотя бы одним дроном. Требуется определить число дронов в каждом депо и найти траекторию каждого дрона так, чтобы весь барьер был покрыт, и общая длина путей (траекторий) дронов была минимальной. Для решения этой задачи с евклидовым расстоянием известен алгоритм динамического программирования, который строит оптимальное решение с псевдополиномиальной трудоёмкостью. В этой статье для решения задачи в прямоугольной метрике предлагается полиномиальный алгоритм, который строит оптимальное решение с квадратичной трудоёмкостью от числа депо.

Cite: Ерзин А.И.
Оптимальное размещения дронов, покрывающих барьер в прямоугольной метрике
Дискретный анализ и исследование операций. 2026. Т.33. №1. С.56–70. DOI: 10.33048/daio.2026.33.849 РИНЦ

Dates:

Submitted:	Dec 17, 2025
Accepted:	Jan 22, 2026
Published online:	Aug 25, 2026

Identifiers:

≡ Elibrary:

91978393

Altmetrics: