Разработка больших сетей связи

оптимизационные проблемы и эвристики

Аннотация

Настоящая статья обобщает и продолжает предыдущие статьи авторов. Мы рассматриваем несколько моделей оптимизационных задач, возникающих при построении больших сетей связи. Топология сети связи формализуется неориентированным графом. Координаты вершин неориентированного графа (узлы сети связи), как правило, каким-то способом заданы заранее, и для этого множества вершин должно быть построено множество рёбер. Основную (и иногда единственную) цель – как наших предыдущих статей, так и настоящей статьи – можно сформулировать следующим образом: для некоторых специальных дополнительных требований нужно построить удовлетворяющее этим требованиям множество рёбер графа, имеющее минимальную суммарную длину. Другой важной идеей является модификация стандартных алгоритмов работы с графами – для того, чтобы иметь возможность рассматривать динамические модели (когда входные данные немного изменяются), причём должна быть возможность при изменении входных данных использовать результаты предыдущих вычислений.
С точки зрения теории графов все эти задачи давно решены – однако на практике реализация соответствующих алгоритмов сопряжена с большими трудностями: во-первых, в реальных условиях мы рассматриваем графы, состоящие из нескольких тысяч вершин и ребер; во-вторых, как мы уже отметили, построение больших сетей связи обычно включает в себя динамическое изменение требований. Следствием двух приведённых обстоятельств является то, что часто даже алгоритмы квадратичной сложности часто не могут быть применены.
Для каждой из наших моделей оптимизационных задач мы приводим один или несколько возможных алгоритмов (в первую очередь эвристических), предназначенных для её решения. Предлагаемые нами алгоритмы, как правило, итерационные – и этот факт хорошо вписывается в возможности, необходимые для построения алгоритмов, работающих с динамически изменяющимися данными.

Сведения об авторах

Boris Feliksovich Melnikov, Совместный Университет МГУ-ППИ в Шэньчжэне

профессор факультета вычислительной математики и кибернетики, доктор физико-математических наук

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

начальник управления анализа и методологии совершенствования информационных телекоммуникационных систем, кандидат технических наук

Опубликована
2021-04-15
Как цитировать
MELNIKOV, Boris Feliksovich; TERENTYEVA, Yulia Yuryevna. Разработка больших сетей связи. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 17, n. 1, apr. 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/727>. Дата доступа: 22 oct. 2021 doi: https://doi.org/10.25559/SITITO.17.202101.727.
Раздел
Прикладные проблемы оптимизации