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

Данная задача выполняется с помощью программы CriticalPath, за-

пускаемой  выбором  пункта  “Длина  критического  пути”  в  меню  “Работа  с  ин-
формационной  моделью”.  В  основе  программы,  реализующей  алгоритм,  не-
формально  описанный  выше,  лежит  модифицированный  вариант  подпрограм-
мы DIJKSTRA [77]. Программа написана на языке Фортран/МВС [74, 75]. Файл
выполнимого  образа  программы  (файл  CRITIC.EXE)  имеет  размер  приблизи-
тельно равный 42 Кбайтам.

3.5.

Реализация отката в технологическом маршруте

Одной из важных задач оперативного управления является выполнение

отката  в  технологическом  маршруте  проектирования.  Процесс  проектирования
современных изделий электронной техники (ИЭТ) и МСВТ имеет выраженный
итерационный  характер.  Каждой  итерации  предшествует  “откат”  к  ранее  вы-
полненной  КПП  в  технологическом маршруте. Откаты могут иметь различную

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

Наиболее распространенными методами, использующимися при решении

задач глобального анализа графов, являются поиски в глубину и в ширину

[76

−

79]. Метод поиска в глубину получил широкое распространение благодаря

большей универсальности. Поиск в глубину

−

это регулярный обход вершин

графа по следующим правилам:

1. Находясь в вершине x, нужно двигаться в любую другую, ранее не

пройденную вершину y (если таковая найдется), одновременно запоминая дугу,
по которой впервые попали в нее.

2. Если из вершины x не удается попасть в ранее не пройденную вершину

или таковой вообще нет, то необходимо вернуться в вершину z, из которой
впервые попали в x, и продолжить поиск в глубину из вершины z.

Таким образом, при выполнении обхода вершин графа по этим правилам

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

Методу поиска в глубину можно в известном смысле противопоставить

метод поиска в ширину, который предполагает последовательный просмотр
всех вершин графа на уровне k, затем всех вершин на уровне k+1 и т.д.

Разработан итеративный алгоритм обхода ациклического орграфа, ис-

пользующий  вспомогательный  список  корневых  вершин  (под)деревьев,  кото-
рый  является  своеобразным  “симбиозом”  алгоритмов,  реализующих  методы
поиска в глубину и ширину [80, 81]. В отличие от известного  рекурсивного  ал-
горитма    поиска    в    глубину,    предложенного    Р.  Тарьяном  [82],  данный  алго-
ритм обладает двумя следующими преимуществами: 1) не требует наличия (или
запоминания)  обратных  дуг  для  вершин  орграфа,  т.е.  экономит  оперативную
память  и/или  дисковое  пространство,  и  2)  сокращает  время  обработки  вершин
орграфа за счет отказа от возврата в корневые вершины поиска по обратным ду-
гам.

Итеративный алгоритм выполняет регулярный обход вершин ацикличе-

ского орграфа по следующим правилам:

1. Попав в некоторую вершину x, нужно проанализировать ее тип (по ко-

личеству исходящих дуг). Если вершина корневая, то занести ее в список кор-
невых вершин (при условии, что она не была ранее занесена в этот список) и
прекратить продвижение вглубь орграфа. Если вершина обычная, то продви-
гаться в другую, ранее не пройденную вершину y.

2. Если из вершины x не удается попасть в ранее не пройденную вершину

или таковой вообще нет, то необходимо выбрать очередную корневую вершину

z из списка и продолжить поиск в глубину из этой вершины.

3. Если список корневых вершин оказывается исчерпанным, т.е. все об-

наруженные корневые вершины орграфа обработаны, то алгоритм прекращает
свою работу.

Укрупненное описание итеративного алгоритма для обхода вершин ацик-

лического орграфа, приведено ниже.

1.НАЧАЛО. Проинициализировать список корневых вершин.

2. Получить вершину, с которой необходимо начать обход орграфа.

3. Пронумеровать эту вершину, т.е. присвоить ей номер N = 1.

4. Получить информацию о количестве исходящих дуг для вершины и за-

нести ее в переменную Cnt.

5.Если Cnt

≠

0, выполнить переход на шаг 8.

6. Если список корневых вершин исчерпан, то КОНЕЦ.

7. Получить номер корневой вершины из списка и выполнить переход на

шаг 4.

8. Если Cnt > 1, выполнить переход на шаг 11.

9. Перейти в следующую вершину по исходящей дуге.

10. Пронумеровать вершину, т.е. N = N + 1, и выполнить переход на

шаг 4.

11. Если номер вершины N есть в списке корневых вершин, выполнить

переход на шаг 14.

12. Занести номер вершины N в список корневых вершин.

13. Выбрать левую исходящую дугу и пронумеровать ее, т.е. M = 1, и вы-

полнить переход на шаг 16.

14. Проинициализировать номер дуги, т.е. M = 0.

15. Пронумеровать следующую исходящую дугу, т.е. M = M + 1.

16. Если Cnt < M, установить указатель на следующий элемент списка

корневых вершин и выполнить переход на шаг 6.

17. Перейти в следующую вершину по исходящей дуге с номером

18. Если эта вершина пронумерована, то выполнить переход на шаг 15.

19. Пронумеровать вершину, т.е. присвоить ей номер N = N + 1.

20. Получить информацию о количестве исходящих дуг для вершины и

занести ее в переменную Cnt2.

21. Если Cnt2 = 0, выполнить переход на шаг 15.

22. Если Cnt2 > 1, занести номер вершины N в список корневых вершин

и выполнить переход на шаг 15.

23. Перейти в следующую вершину по исходящей дуге и выполнить

переход на шаг 18.

Структурная схема итеративного алгоритма для обхода вершин ацикличе-

ского орграфа показана на рис. 3.1.

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

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

Следует также отметить, что хотя данный алгоритм разрабатывался в рас-

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

Действительно, в предложенном алгоритме одним из условий прекраще-

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

Анализ эффективности выполнения рекурсивного и итеративного алго-

ритмов для двух граничных вариантов структуры орграфов (линейного орграфа
и двоичного дерева) позволил получить следующие соотношения:

= (2N

−1) / N

−

для линейного орграфа;

= (N+2M) / (N+2M

−1)

−

для двоичного дерева,

содержание .. 19 20 21 22 ..