Алгоритмы в ортогональном режиме.
Рис. 11 Алгоритм Краскала в ортогональном режиме.
Рис. 12 Алгоритм Прима в ортогональном режиме.
Выводы: Оба рассмотренных алгоритма позволяют при выполнении соответствующих условий находить глобально-оптимальные или близкие к ним решения.
При этом для работы алгоритма Краскала требуется n ( n -1)/2 памяти ЭВМ для записи исходных данных, однако в процессе работы необходимо дополни-тельное время для проверки ребер на образование циклов.
Для работы алгоритма Прима памяти необходимо n 2, но зато отсутствует необходимость проверки ребер на образование циклов.
Следовательно, алгоритм Краскала требует в два с лишним раза меньше памяти, чем алгоритм Прима; зато машинного времени меньше необходимо при расчёте по алгоритму Прима. Кроме этого надо отметить, что алгоритм Краскала более прост при реализации.
ЛАБОРАТОРНАЯ РАБОТА № 7
ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ
ТРАССИРОВКИ ПЕЧАТНЫХ И ПЛЕНОЧНЫХ СОЕДИНЕНИЙ
Цель работы – исследовать эффективность алгоритмов трассировки печатных и пленочных соединений; освоить особенности алгоритмизации и программирования задач трассировки печатных соединений на современных ЭВМ волновыми и лучевым алгоритмами; приобрести навык построения математических моделей объектов конструирования, реализации и иссле-дования их при решении задачи трассировки в САПР.
|
|
|
СВЕДЕНИЯ ИЗ ТЕОРИИ
Многие методы трассировки печатных соединений основаны на идеях волнового алгоритма, предложенного С. Ли. Он представляет собой развитие алгоритмов построения кратчайших путей в сети и позволяет находить маршруты соединений, оптимальные по ряду параметров. Данный алгоритм является классическим примером использования методов динамического программирования.
Волновой алгоритм C. Ли
Монтажное поле разбивается на элементарные ячейки. Размеры ячеек и их количество определяются площадью поля, допустимой плотностью расположения выводов элементов и проводников. В простейшем случае ячейка представляет собой квадрат со стороной h, равной расстоянию между средними линиями двух соседних печатных проводников
На первом этапе из одной из заданных ячеек ДРП – источника моделируется распространение числовой волны до тех пор, пока ее фронт не достиг второй отмеченной ячейки ДРП – цели, либо наступает момент, когда в оче-редной фронт нельзя включить ни одну новую не занятую ячейку ДРП.
В первом случае искомый путь существует, во втором – нет.
Все условия, которые необходимо выполнить при проведении соединения, в том числе и условия оптимальности, должны быть заложены в правила движе-ния волны, т. е. в правила построения очередного фронта волны. В процессе распространения волны ячейкам ДРП присваиваются весовые оценки, связанные с принятым критерием оптимальности.
|
|
|
На втором этапе алгоритма осуществляется проведение пути. Для этого следует, начиная от ячейки-цели, двигаться в направлении, противоположном направлению волны, переходя последовательно от ячейки с большим весом к соседней ячейке с меньшим весом до тех пор, пока не будет достигнута ячейка-источник. Ячейки ДРП, выделенные в ходе указанного процесса, и определяют искомое оптимальное соединение.
Ручное проведение пути
1) Моделируеме распространение числовой волны по 4 либо по 8 направлениям.
2) Проводимкратчайший путь по минимальным значениям ячеек.
3) Соединяем
| 9 | 2 | 1 | 2 | 3 | |||||||||||||||||
| 8 | 1 | 1 | 2 | ||||||||||||||||||
| 7 | 2 | 1 | 2 | 3 | |||||||||||||||||
| 6 | 3 | 2 | 3 | 4 | |||||||||||||||||
| 5 | 4 | 3 | 4 | 5 | |||||||||||||||||
| 4 | 5 | 4 | 6 | 7 | 8 | 9 | 10 | 11 | |||||||||||||
| 3 | 6 | 8 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||||||||||
| 2 | 7 | 8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | ||||
| 1 | 8 | 9 | 10 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | |||
| 0 | 9 | 10 | 11 | 12 | 13 | 14 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | |||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
Результат распространения числовой волны по 4 направлениям и проведения пути.
|
|
|
|
|
|
| 9 | 1 | 1 | 1 | 2 | 3 | 4 | |||||||||||||||
| 8 | 1 | 1 | 2 | 3 | 4 | ||||||||||||||||
| 7 | 1 | 1 | 1 | 2 | 4 | ||||||||||||||||
| 6 | 2 | 2 | 2 | 2 | 4 | ||||||||||||||||
| 5 | 3 | 3 | 3 | 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 14 | 15 | 16 | 17 | |||
| 4 | 4 | 4 | 4 | 4 | 4 | 5 | 6 | 7 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |||||
| 3 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | ||||
| 2 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ||||
| 1 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | ||
| 0 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
Результат распространения числовой волны по 8 направлениям и проведения пути.
Сравним результаты с результатми прикладной программы САПР
Рис.13, 14 Результат трассировки по 4 и 8 направлениям Алгоритм ЛИ.
Достоинства волнового алгоритма: возможность нахождения пути мини-мальной длины в любом лабиринте, если существует хотя бы один путь в нем.
Недостатками волнового алгоритма Ли являются малое быстродействие и большой объем оперативной памяти ЭВМ, необходимый для хранения инфор-мации о текущем состоянии всех ячеек коммутационного поля.
Алгоритм Акерса
Наиболее экономичный способ кодирования состояний ячеек коммутаци-онного поля предложен Акерсом. При распространении волны ячейки поля получают отметки в соответствии с базовой последовательностью 1, 1, 2, 2, 1, 1, 2, 2, … . Данная последовательность характерна тем, что в ней любой член имеет разных соседей слева и справа. Вначале все незанятые ячейки, соседние с ячейкой-источником, помечаются 1, затем все ячейки фронта 
помечаются так же 1. Далее отметка 2 присваивается ячейкам фронта 
и т. д.
Для построения пути в общем случае необходимо найти требуемую подпо-следовательность отметок базовой последовательности. Это легко может быть сделано по отметке ячейки цели и отметке соседней с ней ячейки.
| 9 | 1 | 1 | 1 | 2 | 2 | ||||||||||||||||
| 8 | 1 | 1 | 1 | 2 | |||||||||||||||||
| 7 | 1 | 1 | 1 | 2 | |||||||||||||||||
| 6 | 2 | 2 | 1 | 2 | |||||||||||||||||
| 5 | 2 | 2 | 2 | 1 | 1 | 2 | |||||||||||||||
| 4 | 1 | 2 | 1 | 2 | 2 | 1 | 1 | 2 | |||||||||||||
| 3 | 1 | 2 | 2 | 2 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 1 | 1 | ||||
| 2 | 2 | 2 | 2 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | ||||
| 1 | 2 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | ||
| 0 | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 2 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
Результат распространения волны и проведения пути по алгоритму Акерса.
Рис. 15 Результат трассировки алгоритм Акерса.
Лучевой алгоритм
Основная идея алгоритма, предложенного Л. Б. Абрайтисом заключается в исследовании поля для определения пути между ячейками A и B по некоторым заранее заданным направлениям, подобным лучам. Это позволяет сократить число просматриваемых алгоритмом ячеек, а, следовательно, и время на анализ и кодировку их состояний, однако снижает вероятность нахождения пути сложной конфигурации и усложняет учет конструктивных требований к технологии печатной платы.
Работа алгоритма заключается в следующем. Задается число лучей, распространяемых из ячейки A и B, а также порядок присвоения путевых координат. Обычно число лучей для каждой из ячеек (источников) принимают одинаковым (часто равным двум). Лучи 
, 
, …, 
и 
, 
, …, 
считаются одноименными, если они распространяются из одноименных источников A или B. Лучи 
и 
являются разноименными по отношению друг к другу. Распространение лучей происходит одновременно из обоих источников до встречи двух разноименных лучей в некоторой точке C.
Путь проводится из ячейки C, в которой встретились лучи по путевым координатам, и проходит через ячейки, по которым распространялись лучи.
При распространении луча может возникнуть ситуация, когда две соседние ячейки будут заняты. В этом случае луч считается заблокированным и его распространение прекращается.
| 9 | А | А2 | С | ||||||||||||||||||
| 8 | |||||||||||||||||||||
| 7 | В2 | ||||||||||||||||||||
| 6 | |||||||||||||||||||||
| 5 | |||||||||||||||||||||
| 4 | А1 | ||||||||||||||||||||
| 3 | |||||||||||||||||||||
| 2 | В1 | В | |||||||||||||||||||
| 1 | |||||||||||||||||||||
| 0 | |||||||||||||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
Результат. Лучи сходятся в точке С , кратчайший путь найден.
Рис. 16 Результат трассировки лучевым алгоритмом.
Достоинства алгоритма: получение соединений минимальной длины и высокое быстродействие.
Недостаток: не всегда находит решение, хотя оно может существовать, при трассировке двухслойных плат с ортогональной коммутацией с помощью лучевого алгоритма удается построить до 70% трасс, а остальные проводят, используя волновой алгоритм или вручную.
Поэтому лучевой алгоритм целесообразно применять для трассировки плат с небольшой степенью заполнения ячеек или в начальной стадии трассировки
Вывод: исследовали эффективность алгоритмов трассировки печатных и пленочных соединений; освоили особенности алгоритмизации и программирования задач трассировки печатных соединений на современных ЭВМ волновыми и лучевым алгоритмами; приобрели навык построения математических моделей объектов конструирования, реализации и иссле-дования их при решении задачи трассировки в САПР.
Дата добавления: 2019-07-17; просмотров: 337; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!