Консалтология Общая теория консалтинга (стр. 48 )

где ak — число ребер, соединяющих вершину xk со всеми невыбранными вершинами графа G.

Строят множество вершин Гxj, смежных xj, и процесс выборки вершин G1 повторяют. Образованный подграф G1 исключают из исходного и получают граф G*=(X*, U*), где X* X\X1, U* = U\U1. Далее в графе G* выбирают вершину с наибольшей локальной степенью, включают ее в G2 и процесс повторяют до тех пор, пока граф G не бу­дет разрезан на l частей.

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

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

Главная цель размещения — создание наилучших усло­вий для трассировки с учетом обеспечения тепловых режи­мов и электромагнитной совместимости электрорадиоэле­ментов. Несмотря на обилие существующих критериев раз­мещения (минимума пересечений, минимума суммарной длины соединений и т. д.) истинной целью размещения компонентов является максимальное упрощение процесса трассировки соединений, т. е. достижение минимального числа непроведенных трасс. При размещении п электро­радиоэлементов в регулярном монтажном пространстве с числом позиций т общее число размещений N(n, m) оп­ределяется как

N(n,m) = n!Cnm =т!1(т — п)!.

В связи с этим поиск оптимального размещения с по­мощью перебора нецелесообразен уже при п>15.

Имеется много разновидностей последовательных алго­ритмов размещения. Основной идеей этих алгоритмов яв­ляется идея упорядочения электрорадиоэлементов по оп­ределенным признакам. Сначала устанавливают очеред­ность электрорадиоэлементов, а затем для каждого из них определяют наилучшую позицию по выбранному критерию, например по суммарной длине связей с уже размещенны­ми компонентами. Затем процесс повторяют для оставших­ся компонентов и свободных позиций. Связность размеща­емых элементов задается матрицей смежности R графа G=(X, U). Для выбора размещаемого элемента исполь­зуют различные оценки степени связности.

Пусть на k-м шаге алгоритма размещено Ik I элементов, тогда

I′k = I\Ik — множество еще не размещенных эле­ментов. Основными правилами для выбора элемента на (k+1)-м шаге алгоритма являются:

а) максимум суммарной связности hi со всеми раз­мещенными элементами

б) максимум разности связей fi между размещенными и неразмещенными элементами

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

Последовательные алгоритмы размещения требуют не­больших затрат машинного времени, относят их к классу полиномиальных алгоритмов со сложностью О(п), приво­дящих к неоптимальным решениям. Улучшить решение можно путем применения итерационных алгоритмов ком­поновки, основанных на изменении позиций одиночных элементов или групп элементов. Итерационные алгоритмы также относятся к классу полиномиальных со сложностью порядка О(п2) — О (n4).

Задача трассировки заключается в определении кон­кретной геометрии печатного или проводного монтажа, ре­ализующего соединения между элементами схемы. Исход­ными данными для трассировки являются список цепей, метрические параметры и топологические свойства типо­вой конструкции и ее элементов, а также результаты ре­шения задачи размещения, по которым находят коорди­наты выводов элементов.

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

В последовательных алгоритмах трассировки трассы цепей проводятся в определенном порядке одна за другой, при этом каждая проложенная трасса становится препят­ствием для всех последующих цепей. В последовательных алгоритмах производят локальную оптимизацию качества трассировки каждой отдельной трассы без учета влияния размещения данной трассы на возможность проведения последующих. Это приводит к тому, что некоторые участ­ки платы могут оказаться заблокированными.

Большинство известных алгоритмов трассировки осно­вывается на волновом алгоритме (алгоритм Ли). Основ­ные принципы волнового алгоритма Ли заключаются в следующем. Плоскость трассировки разбивают на прямо­угольные площадки — дискреты заданного размера. Раз­мер дискретной площадки определяется допустимыми раз­мерами проводников и расстояниями между ними. Задача проведения трасс сводится к получению последовательно­сти дискретов, соединяющих элементы а и b, соответству­ющие началу и концу проводимой трассы.

Вводим целевую функцию F=F(f1,...,fr) как критерий качества пути. Начиная с элемента а дискретам, соседним с ранее просмотренным, присваивают определенное зна­чение целевой функции Fij=m (i, j). Этот этап проводится итерационно до элемента b, которому присваивают неко­торое значение веса m(ib, jb). Затем, начиная от элемен­та b, перемещаются к элементу а по пройденным дискре­там таким образом, чтобы значения целевых функций дис­кретов монотонно убывали. В результате получается трасса, соединяющая элементы а и b.

Обычно работа алгоритма Ли реализуется следующим образом. На трассируемой плоскости из источника а моде­лируется распространение волны до тех пор, пока не будет достигнута точка b или пока на некотором шаге фронт волны не сможет включить ни одного незанятого дискрета. Эту часть алгоритма называют распространением волны. После этого проводят трассу, начиная от конечной точки b, по дискретам с последовательно уменьшающимися ве­сами. На рис. 9.14 цифры в квадратах соответствуют весам дискретов, занятые дискре­ты заштрихованы, а постро­енная трасса показана штриховой линией.

Рис. 9.14. Пример соединения эле­ментов а и b с помощью волно­вого алгоритма

Сущест­вует несколько вариантов проведения пути, из кото­рых конструктор (или ЭВМ) выбирает один, наи­более удовлетворяющий за­данным требованиям. Име­ется многообразие модифи­каций волновых алгорит­мов, направленных на по­вышение быстродействия трассировки, уменьшение объема требуемой опера­тивной памяти ЭВМ и т. д. Волновые алгоритмы широко применяют в различных областях техники, в частности при разработке се­тей связи и сетей ЭВМ.

9.14. Алгоритм распределения консультационных функций по модулям САК

Пусть задано множество консультационных функций, реализу­емых в САК (i = 1, 2, ...,), задано множество функциональных модулей САК

(j = 1, 2, .,.,). Необходимо так распределить функ­ции по модулям системы, чтобы достигнуть максимального значе­ния эффективности, не выходя из области допустимых ограниче­ний. Пусть Сij — затраты на реализацию i-й функции (консультационных операций) в j-м модуле, tij — время реализации функции в j-м модуле.

Вводим дополнительную переменную

Оптимизация распределения консультационных функций по модулям может производиться по одной из следующих целевых функций:

(9.132)

(9.133)

(9.134)

Функция (9.132) соответствует минимизации затрат, функция (9.133) — минимизации общего времени реализации консультационных функций, а функций (9.134) — минимизации максимального времени, реализации консультационной функции в модуле. При этом могут учитываться следующие ограничения:

а) связи между функциями (обычно задаются графом G (J), где J — множество функций;

б) связи между модулями, в состав которых входят техни­ческие средства (элементы) системы (обычно задаются графом G (J), где J — множество модулей);

в) ограничение на общее время реализации консультационных функций

если минимизируются затраты, либо ограничение на общие за­траты по реализации функций в САК