Математическая формулировка задачи

УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Заочно-вечерний факультет

Кафедра «Проектирования и Технология Электронных Средств»

Лабораторная работа № 5

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

ТРАССИРОВКИ ПРОВОДНЫХ СОЕДИНЕНИЙ

Работу выполнил:                                                        Работу принял:      

студент группы Рбв-31                                                преподаватель кафедры

Латыпов М.Р.                                                               Мактас М.Я.

_____________                                                              _______________

Ульяновск

2018

Цель работы – исследовать эффективность алгоритмов трассировки проводных соединений методом «внавал»; освоить особенности алгоритмизации и программирования задачи трассировки проводов на ПЭВМ; приобрести навыки построения математических моделей проводных соединений, реализации и исследования их при решении задачи трассировки с применением САПР.

АЛГОРИТМЫ ТРАССИРОВКИ ПРОВОДОВ

Задача проектирования соединений, иначе трассировка соединений, возника-ет на последних этапах проектирования радиоэлектронных средств (РЭС) и является одной из наиболее сложных задач в общей проблеме автоматизации проектирования РЭС [1-5]. Связано это с многообразием способов конструк-торско-технологической реализации соединений, каждый из которых обусловливает использование специфических критериев оптимизации и ограни-чений при алгоритмическом решении этой задачи.

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

В современных РЭС трассировку проводных соединений производят двумя способами [1-2]:

– по прямым, соединяющим отдельные выводы модулей (монтаж «внавал»);

– по ортогональным направлениям – с помощью жгутов.

Достоинство монтажа «внавал»: простота при выполнении и высокая помехоустойчивость, т. к. он позволяет сократить до минимума общую длину проводников и протяженность участков их параллельного прохождения.

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

При жгутовом монтаже проводники объединяются в жгуты (перевязанные прочной нитью проводники), которые укладываются в специальные каналы.

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

Недостатки: неприемлем при создании высокочастотной и чувствительной к электрическим помехам аппаратуре. Основные ограничения при проводном монтаже – количество проводников, которые можно подсоединить к одному выводу (обычно не более трех) и число проводов в каждом жгуте.

Теоретически к одному выводу может быть подсоединено не более шести проводников. Это легко понять из чертежа, представленного на рис.1. Допус-тим, точки a₁, a₂, …, a_n удалены от точки О на расстояние R. Тогда можно считать, что эти точки расположены на окружности с радиусом R (рис.1, а). Из геометрии известно, что в круг вписывается правильный шестиугольник со стороной, равной радиусу круга (рис.1, б). Очевидно, что в данном случае ми-нимальное дерево в вершинах O, a₁, a₂, a₃, a₄, a₅, a₆ только шестиугольника имеет суммарную длину ребер, равную 6R (рис.1, в, г). Причем максимальную локальную степень ρ = 6 будет иметь вершина O в звездном варианте такого дерева (рис.1, в). Любая дополнительная вершина a₇ на расстоянии R от вершины O будет уже ближе к одной из точек a_i (рис.1, д, е). Поэтому ρ_max = 6.

Математическая формулировка задачи

В общем виде задача формулируется следующим образом [2]. В системе координат XYZ, связанной с коммутационным пространством модуля, задано местоположение множества выводов . Это множество M разобьем в соответствии с электрической схемой соединений на непере-секающиеся подмножества M⁽¹⁾, M⁽²⁾,…,M^(k), каждое из которых включает в себя выводы, подлежащие электрическому объединению. Для каждого подмножества , i = 1, 2, …, k требуется определить последовательность соединений выводов и конфигурацию проводников, обеспечивающих при заданных ограничениях минимальную суммарную длину соединений.

Практически задача сводится к отысканию дерева с минимальной суммарной длиной ребер (построению кратчайшей связывающей сети). Согласно теореме Кэли на n вершинах может быть построено t = n^(n-2) деревьев. Поэтому при большом числе выводов в электрической цепи эта задача становится сложной.

Для определения минимального дерева на заданных n вершинах можно построить все возможные деревья и выбрать минимальное из них. Однако в РЭC число цепей исчисляется сотнями, поэтому поиск всех деревьев практи-чески нереален. К тому же существующие алгоритмы построения минимальных деревьев позволяют находить глобально-оптимальные или близкие к ним решения (при отсутствии ограничений на количество проводников, подсоединяемых к одному выводу). Поэтому эта задача является одной из немногих задач теории графов, которые считают полностью решенными [8]. Рассмотрим используемые в САПР алгоритмы Дж. Краскала и Р. К. Прима.

Алгоритм Краскала

Алгоритм Краскала реализует следующую процедуру [1, 2, 9].

Множество контактов n электрической цепи моделируют n вершин графа. На них строится полный граф. Число ребер в полном графе r = [n (n-1) / 2]. Из списка ребер полного графа последовательно выбираются самые короткие ребра до тех пор, пока не получится дерево.

Особенностью этого алгоритма является возможность параллельного образования нескольких поддеревьев, которые затем объединяются в единое дерево – остов.

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

( n – 1 ) ребер.

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

Проверка ребра на образование цикла выполняется с помощью таблицы меток вершин N_i, где i = 1, 2, …, n. В начале работы алгоритма в этой таблице все вершины имеют разные метки (например, свой номер N_i = i). Если две изолированные i и j вершины объединяются во фрагмент, то происходит поглощение меток: N_i присваивается значение N_j или наоборот. Аналогично обстоит дело и при образовании более сложных фрагментов: если два фраг-мента объединяются ребром r_ij в один, то все метки вершин получают одинако-вое значение N_i, обычно минимальное из сравниваемых. По таблице меток легко проверить, образует ли очередное выбранное ребро цикл или нет: цикл образуется в том случае, если соединяемые вершины имеют одинаковые метки.

Алгоритм позволяет строить дерево и с ограничениями на степени  вершин, однако в этом случае получение минимального дерева не гарантируется.

Рис. 5.1.

Если локальные степени вершин не должны превышать двух, то задача построения минимального дерева сводится к задаче построения гамильтоновой цепи минимальной длины: пройти по всем вершинам графа, но не возвращаться в исходную вершину [6 – 9].

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

АЛГОРИТМ

1. На множестве вершин (выводов) M⁽ⁱ⁾ построить взвешенный полный граф (число ребер в нем n(n-1)/2). Для этого вычислить элементы матрицы расстояний  по одной из формул:

               или         (5.1)

,                                    (5.2)

где  и  – координаты i-й и j-й позиций монтажного пространства.

Формулой (5.1) пользуются для монтажа «внавал», а формулой (5.2) – при жгутовом монтаже.

2. Всем элементам, лежащим на главной диагонали и ниже её, присваивается значение . Присвоить нулевое значение длине L рёбер искомого дерева: L = 0; i = 0; j = 0.

3. Сформировать таблицу меток и локальных степеней вершин: ; ; ; ; .

4. Присвоить .

5. Найти минимальный элемент  матрицы .

6. Если , то идти к 4.

7. Если  или , то идти к 4.

8. Поглощение меток: все метки нового фрагмента получают значение , а локальные степени соединенных вершин –  и .

9. Включить ребро  во множество R ребер минимального дерева, а длину дерева увеличить на длину ребра: .

10. Если , то идти к 4, в противном случае к 11.

11. Минимальное дерево построено. R – множество его ребер, а L – суммарная их длина.

 Конец.

Алгоритм Прима

Алгоритм Прима реализует следующую процедуру [1 – 7].

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

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

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

Для реализации алгоритма составляют матрицу расстояний , элемент  которой вычисляют по одной из формул (5.1) или (5.2). Просматривают элементы первой строки матрицы D и находят минимальный элемент. Пусть таким оказался элемент g-го столбца, тогда весь 1-й и g-й столбцы матрицы D исключаются из рассмотрения, а первое соединение проводится между точками  и . Просматриваются 1-я и g-я строки матрицы с оставшимися элементами. Из элементов этих строк находится минимальный. Предположим, что им оказался элемент, принадлежащий j-му столбцу. Если этот элемент находится на пересечении с первой строкой, то точку  соединяем с 1-й точкой ( ), если же он находится на пересечении с g-й строкой, то точку  соединяем с g-й ( ), после чего из матрицы D исключаем все элементы j-го столбца. Просматриваются 1-я, g-я и j-я строки и т. д.

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

АЛГОРИТМ

1. Вычислить элементы матрицы расстояний  по одной из формул – (5.1) или (5.2).

2. Найти минимальный элемент матрицы , где ; . Номера строки и столбца q и p, на пересечении которых он находится, определяют номера вершин  и , соединяемых ребром.

3. Занести номера вершин во множество , построенное ребро – во множество .

4. Подсчитать локальные степени  и , подлежащих соединению на данном шаге вершин  и .

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

6. Найти . Здесь , , т. е. среди еще не вошедших в дерево вершин отыскать вершину , минимально удаленную от некоторой вершины дерева .

7. Дополнить множества ; .

8. Проверить, все ли вершины графа соединены ветвями . Если условие выполняется, идти к 9, иначе – к 4.

Конец.

ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ