Алгоритм Краскала трассировки проводного монтажа

 

Министерство образования и науки РФ

Рязанский Государственный Радиотехнический Университет

Кафедра САПР ВС

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

на курсовую работу

по дисциплине «Автоматизация конструкторского и технологического проектирования»

на тему: «Алгоритм Краскала трассировки проводного монтажа»

Выполнил: Горбунов Р.Ю.

Проверил: доц. кафедры САПР ВСКарманов П.В.

Рязань 2014

Содержание

Введение

.Практическая и математическая постановка задачи

.Анализ существующих алгоритмов решения задачи

.Описание разрабатываемого алгоритма, его укрупненная схема

.Развернутая блок схема алгоритма

.Контрольный пример

.Перечень идентификаторов

.Текст программы

.Листинг с результатами машинного решения

Заключение

Список литературы

Введение

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

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

В данном курсовом проекте будет рассматриваться алгоритм Краскала трассировки проводного монтажа.

алгоритмический трассировка монтаж печатный

1. Практическая и математическая постановка задачи

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

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

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

Расстояние между каждой парой вершин полного подграфа для проводников, идущих по кратчайшему направлению:

, (1)

для ортогональной трассировки

. (2)

Здесь и - координаты i-й и j-й вершин графа.

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

Ставится задача построения КСД на тех комп-х связности число вершин которых>2.

Отметим, что на n вершинах полного графа можно построить tn деревьев.

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

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

Пусть задан G=(X,V) i,j=1,n, i?j

Каждому ребру Vij поставлено в соответствие число Cij - вес или длина данного ребра.

Ставится задача: среди всех деревьев (n-(n-2)), кот. м. выделить в данном графе, требуется найти дерево с минимальной длиной в дереве (n-1) ребро.

Пусть C=[cij]n*n матрица длины ребер графа.

. Все ребра графа n(n-1)\2 упорядочиваются в порядке убывания длины, начиная с ребра C1=mini,jCij, Cn=maxi,jCij

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

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

На рис 1. показан процесс построения минимального покрывающего дерева алгоритмом Краскала.

Рис 1.

2. Анализ существующих алгоритмов решения задачи

Задача трассировки состоит в построении для всех цепей схемы оптимальных монтажных соединений. Метрический аспект задачи предполагает учет конструктивных размеров элементов, соединений и коммутационного поля. Топологический аспект связан с выбором допустимого пространственного расположения отдельных монтажных соединений при ограничениях на число пересечений соединений, число слоев коммутационной схемы и т. п. Классификация методов трассировки представлена на рис. 2.

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

1. топографические методы - в них приоритет отдается метрическому аспекту задачи;
2. графо-теоретические метод решения задач трассировки.

Топографический метод трассировки содержит следующие этапы:

1. получение списка соединений;
2. распределение соединений по слоям;
3. определение порядка прокладки соединений;
4. трассировка отдельных соединений.

Основной задачей первого этапа является предварительное определение порядка соединений выводов внутри отдельных цепей. Такое упорядочение осуществляется с помощью алгоритмов построения минимальных деревьев. При печатном монтаже соединения могут выполняться не только по выводам, но и в любой точке проводника. Поэтому построение КСД формулируется как задача Штейнера. Метод же решения задачи Штейнера требует больших затрат машинного времени.

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

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

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

1. волновой алгоритм и его модификации;
2. алгоритмы трассировки по магистралям и каналам;
3. комбинированные алгоритмы.

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

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

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

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

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

К этой же группе примыкают эвристические алгоритмы построения малоповоротных путей, в которых осуществляется построение соединений простой конфигурации (до 3-4 изгибов). По имеющимся данным, подобные алгоритмы позволяют осуществить разводку до 90% всех соединений в двухслойных схемах с ортогональными соединениями. Остальные соединения трассируются с помощью волнового алгоритма.

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

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

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

3. Описание разрабатываемого алгоритма, его укрупненная схема

1. Для всех пар полного подграфа считываем длины соединяющих их рёбер.

. Упорядочиваем рёбра по возрастанию их длин.

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

Блок-схема алгоритма представлена на рисунке 3.

Рис.3 Укрупненная блок-схема разрабатываемого алгоритма

4. Развёрнутая блок-схема алгоритма

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

Рис.4.1 Укрупненная блок-схема программы

·Схема алгоритма заполнения массива ребер представлена на рисунке 4.2

Рис.4.2 Схема алгоритма заполнения массива ребер

Схема алгоритма сортировки ребер по возрастанию их длин представлена на рисунке 4.3

Сортировка массива ребер происходит методом пузырьковой сортировки.

Рис.4.3 Схема алгоритма сортировки

·Схема алгоритма Краскала построения КС дерева представлена на рисунке 4.4

Рис.4.4 Схема алгоритма Краскала построения КС дерева

5. Контрольный примера

Требуется построить КСД для цепи содержащей 6 контактов. Полный граф на рис:

Рис.5 Полный граф

Пусть матрица длин ребер графа цепи имеет вид:

U= n = 6; n*(n-1) = 15

. Упорядочивание длин ребер полного графа

- 15 элементов.

.1. Включаем в в дерево получаем 1-ую изолированную компоненту связности.

.2. Включаем в дерево , получаем 2-ую изолированную компоненту связности (2,3).

.3. Включаем - получаем 3-ю изолированную компоненту связности (4,5).

.4. Включаем - получаем 4-ю изолированную компоненту связности (1,6,4,5).

Ребро образовывает цикл - брать нельзя.

Ребро тоже образовывает цикл - брать нельзя.

.5. Включаем в дерево . КСД построено.

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

Недостатки:

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

)Большое время уходит на упорядочивание ребер полного графа.

6. Перечень идентификаторов

type

RBR=record

x1,x2:integer; {Начальная и конечная вершины ребра}

ves:integer; {Вес ребра}

rebro:array of RBR; {Массив ребер}

trassa:array of RBR; {Массив ребер, включенных в КС дерево}:array of integer; {Массив вершин, включенных в дерево}:boolean; {Логическая переменная, определяющая, входит ли вершина в массив вершин, включенных в дерево}, trassaLen, rebroLen:integer; {Длины стока, массива ребер, включенных в дерево, массива ребер}

i, j, k:integer; {Счетчики цикла}:string; {Упорядоченный список ребер}: string; {Список ребер, включенных в дерево}

7. Текст программы

Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Grids, StdCtrls, ComCtrls;=record,x2:integer;:integer;;= class(TForm): TGroupBox;: TLabel;: TEdit;: TStringGrid;: TButton;: TButton;: TButton;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;Edit1KeyUp(Sender: TObject; var Key: Word;: TShiftState);Button1Click(Sender: TObject);Button3Click(Sender: TObject);Button2Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;:array of RBR;:array of RBR;:array of integer;,trassaLen:integer;,j,k,rebroLen:integer;:boolean;

{$R *.dfm}TForm1.Edit1KeyUp(Sender: TObject; var Key: Word;: TShiftState);: integer;Edit1.Text='' then Edit1.Text:='0';:=StrToInt(Edit1.Text);.ColCount:=num;.RowCount:=num;;TForm1.Button1Click(Sender: TObject);,j: integer;.Visible:=false;.Caption:='';.Visible:=false;.Visible:=false;.Caption:='';.Visible:=false;.Text:='0';i:=0 to stringgrid1.ColCount-1 doj:=0 to stringgrid1.RowCount-1 do.Cells[i,j]:='';.ColCount:=1;.RowCount:=1;;TForm1.Button3Click(Sender: TObject);;;TForm1.Button2Click(Sender: TObject);,q,k,l,Dlina:integer;:RBR;,j:integer;:string;:integer;: string;:=0;:=0;i:=0 to Strtoint(edit1.text)-1 do beginj:=0 to Strtoint(edit1.text)-1 do(i<j) and (Stringgrid1.cells[i,j]<>'0') then begin:=rebroLen+1;(rebro,rebroLen);[k].x1:=i+1;[k].x2:=j+1;[k].Ves:=Strtoint(Stringgrid1.cells[i,j]);:=k+1;;;end;i:=0 to k-1 doj:=0 to k-i-2 dorebro[j].Ves>rebro[j+1].Ves then:=rebro[j];[j]:=rebro[j+1];[j+1]:=buf;;:='';i:=0 to k-1 do:=put+' '+'X'+inttostr(rebro[i].x1)+'X'+inttostr(rebro[i].x2)+'('+inttostr(rebro[i].Ves)+')';(put);:=2;(stock,2);[0]:=rebro[0].x1;[1]:=rebro[0].x2;:=1;(trassa,1);[0]:=rebro[0];i := 1 to length(rebro)-1 do:=0;:=false;k<>stockLen dorebro[i].x2=stock[k] then inSt:=true;:=k+1;;inSt=false then

//rebro[i].Fl:=true;

//добавление нового в сток:=stockLen+1;

setlength(stock,stockLen);[stockLen-1]:=rebro[i].x2;

//составление рёбер:=trassaLen+1;(trassa,trassaLen);[trassaLen-1]:=rebro[i];

//поменяем вершины местами:=0;:=false;k<>stockLen dorebro[i].x1=stock[k] then inSt:=true;:=k+1;;inSt=false then:=rebro[i].x1;[i].x1:=rebro[i].x2;

rebro[i].x2:=p;

//добавление нового в сток

stockLen:=stockLen+1;(stock,stockLen);[stockLen-1]:=rebro[i].x2;

//составление рёбер:=trassaLen+1;(trassa,trassaLen);[trassaLen-1]:=rebro[i];;;;.Visible:=true;.Visible:=true;.Visible:=true;:=0;:='';i := 0 to length(trassa)-1 do:=Dlina+trassa[i].Ves;:=tr+' | '+inttostr(trassa[i].x1)+'--'+inttostr(trassa[i].x2)+' | ';.Caption:=' - '+tr+' -';.Caption:='Dlina = '+inttostr(Dlina);

end;.

8. Листинг с результатами машинного решения

Исходные данные

Отсортированный массив ребер

Ребра, входящие в дерево и длина соединения

Заключение

В результате выполнения данной курсовой работы была создана программа, выполняющая трассировку проводного монтажа алгоритмом Краскала. Программа была написана с использованием среды разработки Delphi и сконфигурирована для работы под управлением операционных систем семейства Microsoft Windows.

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

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

Список литературы

1. Селютин В. А. Машинное конструирование электронных устройств. М.: Сов. радио, 1977.

. Савельев А.Я. Овчинников В.А «Конструирование ЭВМ и систем»

. Конспект лекций

Министерство образования и науки РФ Рязанский Государственный Радиотехнический Университет Кафедра САПР ВС

Больше работ по теме: