Статья: Расчет эйлеровых и гамильтоновых маршрутов на графах методом перебора, редукции и мозаики (2024)

Читать онлайн

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

Ключевые фразы: эйлеровы графы реперных точек, оптимальные замкнутые маршруты, маршрут максимального и наибольшего мониторинга, БПЛА, ЦЕЛЕВАЯ ФУНКЦИЯ, ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
Автор (ы): Руденко Эдуард Михайлович, Семикина Елена Викторовна
Журнал: I-METHODS

Предпросмотр статьи

Идентификаторы и классификаторы

УДК
00. Наука в целом (информационные технологии - 004)
Для цитирования:
РУДЕНКО Э. М., СЕМИКИНА Е. В. РАСЧЕТ ЭЙЛЕРОВЫХ И ГАМИЛЬТОНОВЫХ МАРШРУТОВ НА ГРАФАХ МЕТОДОМ ПЕРЕБОРА, РЕДУКЦИИ И МОЗАИКИ // I-METHODS. 2024. № 2, ТОМ 16
Текстовый фрагмент статьи