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

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