Архив статей журнала
в работе рассматриваются различные подходы к решению задачи нахождения на эйлеровых графах эйлеровых маршрутов, которые проходят один раз через все ребра графа, и гамильтоновых маршрутов на гамильтоновых графах, которые проходят один раз через все вершины графа. Расчет эйлеровых или гамильтоновых маршрутов является научной задачей, которая имеет теоретическое и практическое значение. Теоретическое значение обусловлено отсутствием в литературе информации о формуле числа этих маршрутов и методах нахождения всех маршрутов на эйлеровых и гамильтоновых графах. Практическое значение обусловлено известным фактом, что на этих графах число маршрутов быстро увеличивается с ростом числа вершин и ребер, что позволяет использовать эти маршруты для организации разнообразных схем группового мониторинга БПЛА на местности по реперам, которые соединены отрезками между собой, как ребрами, и образуют эйлеровы или гамильтоновы графы. Имея в распоряжении все или большое множество маршрутов можно выделить из них маршруты наибольшего или максимального мониторинга, на которых возможен групповой полет наибольшего или максимального количества БПЛА, безопасно двигающихся в группе с интервалом в одно или несколько ребер графа таким образом, чтобы исключить возможность одновременного нахождения в одинаковых вершинах или на ребрах двух и более аппаратов. Определение таких маршрутов имеет важное практическое значение для обеспечения наиболее плотного и непрерывного мониторинга на местности, где расположены реперы. Постановка задачи: на основе разработанных в работе методов определить все или большое множество эйлеровых или гамильтоновых маршрутов и определить маршруты наибольшего и максимального мониторинга. При этом использовать полиномиальные алгоритмы по времени счета для графов средней и большей размерности. Методы: определение эйлеровых и гамильтоновых маршрутов для графов малой размерности с помощью метода полного перебора, для графов средней размерности с помощью метода редукции и мозаики. Результаты: вычисление всех или большого множества эйлеровых или гамильтоновых маршрутов и определение из них маршрутов наибольшего или максимального мониторинга. Практическая значимость: множество всех или большая часть эйлеровых или гамильтоновых маршрутов могут быть использованы в алгоритмах одиночного или группового полета БПЛА для организации плотного и непрерывного мониторинга по реперам на местности с соблюдением условий безопасного полета с интервалом в одно и более ребер друг за другом. Адаптирование методов перебора, редукции и мозаики программными средствами в бортовых алгоритмах БПЛА позволит рассчитывать оперативно множество маршрутов максимального и наибольшего мониторинга в ходе полета или заблаговременно в предполетной подготовке.