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

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

Аннотация

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