Разработка больших сетей связи: оптимизационные проблемы и эвристики
Authors: Мельников Б.Ф. , Терентьева Ю.Ю. 
Published: December 2024

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

This paper summarizes and continues the previous papers of the authors. We consider some models of optimization problems that arise when building large communication networks. The topology of the communication network is formalized by an undirected graph. The coordinates of the vertices of an undirected graph (nodes of the communication network) are usually set in advance in some way, and a set of edges must be constructed for this set of vertices. The main (and sometimes the only) goal, both of our previous articles and of this article, can be formulated as follows: for some special additional requirements, it is necessary to construct a set of edges of the graph that satisfies these requirements; these edges should have the minimum possible total length. Another important idea is to modify the standard algorithms for working with graphs in order to be able to consider dynamic models (when the input data changes slightly), and it should be possible to use the results of previous calculations when changing the input data. From the point of view of graph theory, all these problems have long been solved, but in practice, the implementation of the corresponding algorithms is fraught with great difficulties: first, in real conditions, we consider graphs consisting of several thousand vertices; second, as we have already noted, the construction of large communication networks usually involves a dynamic change in requirements. The consequence of the two circumstances given is that often even algorithms of quadratic complexity often cannot be applied. For each of our models of optimization problems, we present one or more possible algorithms (primarily heuristic ones) designed to solve it. Our proposed algorithms are usually iterative, and this fact fits well into the capabilities needed to build algorithms that work with dynamically changing data.