Отчёт к третей лабе
Описание файла
PDF-файл из архива "Отчёт к третей лабе", который расположен в категории "". Всё это находится в предмете "автоматизация проектирования" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "автоматизация проектирования" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
Ф ЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮМ ОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ(государственный технический университет)Кафедра 304(вычислительные машины, системы и сети)Лабораторная работа по курсу«Автоматизация проектирования»Отчёт по работе№3 .Волновые и лучевые алгоритмы трассировки соединений(наименование работы)Вариант задания№2 .Лабораторную работу выполнил:студент гр. 13-501, Резвяков Денис Михайлович(должность)(Ф. И.
О.)(подпись)Лабораторную работу принял:доцент каф. 304, Силаева Татьяна Александровна(должность)(Ф. И. О.)«.(подпись)»2010 г.(дата приёма)Цель работы: Изучить и практически овладеть волновымии лучевыми алгоритмами трассировки соединений в БИСи печатных платах.ЗаданиеПротрассировать соединения в следующей БИС из точки Aв точку B:Порядок выполнения работы1. Построить кратчайший путь с минимальным количествомизломов, соединяющий две заданные точки ДРП, с помощьюследующих четырёх методов: волнового, встречных волн,–2–однолучевого и двухлучевого.2. Проанализировать результаты и сформулировать выводы.1-1.
Построение кратчайшего пути волновым алгоритмомРаспространяя волну из точки A, достигаем точки B.Проанализировав полученную последовательность фронтовволны, находим путь от точки A до точки B с наименьшимчислом изломов:–3–1-2. Построение пути алгоритмом встречных волнРаспространяем волны из точек A и B до момента встречидвух волн. Проанализировав полученные последовательностифронтов волн, находим путь от точки A до точки B с наименьшим числом изломов:–4–1-3. Построение пути однолучевым алгоритмомРаспространяем по одному лучу из точек A и B по соответствующим приоритетам направлений до их пересечения(или вырождения). Находим путь от точки A до точки B:–5–1-4. Построение пути двухлучевым алгоритмомРаспространяем по два луча из точек A и B по соответствующим приоритетам направлений до пересечения двух лучейиз разных точек (или их вырождения). Находим путь от точки Aдо точки B:–6–2.
Анализ результатов и выводыВолновой алгоритм дал идеальный вариант проведениясоединения с минимальным числом изломов, однако на трассировку этим методом ушло достаточно много времени и пришлосьпроанализировать почти все дискреты рабочего поля.Алгоритм встречного распространения волн дал такой жерезультат. На его выполнение потребовалось немного меньшевремени и анализа дискретов.Однолучевой алгоритм дал вариант проведения соединениятакой же длины, но с чуть большим количеством изломов, чтотоже является хорошим результатов. А времени на его выполнение понадобилось гораздо меньше.Двухлучевой алгоритм дал другое положение соединения,но такое же по длине и количеству изломов.
Однако времени напоследний алгоритм было потрачено практически в два разабольше, чем на однолучевой алгоритм из-за одновременногопроведения двух лучей из источника и из цели.Волновые алгоритмы, в отличие от лучевых: просты;решение дают всегда, если оно существует; позволяют найтикратчайший путь. Лучевые алгоритмы, в отличие от волновых:быстры; требуют гораздо меньше времени и ресурсов памяти.Лучевой алгоритм может не дать решения, если на рабочемполе имеется много занятых ячеек, а волновой алгоритм работает очень долго, если на рабочем поле много свободных ячеек.–7–В результате можно сформулировать следующие принципы:Целесообразнее всего, для трассировки первых по очерёдности соединений, когда на дискретном рабочем поле оченьмало препятствий, использовать однолучевой алгоритм трассировки. Затем, когда число препятствий несколько увеличится,следует использовать двухлучевой алгоритм.
Когда препятствийстанет достаточно много, следует переключиться на методвстречных волн. И, если при трассировании последних по очерёдности соединений будет совсем мало свободных дискретов,то целесообразнее будет использовать обычный волновойалгоритм, т.к. для него в такой ситуации потребуется меньшевычислительных затрат.–8–.