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

Автор работы: Пользователь скрыл имя, 20 Мая 2013 в 14:54, курсовая работа

Описание работы

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

Содержание работы

Введение…………………………………………………………………………...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 файл

Отчёт.docx

— 329.76 Кб (Скачать файл)

п.2. Вычислим:

 

   

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

5

 

x2

2

0

1

0

1

1

0

0

0

0

0

0

0

0

0

0

5

 

x3

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

2

 

x4

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

2

 

x5

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

3

 

x6

1

1

0

1

0

0

0

0

0

0

0

0

0

1

0

0

4

A=

x7

0

0

0

0

0

0

0

2

1

0

1

0

0

1

0

0

5

 

x8

0

0

0

0

0

0

2

0

0

0

0

1

0

0

0

0

3

 

x9

0

0

0

0

1

0

1

0

0

0

1

0

0

0

0

0

3

 

x10

0

0

0

0

0

0

0

0

0

0

5

0

0

0

0

0

5

 

x11

0

0

0

0

0

0

1

0

1

5

0

0

0

0

0

0

7

 

x12

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

2

 

x13

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

3

5

 

x14

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

4

 

x15

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

 

x16

0

0

1

0

0

0

0

0

0

0

0

0

3

0

1

0

5


 

п. 3. В матрице А0 графа G определяем элемент с наибольшей локальной степенью (p).


   

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

5

 

x2

2

0

1

0

1

1

0

0

0

0

0

0

0

0

0

0

5

 

x3

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

2

 

x4

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

2

 

x5

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

3

 

x6

1

1

0

1

0

0

0

0

0

0

0

0

0

1

0

0

4

А0 =

x7

0

0

0

0

0

0

0

2

1

0

1

0

0

1

0

0

5

 

x8

0

0

0

0

0

0

2

0

0

0

0

1

0

0

0

0

3

 

x9

0

0

0

0

1

0

1

0

0

0

1

0

0

0

0

0

3

 

x10

0

0

0

0

0

0

0

0

0

0

5

0

0

0

0

0

5

 

x11

0

0

0

0

0

0

1

0

1

5

0

0

0

0

0

0

7

 

x12

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

2

 

x13

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

3

5

 

x14

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

4

 

x15

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

 

x16

0

0

1

0

0

0

0

0

0

0

0

0

3

0

1

0

5


 

 

  

п. 4. Формируем массив вершин смежных вершине x11.

  Г(x11) = { x11 , x7 , x9 , x10}

 

   

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

5

 

x2

2

0

1

0

1

1

0

0

0

0

0

0

0

0

0

0

5

 

x3

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

2

 

x4

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

2

 

x5

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

3

 

x6

1

1

0

1

0

0

0

0

0

0

0

0

0

1

0

0

4

А0 =

x7

0

0

0

0

0

0

0

2

1

0

1

0

0

1

0

0

5

 

x8

0

0

0

0

0

0

2

0

0

0

0

1

0

0

0

0

3

 

x9

0

0

0

0

1

0

1

0

0

0

1

0

0

0

0

0

3

 

x10

0

0

0

0

0

0

0

0

0

0

5

0

0

0

0

0

5

 

x11

0

0

0

0

0

0

1

0

1

5

0

0

0

0

0

0

7

 

x12

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

2

 

x13

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

3

5

 

x14

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

4

 

x15

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

 

x16

0

0

1

0

0

0

0

0

0

0

0

0

3

0

1

0

5


 

 

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

σ(xj) = p(xj) – a(xj) = min σ (xi).

 

   

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

5

5

 

x2

2

0

1

0

1

1

0

0

0

0

0

0

0

0

0

0

5

5

 

x3

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

2

2

 

x4

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

2

2

 

x5

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

3

2

 

x6

1

1

0

1

0

0

0

0

0

0

0

0

0

1

0

0

4

4

А0 =

x7

0

0

0

0

0

0

0

2

1

0

1

0

0

1

0

0

5

3

 

x8

0

0

0

0

0

0

2

0

0

0

0

1

0

0

0

0

3

1

 

x9

0

0

0

0

1

0

1

0

0

0

1

0

0

0

0

0

3

1

 

x10

0

0

0

0

0

0

0

0

0

0

5

0

0

0

0

0

5

0

 

x11

0

0

0

0

0

0

1

0

1

5

0

0

0

0

0

0

7

0

 

x12

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

2

2

 

x13

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

3

5

5

 

x14

0

0

0

0

0

1

1

0

0

0

0

0

1

0

1

0

4

3

 

x15

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

2

 

x16

0

0

1

0

0

0

0

0

0

0

0

0

3

0

1

0

5

5


Т.е. элемент x8 .

п.5. Количество элементов в массиве равно количеству элементов в первом куске разбиения, следовательно, кусок G1 сформирован G1 = {x11 , x7 , x9 , x10, x8}

 

п. 8.  Исключаем из G кусок G1 формируя матрицу А1.

   

x1

x2

x3

x4

x5

x6

x12

x13

x14

x15

x16

ρ

 

x1

0

2

0

1

1

1

0

0

0

0

0

5

 

x2

2

0

1

0

1

1

0

0

0

0

0

5

 

x3

0

1

0

0

0

0

0

0

0

0

1

2

 

x4

1

0

0

0

0

1

0

0

0

0

0

2

 

x5

1

1

0

0

0

0

0

0

0

0

0

2

А1 =

x6

1

1

0

1

0

0

0

0

1

0

0

4

 

x12

0

0

0

0

0

0

0

1

0

0

0

1

 

x13

0

0

0

0

0

0

1

0

1

0

3

5

 

x14

0

0

0

0

0

1

0

1

0

1

0

3

 

x15

0

0

0

0

0

0

0

0

1

0

1

2

 

x16

0

0

1

0

0

0

0

3

0

1

0

5


 

 

п. 3. В матрице А1 определяем элемент с наибольшей локальной степенью (p).


   

x1

x2

x3

x4

x5

x6

x12

x13

x14

x15

x16

ρ

 

x1

0

2

0

1

1

1

0

0

0

0

0

5

 

x2

2

0

1

0

1

1

0

0

0

0

0

5

 

x3

0

1

0

0

0

0

0

0

0

0

1

2

 

x4

1

0

0

0

0

1

0

0

0

0

0

2

 

x5

1

1

0

0

0

0

0

0

0

0

0

2

А1 =

x6

1

1

0

1

0

0

0

0

1

0

0

4

 

x12

0

0

0

0

0

0

0

1

0

0

0

1

 

x13

0

0

0

0

0

0

1

0

1

0

3

5

 

x14

0

0

0

0

0

1

0

1

0

1

0

3

 

x15

0

0

0

0

0

0

0

0

1

0

1

2

 

x16

0

0

1

0

0

0

0

3

0

1

0

5

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