Последовательные алгоритмы компоновки

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

1.2.1. Метод максимальной конъюнкции – минимальной дизъюнкции

Основной критерий разбиения графа на куски – минимум числа соединяющих ребер между кусками графа. Если формировать куски Последовательные алгоритмы компоновки - student2.ru графа G так, чтобы каждый из кусков во множестве Последовательные алгоритмы компоновки - student2.ru содержал возможно большее число ребер, то при этом получится локальный минимум суммарного числа K соединяющих ребер.

Рассмотрим метод максимальной конъюнкции – минимальной дизъюнкции [1, 4].

Пусть дана схема с множеством элементов Последовательные алгоритмы компоновки - student2.ru , соединенных между собой множеством электрических цепей Последовательные алгоритмы компоновки - student2.ru . Ее необходимо скомпоновать в узлы, включающие по t элементов. Число внешних связей узлов не должно превышать z (z – число контактов в разъеме).

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

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

При работе алгоритма схема представляется в виде графа Кенига Последовательные алгоритмы компоновки - student2.ru , в котором подмножество вершин E и V интерпретируют соответственно множества элементов E и электрических цепей V. При этом вершина Последовательные алгоритмы компоновки - student2.ru соединяется с вершиной Последовательные алгоритмы компоновки - student2.ru ребром Последовательные алгоритмы компоновки - student2.ru в том случае, когда элемент Последовательные алгоритмы компоновки - student2.ru принадлежит цепи Последовательные алгоритмы компоновки - student2.ru . Для вычисления на ЭВМ граф Последовательные алгоритмы компоновки - student2.ru задается матрицей инцидентности Последовательные алгоритмы компоновки - student2.ru , в которой число строк n определяется количеством элементов схемы, а столбцов m – количеством электрических цепей. Элемент Последовательные алгоритмы компоновки - student2.ru , стоящий на пересечении i-й строки и j-го столбца, равен 1, если элемент Последовательные алгоритмы компоновки - student2.ru подключен к цепи Последовательные алгоритмы компоновки - student2.ru , и нулю в противном случае.

АЛГОРИТМ

1. Ввод матрицы Последовательные алгоритмы компоновки - student2.ru .

2. По матрице Последовательные алгоритмы компоновки - student2.ru определяем локальные степени вершин Последовательные алгоритмы компоновки - student2.ru :

Последовательные алгоритмы компоновки - student2.ru .

3. Из множества нераспределенных вершин E выбираем вершину Последовательные алгоритмы компоновки - student2.ru с локальной степенью Последовательные алгоритмы компоновки - student2.ru .

4. Назначаем выбранную вершину Последовательные алгоритмы компоновки - student2.ru во множество Последовательные алгоритмы компоновки - student2.ru , формируемого узла.

5. Строку Последовательные алгоритмы компоновки - student2.ru матрицы Последовательные алгоритмы компоновки - student2.ru , соответствующую назначенной вершине Последовательные алгоритмы компоновки - student2.ru , модифицируем путем поразрядной дизъюнкции со строками матрицы, соответствующими нераспределенным элементам:

Последовательные алгоритмы компоновки - student2.ru ; Последовательные алгоритмы компоновки - student2.ru ;…

6. Определяем суммы элементов Последовательные алгоритмы компоновки - student2.ru в модифицированных строках Последовательные алгоритмы компоновки - student2.ru .

7. Из множества строк Последовательные алгоритмы компоновки - student2.ru выбираем такие, в которых Последовательные алгоритмы компоновки - student2.ru . Объединяем их во множество Последовательные алгоритмы компоновки - student2.ru .

8. Если Последовательные алгоритмы компоновки - student2.ru , то переходим к 17, иначе к 9.

9. Строку Последовательные алгоритмы компоновки - student2.ru матрицы Последовательные алгоритмы компоновки - student2.ru , соответствующую элементу Последовательные алгоритмы компоновки - student2.ru , модифицируем путем поразрядной конъюнкции со строками множества Последовательные алгоритмы компоновки - student2.ru :

Последовательные алгоритмы компоновки - student2.ru ;…

10. Определяем суммы Последовательные алгоритмы компоновки - student2.ru элементов в модифицированных строках Последовательные алгоритмы компоновки - student2.ru .

11. Из множества строк Последовательные алгоритмы компоновки - student2.ru выбираем такую, в которой Последовательные алгоритмы компоновки - student2.ru .

12. Вершину Последовательные алгоритмы компоновки - student2.ru , дающую Последовательные алгоритмы компоновки - student2.ru назначаем в формируемый узел Последовательные алгоритмы компоновки - student2.ru .

13. Если Последовательные алгоритмы компоновки - student2.ru , то идти к 17, иначе к 14.

14. Определяем множество нераспределенных элементов Последовательные алгоритмы компоновки - student2.ru . Если Последовательные алгоритмы компоновки - student2.ru , то идти к 19, иначе к 15.

15. Составляем матрицу Последовательные алгоритмы компоновки - student2.ru . Для чего в исходной матрице Последовательные алгоритмы компоновки - student2.ru вместо строк, соответствующих элементам, назначенным в узел Последовательные алгоритмы компоновки - student2.ru , записываем дизъюнкцию всех указанных строк.

16. Идти к 5.

17. Узел Последовательные алгоритмы компоновки - student2.ru считаем сформированным. Поэтому преобразуем матрицу Последовательные алгоритмы компоновки - student2.ru . Исключаем из нее строки, соответствующие элементам, включенным в узел Последовательные алгоритмы компоновки - student2.ru . Получаем матрицу Последовательные алгоритмы компоновки - student2.ru .

18. Идти к 2.

19. Конец.

ПРИМЕР 2.1

Пусть дана схема соединений (рис. 2.1, а), которую необходимо скомпоновать в узлы, содержащие не более трех элементов Последовательные алгоритмы компоновки - student2.ru , и каждый узел имеет не более пяти выводов Последовательные алгоритмы компоновки - student2.ru .

Граф схемы представлен на рис. 2.1, б.

Решение

По матрице Последовательные алгоритмы компоновки - student2.ru исходного графа определяем локальные степени вершин и приписываем их справа к каждой строке матрицы (число цепей, подключенных к каждому элементу схемы):

Последовательные алгоритмы компоновки - student2.ru      
Последовательные алгоритмы компоновки - student2.ru

Максимальную локальную степень, равную трем, имеют вершины Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru . В качестве исходной выбираем 1-ю по порядку Последовательные алгоритмы компоновки - student2.ru . (Процесс компоновки иллюстрируем таблицей 1.1). Выполним дизъюнкции 1-й строки Последовательные алгоритмы компоновки - student2.ru , соответствующей Последовательные алгоритмы компоновки - student2.ru , с остальными строками:

Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru ,

Последовательные алгоритмы компоновки - student2.ru

Рис. 2.1

Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru и т. д.

Находим суммы элементов в дизъюнкциях: Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru .

Выбираем вершины, имеющие Последовательные алгоритмы компоновки - student2.ru , и включение которых в формируемый узел не превысит условия Последовательные алгоритмы компоновки - student2.ru . Такими являются вершины Последовательные алгоритмы компоновки - student2.ru , у которых Последовательные алгоритмы компоновки - student2.ru .

Выполним конъюнкцию 1-й строки со строками отобранных элементов Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru :

Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru ,

Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru и т. д.

Вычисляем суммы элементов в конъюнкциях Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru . Выбираем вершину Последовательные алгоритмы компоновки - student2.ru , величина Последовательные алгоритмы компоновки - student2.ru у которой максимальна, и включаем ее в узел Последовательные алгоритмы компоновки - student2.ru .

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

Для этого модифицируем матрицу Последовательные алгоритмы компоновки - student2.ru .

Вместо 1-й и 2-й строк в ней запишем дизъюнкцию этих строк.

Получим матрицу Q2:

Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru    
 
 
 
 

Снова вычисляем дизъюнкции строки Последовательные алгоритмы компоновки - student2.ru со всеми остальными и определяем суммы элементов в них.

Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru ,

Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru и т. д.

Результаты суммирований запишем справа от каждой строки матрицы Последовательные алгоритмы компоновки - student2.ru . Минимальную Последовательные алгоритмы компоновки - student2.ru имеют Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru . Причем Последовательные алгоритмы компоновки - student2.ru . После выполнения конъюнкции строки Последовательные алгоритмы компоновки - student2.ru с остальными строками и суммирования элементов в результирующих строках получим

Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru ,

Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru и т. д.

Справа от матрицы Последовательные алгоритмы компоновки - student2.ru запишем Последовательные алгоритмы компоновки - student2.ru . Максимальное значение Последовательные алгоритмы компоновки - student2.ru имеет вершина Последовательные алгоритмы компоновки - student2.ru . Ее и включаем в узел Последовательные алгоритмы компоновки - student2.ru : Последовательные алгоритмы компоновки - student2.ru . Итак, узел Последовательные алгоритмы компоновки - student2.ru сформирован, поскольку в него назначено три элемента. Число внешних связей у Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru .

Аналогично формируем второй узел Последовательные алгоритмы компоновки - student2.ru , рассматривая оставшиеся вершины Последовательные алгоритмы компоновки - student2.ru . Для этого из исходной матрицы Последовательные алгоритмы компоновки - student2.ru исключаем строки, соответствующие элементам Последовательные алгоритмы компоновки - student2.ru . Получим:

Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
   
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru

После определения локальных степеней вершин первой в формируемый узел Последовательные алгоритмы компоновки - student2.ru назначаем Последовательные алгоритмы компоновки - student2.ru .

Вычисление дизъюнкции и конъюнкции строки Последовательные алгоритмы компоновки - student2.ru , соответствующей Последовательные алгоритмы компоновки - student2.ru , с остальными строками (см. Последовательные алгоритмы компоновки - student2.ru ) позволило назначить в узел Последовательные алгоритмы компоновки - student2.ru элемент Последовательные алгоритмы компоновки - student2.ru . Для назначения следующего элемента модифицируем Последовательные алгоритмы компоновки - student2.ru :

Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru    
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru

Нахождение дизъюнкций и конъюнкций Последовательные алгоритмы компоновки - student2.ru с остальными позволило укомплектовать Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru .

Дальнейшее формирование узла Последовательные алгоритмы компоновки - student2.ru происходит следующим образом.

Ef = E / T1 / T2 = {5, 6, 7}. Получаем матрицу:

Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
   
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru

Максимальную локальную степень имеет Последовательные алгоритмы компоновки - student2.ru , следовательно, Последовательные алгоритмы компоновки - student2.ru . Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru у вершин Последовательные алгоритмы компоновки - student2.ru и Последовательные алгоритмы компоновки - student2.ru одинаковы, поэтому выбираем Последовательные алгоритмы компоновки - student2.ru : Последовательные алгоритмы компоновки - student2.ru . Наконец, в результате модификации имеем:

Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru    
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru

По результатам дизъюнкции и конъюнкции в узел Последовательные алгоритмы компоновки - student2.ru распределен последний элемент: Последовательные алгоритмы компоновки - student2.ru , Последовательные алгоритмы компоновки - student2.ru .

Условия задачи выполнены. Схема скомпонована в узлы по три элемента и число внешних соединений каждого не превышает пяти (рис.2.1, в). Динамика процесса компоновки элементов в узлы представлена в таблице 2.1. Здесь n – номер формируемого узла, E – множество распределяемых на данном шаге элементов, Последовательные алгоритмы компоновки - student2.ru – число подключённых к элементу цепей, ei – назначенный в узел элемент, Et – множество оставшихся элементов, c(qik) – число цепей, подключённых к i-му и k-му элементам (дизъюнкция), S(bik) – число цепей, соединяющих i-й и k-й элементы (конъюнкция), Tn – множество элементов назначенных в узел с номером n.

Граф схемы, разрезанный на три куска, приведён на рис. 2.2, а схема, скомпонованная в три блока – на рис. 2.3. Качество компоновки оценим по коэффициенту разбиения DG схемы.

Общее число цепей между блоками Последовательные алгоритмы компоновки - student2.ru , число цепей внутри блоков Последовательные алгоритмы компоновки - student2.ru .

Тогда коэффициент разбиения схемы Последовательные алгоритмы компоновки - student2.ru .

Выводы

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

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

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

Таблица 2.1

Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru     Последовательные алгоритмы компоновки - student2.ru  
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru  
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru    
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru     Последовательные алгоритмы компоновки - student2.ru    
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru            
  Последовательные алгоритмы компоновки - student2.ru                  
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru  
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru          
  Последовательные алгоритмы компоновки - student2.ru                  
Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru   Последовательные алгоритмы компоновки - student2.ru Последовательные алгоритмы компоновки - student2.ru       Последовательные алгоритмы компоновки - student2.ru
  Последовательные алгоритмы компоновки - student2.ru                 Последовательные алгоритмы компоновки - student2.ru

Последовательные алгоритмы компоновки - student2.ru

Рис. 2.2

Последовательные алгоритмы компоновки - student2.ru

Рис. 2.3

ДОМАШНЕЕ ЗАДАНИЕ

2.1. Ознакомиться с методами решения задачи компоновки схем РЭС [1 – 5].

2.2. Изучить последовательный алгоритм компоновки (метод максимальной конъюнкции – минимальной дизъюнкции).

2.3. Подготовить данные для проведения эксперимента. Для этого полученный вариант схемы соединения конструктивных модулей представить математической моделью в виде графа Кёнига.

2.4. Предложить вариант компоновки «вручную» схемы по алгоритму.

3. ПОРЯДОК РАБОТЫ С ПРОГРАММОЙ «КОМПОНОВКА»

Алгоритм последовательной компоновки конструктивных элементов и узлов схем в узлы высшего уровня реализован в пакете учебной САПР PSAPRна ПЭВМ программой Pskomp – «Компоновка». Программа позволяет:

- компоновать элементы в блоки с минимизацией числа связей между блоками;

- учитывать число контактов в разъемах, устанавливаемых в блоках;

- назначать в блоки не больше заданного числа элементов;

- получать результат в графическом виде.

Для запуска программы «Компоновка» установить курсор на окно «Компоновка блока» (оно будет в зелёной рамке) и нажать Enter. Появится рабочее поле графического редактора «Компоновка» (см. рис.1.3.2 работы №1).

В верхней части экрана размещены слева направо следующие зоны:

- элементов. В ней указаны типы элементов, из которых можно набирать на рабочем поле схему электрическую принципиальную;

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

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

Справочная информация о работе с программой выводится на экран после нажатия клавиши F1 – Помощь (рис.2.4).

В центральной части экрана помещено дискретное рабочее поле, на котором набирается электрическая схема. Для её формирования надо установить красный прямоугольник (курсором или стрелками) в нужное место экрана и нажать клавишу Insert. На поле появится тот элемент, который в данный момент будет отображаться в левой верхней зоне. Смена типа элемента осуществляется нажатием серой клавиши « – » или щелчком ЛК мыши по элементу в верхней зоне (рис.2.5).

После того, как на поле установлены все элементы схемы, их необходимо соединить цепями. Для этого надо перейти в режим ввода цепей – нажать на серую клавишу «*» или указать на неё курсором и щелкнуть ЛК.

Вместо красного прямоугольника на рабочем поле появится «+». Для соединения контактов элементов цепью необходимо установить + на край 1-го контакта и нажать клавишу Insert. На краю контакта появится красная точка. Затем перемещать курсор ко 2-му контакту. При этом на каждом изгибе цепи нажимать широкую клавишу «Пробел» и будет появляться прямолинейный фрагмент строящейся цепи. После завершения цепи дважды нажать клавишу «Пробел». На 2-м контакте также появится красная точка. Это признак построения цепи (рис.2.5).

В нижней части экрана размещена строка с указаниями клавиш и названий основных команд редактора.

Кроме этого система позволяет загружать схему, соответствующую результатам покрытия (предыдущей работы). Для этого надо нажать одновременно клавиши Alt + F3. На экран будет выведена схема (рис.2.5).

Последовательные алгоритмы компоновки - student2.ru

Рис.2.4

Последовательные алгоритмы компоновки - student2.ru

Рис.2.5

Зададим условия компоновки. Назначим в узлы по три элемента, а разъем зададим из пяти контактов. Для этого в верхней строке экрана для 1-го и 2-го узлов зададим по 3 элемента. Надо нажимать на клавишу 1 до тех пор, пока не появится тройка, затем также на клавишу цифры 2, либо, установив на них курсор, щёлкать ЛК мыши до тех пор, пока не установится цифра 3. Для установки числа контактов в разъеме нажимать на клавишу буквы «z» или щёлкать курсором по цифре «Максимальное число внешних связей». Установить число 5 (рис.2.6).

Последовательные алгоритмы компоновки - student2.ru

Рис.2.6

После того как схема сформирована, можно приступать к решению задачи компоновки. Для этого надо нажать клавишу Enter. По запросу системы выбрать ручной режим. После этого на экране появятся исходные данные для расчета (рис.2.7): сверху слева матрица инцидентности, справа – сумма элементов в строках, дизъюнкция, конъюнкция и номера строк. Снизу пояснения и результаты работы алгоритма. Нажатием клавиши Enter можно по шагам выполнить весь расчёт. Результаты будут выведены на экран (рис.2.8).

Повторное нажатие на клавишу Enter выводит на экран результат компоновки элементов исходной схемы в блоки (рис.2.9).

Последовательные алгоритмы компоновки - student2.ru

Рис.2.7

Последовательные алгоритмы компоновки - student2.ru

Рис.2.8

Последовательные алгоритмы компоновки - student2.ru

Рис.2.9

Наши рекомендации