Решение задачи компоновки последовательным алгоритмом разбиения графа G=(X,E) на l кусков G_1,…G_l с числом вершин n_1,…n_l в каждом куске

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

Казанский национально исследовательский технический университет

им. А.Н. Туполева - КАИ

 

Факультет технической кибернетики и информатики

Кафедра ИТП ЭВС

 

 

 

Пояснительная записка к курсовой работе по дисциплине:

«Информационные технологии проектирования ЭВС»

на тему: Решение задачи компоновки последовательным алгоритмом разбиения графа G=(X,E) на кусков _{с числом вершин в каждом куске}»

 

 

 

Выполнила: студентка гр.4414

М.М. Демченко__________

Научный руководитель:

доцент кафедры ИТП ЭВС

В.В. Воронова___________

Оценка___________

«____» ______________2011 г.

 

 

 

                                                        

Казань 2011

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

Казанский национальный исследовательский технический университет

им. А.Н.Туполева - КАИ

 

Кафедра Информационных технологий проектирования ЭВС

 

ЗАДАНИЕ

на курсовую работу ИТПЭВС

Студентка   Демченко Марина Михайловна         Группа 4414                

Руководитель   Воронова Валентина Васильевна                     .

Дата выдачи задания 07.09.2011         Срок сдачи задания        28.12.2011

Тема задания

Решить задачу компоновки последовательным алгоритмом. Разработать программу, разбивающую произвольный граф на куски, используя последовательный алгоритм разбиения графа ) на   кусков _{с числом вершин} в каждом куске.

Исходные данные: схема соединений элементов рис.1, стр.11, n=16, l=3, число элементов в каждом куске:

 

 

 

 

Воронова  В. В._________________                                                          (Подпись)

2011 г.                                         

 

Оглавление

Введение…………………………………………………………………………...3

1.Теоретическая  часть…………………………………………………………….4

1.1. Постановка задачи компоновки………………………………………4

1.2. Алгоритмы компоновки……………………………………………….4

1.3. Последовательный алгоритм разбиения графа G=(X,E) на   кусков _{с числом вершин в каждом куске…………………………….}.7

2.Практическая  часть……………………………………………………………..8

2.1. Решение задачи компоновки………………………………………….8

2.2.Инструкция  пользователя……………………………………………10

3.Заключение……………………………………………………………………..12

4.Список  использованной литературы…………………………………………13

Приложение. Листинг программы……………………………………………...14

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретическая  часть

1.1. Постановка задачи  компоновки

Задача компоновки рассматривается  как задача принятия решения в  определенных или неопределенных условиях. Под задачей компоновки понимают объединение модулей низшего  уровня в модули более высокого уровня. Среди методов компоновки ЭВС  выделяются два класса:

Первый класс включает в себя задачи разбиения схемы на части. К   задачам  этого   класса   относятся:   распределение  ТЭЗ  по   панелям, распределение микросборок по печатным платам, разбиение коммутационной схемы на БИС или СБИС. В этом классе критерии оптимизации и ограничения могут быть сведены к определенным конструктивным параметрам расположения отдельных элементов и их межсоединений.

Второй класс включает задачи, которые возникают на этапе перехода от функционально-логической схемы (ФЛС) к коммутационной схеме, ориентированной на заданную  систему элементов, и состоят в назначении элементов логической схемы в типовые модули из заданного набора. Это так называемые задачи покрытия (компоновки типовых блоков).

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

В общем виде задача компоновки может быть сформулирована следующим  образом:

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

1.2. Алгоритмы компоновки

На этапе конструкторского проектирования решаются вопросы, связанные  с компоновкой элементов логической схемы в модули, модулей в ячейки, ячеек в панели и т. д. Эти задачи в общем случае тесно связаны  между собой, и их решение позволяет  значительно сократить затраты  и трудоемкость указанного этапа  в САПР. Обычно задачи компоновки рассматриваются  как процесс принятия решений  в определенных или неопределенных условиях, в результате выполнения которого части логической схемы  располагаются в конструктивных элементах i-го уровня, а эти элементы размещаются в конструктивных элементах (i+1)  уровня и т. д., причем расположение выполняется с оптимизацией по выбранному критерию.

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

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

Известные алгоритмы компоновки можно условно разбить на пять групп:

1. алгоритмы, использующие методы целочисленного программирования;
2. последовательные алгоритмы;
3. итерационные алгоритмы;
4. смешанные алгоритмы.

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

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

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

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

Если оказывается, что  мощность множества ½Г(x_i)½=n₁ для выбранной вершины, то первый кусок сформирован. Здесь n₁ – число вершин первого куска. Затем из матрицы смежности Е исключаются все вершины, вошедшие в первый кусок. Это означает, что из нее удаляются соответствующие строки и столбцы. Если окажется, что ½Г(x_i)½> n₁, то в этом случае необходимо из списка Г₁ удалить “лишние вершины”. При удалении такой вершины, ее связи с остающимися вершинами станут внешними, отсюда следует, что нужно удалить вершину, которая связана с остающимися вершинами меньшим числом ребер. Если окажется, что ½Г(x_i)½< n₁,  то  в   этом  случае  необходимо добавить  вершины  в  кусок G₁ по условию:

где   - локальная   степень вершины  x_j,

_-  количество  связей  вершины x_j  с ещё не вошедшими в кусок G₁ вершинами.

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

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

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

Оптимизация компоновки достигается  парными или групповыми перестановками вершин графа из различных кусков.

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

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

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

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

Сначала определяется нижняя оценка разбиения графа на заданное число частей. Затем производится построение дерева решений и осуществляется поиск оптимального результата.

Задачу разбиения графа  схемы на части можно свести к  задаче о назначении следующим образом.

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

 

1.3. Последовательный алгоритм разбиения графа G=(X,E) на   кусков _{с числом вершин в каждом куске}

Замечание. Формирования начинаем с вершины с наибольшей локальной степенью.

1.Вычисление  матрицы смежности .

2_{.Определение локальной степени каждой вершины}

 

3.Выбор  строки в матрице смежности,  соответствующей вершине наибольшей локальной степенью. Если , то

4.Формирование  массива вершин, смежных вершине причем Переход к п.5.

5. Если  количество вершин  в списке равно , то первый кусок сформирован и Переход к п.8, иначе к п.6.

6. Если , то из множества вершины, не вошедших в список выбирается вершина удовлетворяющая условию

 

где - вершин несколько, то берется вершина с большим значением список . Переход к п.5.

7.Если то из списка удаляются лишние вершины, то есть связанные с остающимися в куске меньшим числом ребер

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

9.Если  число сформированных кусков , то повторение алгоритма для формирования следующего куска с п.З. Если то переход к п. 10.

10. Конец  работы алгоритма

2. Практическая часть

2.1 Решение задачи компоновки

Дано:

1) Схема соединений  элементов (рис.1);

2) Число элементов  n=16;

3) Число кусков  разбиения l=3;

4) Число элементов  в каждом куске соответственно n₁=5, n₂=5, n₃=6.

 

        

                   Рис.1. Схема соединений элементов. 

Требуется:

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

 

 

 

Решение:

Описываем схему графом

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

п.1. Составим матрицу смежности:

		x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15	x16
	x1	0	2	0	1	1	1	0	0	0	0	0	0	0	0	0	0
	x2	2	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0
	x3	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1
	x4	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0
	x5	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0
	x6	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0
	x7	0	0	0	0	0	0	0	2	1	0	1	0	0	1	0	0
	x8	0	0	0	0	0	0	2	0	0	0	0	1	0	0	0	0
	x9	0	0	0	0	1	0	1	0	0	0	1	0	0	0	0	0
	x10	0	0	0	0	0	0	0	0	0	0	5	0	0	0	0	0
	x11	0	0	0	0	0	0	1	0	1	5	0	0	0	0	0	0
	x12	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0
	x13	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	3
	x14	0	0	0	0	0	1	1	0	0	0	0	0	1	0	1	0
	x15	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1
	x16	0	0	1	0	0	0	0	0	0	0	0	0	3	0	1	0