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

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

Даты:

Поступила в редакцию:	17 дек. 2025 г.
Принята к публикации:	22 янв. 2026 г.
Опубликована online:	25 авг. 2026 г.

Идентификаторы БД:

≡ РИНЦ:

91978393

Альметрики: