ВУЗ:
Составители:
Рубрика:
Эффективность зависит от связности графа. Для полносвязанного графа
реализуется полный просмотр всех схем маршрутов. В остальных случаях число
проверок реализуемости маршрутов на графе
ξ
G
равно сумме мощностей множеств
достижимости и недостижимости. Для случая, рассмотренного в примере, таких
проверок было произведено 25 и обнаружено 4 схемы, в то время как общее число
проверок 5!=120.
ξ
G
для некоторого графа G, можно оценить по формуле :
ξξ
Gk
k
n
=
=
∑
1
,
где
ξ
k
—мощность множества достижимости или недостижимости И/ИЛИ-графа.
Для того чтобы выяснить, как связана топологическая сложность графа со
сложностью алгоритма, рассмотрим наиболее распространенный метод оценки
топологической сложности, основанный на цикломатической метрике Маккейба [26].
В основу этого метода положена оценка сложности программы по числу линейно
независимых маршрутов в его управляющем графе, то
есть маршрутов, комбинируя
которые, можно получить все пути из корневой вершины графа в концевую.
Цикломатическая метрика программы определяется из ее управляющего графа
следующим образом:
ν
G
= m - n + 1,
где m — число дуг в графе, n — число вершин.
Многие авторы подчеркивают адекватность этой метрики интуитивному пониманию
сложности программного модуля [16]. На основании опыта программирования и
статистического материала [4] была определена разумная верхняя граница сложности
ν
G
, равная 10. Рассмотрим, как связана эта метрика со сложностью алгоритма
построения непериодических маршрутов, определяемой с помощью топологического
дерева. С этой целью проведем эксперимент, который заключается в построении полного
множества графов заданного порядка и оценки их сложности с помощью метрики
Маккейба.
Для проведения эксперимента реализован алгоритм, который порождает графы,
удовлетворяющие определенным условиям.
Эти условия накладываются концепциями
технологии графо-символического программирования и подразумевают наличие в графе
корневой и концевой вершин. Алгоритм порождения графов основан на методе
частичного перебора из полного комбинаторного множества всех существующих графов
заданного порядка.
Полученные результаты показывают, что в среднестатистическом смысле
сложность алгоритма построения непериодических маршрутов зависит от
топологической сложности
графа. Однако, при рассмотрении конкретных случаев
имеется большой разброс в показателе сложности алгоритма от топологической
сложности.
Зависимость разброса усредненной сложности алгоритма АПЧ в зависимости от
степени графа получена экспериментально, в результате моделирования орграфов
различной структуры (см. рис.3.11).
