Управление сложными проектами в интегрированных САПР - часть 22

 

 

85

где  

N

 

−

 общее количество вершин орграфа, 

M

 

−

 количество корневых вершин, 

K

  

−

  коэффициент,  показывающий  отношение  эффективностей  рекурсивного  и 

итеративного алгоритмов.  

 

 

 

86

Начало

Инициализация

списка корневых

вершин

Получить вершину,

с которой начина-

ется обход орграфа

Номер вершины:

N = 1

Занести количество

исходящих дуг

в 

Cnt

Cnt 

≠ 0?

нет

да

Cnt 

> 1?

да

нет

Перейти в следую-

щую вершину по

исходящей дуге

Вершина про-

нумерована?

нет

Номер вершины:

N = N + 1

да

А

Получить номер

вершины из спис-

ка и занести в 

N

Установить указа-

тель на следую-

щий элемент

списка

Номер исходящей

дуги: M = 0

Список кор-

невых вер-

шин исчер-

пан?

да

нет

Конец

Б

Рис. 3.1(а). Структурная схема итеративного алгоритма для

обхода вершин ациклического орграфа

 

 

87

Занести номер

вершины 

N

в список

M

≤Cnt?

нет

да

Cnt2

>1?

да

нет

Перейти в следую-

щую вершину по

исходящей дуге с

номером 

M

Вершина про-

нумерована?

нет

Номер вершины:

N = N + 1

да

А

Номер вер-

шины 

N

 есть

в списке?

да

Б

Рис. 3.1(б). Структурная схема итеративного алгоритма для обхода

вершин ациклического орграфа (продолжение)

Номер исходящей

дуги: 

M = M + 1

Номер исходящей

дуги: 

M = 1

нет

Занести кол-во ис-

ходящих дуг для

вершины в 

Cnt2

Cnt2

≠0?

да

Перейти в следую-

щую вершину по

исходящей дуге

нет

Занести номер

вершины 

N

в список

 

 

88

 

Для  сравнительной  оценки  эффективностей  выполнения  указанных алго-

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

Обработка  полутора  десятков  

представлений орграфов произвольной 
структуры  и  последующие  расчеты 
показали,  что  при  выполнении  обхода 
орграфа  итеративный  алгоритм  вы-
полняет  в  среднем  в  1,5  раза  меньше 
обращений  к  его  вершинам,  чем  из-
вестный  рекурсивный  алгоритм.  На-
пример,  для  ациклического  орграфа 
произвольной  структуры,  показанного 
на  рис.  3.2,  это  отношение  составляет 
приблизительно 1,8. 

Приведенный  выше  итератив-

ный  алгоритм  обхода  вершин  ацикли-
ческого  орграфа  модифицирован  при-
менительно  к  задаче  реализации  глу-
бокого  отката  в  технологическом 

маршруте  проектирования  [83].  Описание  модифицированного  итеративного 
алгоритма приведено ниже.  

1. НАЧАЛО.  Для  вершины,  соответствующей  КПП,  в  процессе  выполне-

ния которой была обнаружена ошибка проектирования, сменить состояние “Ак-
тивная” на “Приостановлена”. 

2. Ввести идентификатор вершины, начиная с которой выполняется обход 

в  орграфе,  т.е.  идентификатор  проектной  процедуры,  сформировавшей  некор-
ректное проектное решение. 

 

 

Рис.  3.2.  Пример   ацикличе-
ского орграфа произвольной 
структуры