Методы топологической оптимизации

При организации сетей одной из основных задач является распределение потоков информации по кратчайшим путям. Под такими путями понимают пути передачи информации, кратчайшие по времени передачи или протяженности, или пути с минимальными помехами, числом задействованных узлов, стоимостью и т. п. Таким образом, оптимизация путей может проводиться по различным технико-экономическим критериям и выбранные пути должны обеспечивать при заданных требованиях наиболее эффективное использование линий и узлов связи. В связи с этим имеет смысл проведение сравнительного анализа существующих на сегодняшний день алгоритмов маршрутизации с целью выработки закономерностей эволюции развития топологии и методики управления информационными потоками.

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

Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

Существуют несколько наиболее эффективных алгоритмов нахождения кратчайшего пути:

• 1. Метод Форда-Беллмана. Этот метод применяется для поиска кратчайшего пути во взвешенном графе. Основным достоинством является возможность расчета пути в графе, в котором есть ребра с отрицательным весом.
• 2. Метод Шимбелла — матричный метод определения кратчайших путей между всеми узлами сети. Этот метод был усовершенствован Оттерманом. Возможность полного топологического анализа сети обеспечила широкое практическое применение этого метода при организации трафика передачи данных в сетях.

Однако, матричный метод позволяет не только определить величины кратчайших путей между всеми узлами сети, но также одновременно получить длины всех возможных путей между каждой парой узлов сети. Это дает возможность использовать матричный метод для отыскания в сети обходных путей. Объем вычислений при использовании матричного метода незначительно зависит от структуры сети. Метод удобен для программной реализации.

Но особое место в математическом обеспечении детерминированных процедур выбора трафика передачи информационных потоков занимают методы Флойда и Дейкстры, базирующиеся на принципе оптимальности.

• 3. Метод Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами) позволяет находить кратчайшие пути от одной из вершин графа до всех остальных. Метод работает только для графов без ребер отрицательного веса, хотя в настоящее время существуют обобщенные методы для устранения данного недостатка (метод Дейкстры с потенциалами). Суть метода Дейкстры состоит в поэтапном наращивании дерева кратчайших маршрутов от исходного узла. При этом необходимо, чтобы после добавления на каждом этапе линии связи и узла вновь образуемый кратчайший маршрут был минимально возможным по всем оконечным узлам, еще не вошедшим в дерево. В процессе построения дерева кратчайших маршрутов вычисляются векторы весов маршрутов и корректируются векторы начальных компонент кратчайших маршрутов.
• 4. Метод Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный метод работает, если в графе содержатся ребра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом. В методе Джонсона используется метод Беллмана-Форда и метод Дейкстры, реализованные в виде подпрограмм. Ребра хранятся в виде списков смежных вершин.