RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Поволжский регион. Физико-математические науки // Архив

Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2022, выпуск 3, страницы 32–42 (Mi ivpnz215)

Математика

О графовой модели для задач рефлектометрии и некоторых алгоритмах их решения. Часть II. Подход к программной реализации

Б. Ф. Мельников, Ю. Ю. Терентьева

Центр информационных технологий и систем органов исполнительной власти, Москва

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

Ключевые слова: эвристические алгоритмы, задачи дискретной оптимизации, модели теории графов, жадный алгоритм, метод ветвей и границ.

УДК: 004.021; 004.023; 519.17

DOI: 10.21685/2072-3040-2022-3-4



© МИАН, 2024