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