Задача и алгоритмы поиска кратчайшего маршрута на графовой модели с односторонними связями

Каждому ребру r_i Î R (т.е. односторонней или двусторонней связи) графовой модели ТКС поставим в соответствие действительное число w_i³ 0 и назовём его весом ребра (связи). В конкретных ТКС это число может быть мерой геометрического расстояния между узлами ТКС, времени прохождения данных между соответствующими узлами, стоимости канала связи или другого важного коммуникационного параметра. В случае ТКС с двусторонними связями величина веса ребра может быть, вообще говоря, различной в зависимости от направления передачи данных по соответствующему каналу связи.

Будем считать, что вес ребра (канала связи) графовой модели ТКС обладает следующими свойством аддитивности:

(3.19)

т.е. вес совокупности рёбер, образующих маршрут, равен сумме весов отдельных рёбер. Величина (3.19) может использоваться в качестве критерия оптимальности (целевой функции) маршрута в ТКС при определённых ограничениях на допустимые множества узлов ТКС и рёбер (каналов связи) между ними.

Пусть задан ориентированный граф ТКС такой, что между любыми его узлами a₁ и a_k+1, называемыми соответственно начальным узлам a₁ = s и конечным узлом a_k+1=f, существует, по крайней мере, один связывающий их маршрут передачи данных. Тогда задача поиска оптимального маршрута заключается в нахождении маршрута

P= {r₁, r₂, …., r_k }, (3.20)

имеющего минимальный суммарный вес (3.19) и удовлетворяющего заданным граничным условиям

a₁ = s, a_k+1=f.

Очевидно, что в процессе решения этой задачи будут получены все кратчайшие маршруты, ведущие из узла a₁ = s в каждый промежуточный узел a ¹ a₁ оптимального маршрута. Следовательно, задача поиска оптимального маршрута сводится к задаче нахождения маршрута из некоторого заданного узла a₁ = s в любой узел ТКС, достижимый из узла a₁ = s.

Для решения этой задачи на графовой модели ТКС с односторонними связями введём следующие понятия:

a) деревом кратчайших расстояний относительного начального узла a₁ = s будем называть ориентированное дерево с корнем s такое, что маршрут из s до любой вершины aÎ является оптимальным;

b) максимальным деревом кратчайших расстояний T_*(s) относительно начального узла a₁ = s является дерево T(s), включающее в себя все узлы графа , достижимые из узла s.

Пусть T(s) - растущее дерево, содержащее все узлы aÎ A графа , достижимые из начального узла s. Обозначим через w(s, a) вес ребра (канала связи) между узлами s и aÎ T(s). Заметим, что w(s, a)³ 0, w(s, s)= 0.

Дерево T(s) будет деревом кратчайчих расстояний, т.е. T(s) = , тогда и только тогда, когда

0£ w(s, a) £ w(s, b)+ w(a, b), aÎ T(s), bÎ T(s). (3.21)

Соотношение (3.21) является теоретической основой следующего рекуррентного алгоритма поиска оптимального маршрута [69]:

1. Пусть T₁(s) - любое дерево, содержащее все узлы, достижимые из узла s.

2. На i -ом шаге (i ³ 2) алгоритма находится дерево кратчайших расстояний , для которого справедливо соотношение (3.21). Для этого к дереву добавляется ребро (a_*, b_*) и вычёркивается ребро (канал связи), ведущее к b_*.

3. На последнем шаге алгоритма определяется максимальное дерево кратчайших расстояний и соответствующий ему оптимальный маршрут.

В общем случае может быть найдено несколько оптимальных маршрутов. Если положить w_i = w(r_i)=1 для всех рёбер (каналов связи) r_i Î R, то будут найдены оптимальные маршруты, которые являются кратчайшими в том смысле, что они содержат наименьшее число рёбер (каналов связи) между начальным и конечным узлами ТКС с одностороними связями.

Следует отметить, что для решения задачи поиска оптимальных маршрутов для ТКС с односторонними, двусторонними и смешанными связями можно использовать другие методы (например, метод динамического программирования Р.Беллмана [19, 69]).

Особый интерес представляют нейросетевые методы маршрутизации, основанные на представлении ТКС в виде модифицированных однослойных нейронных сетей Хопфилда [30, 54, 69]. Эти методы обеспечивают массовый параллелизм вычислений, связанных с поиском оптимального маршрута передачи данных в глобальных ТКС.