Решение задачи компоновки последовательным алгоритмом разбиения графа 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

Скачать архив (317.47 Кб) Сколько стоит заказать работу?

Файлы: 1 файл

Отчёт.docx

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

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

		x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	x₁₅	x₁₆	ρ
	x₁	0	2	0	1	1	1	0	0	0	0	0	0	0	0	0	0	5
	x₂	2	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	5
	x₃	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	2
	x₄	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	2
	x₅	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	3
	x₆	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0	4
A=	x₇	0	0	0	0	0	0	0	2	1	0	1	0	0	1	0	0	5
	x₈	0	0	0	0	0	0	2	0	0	0	0	1	0	0	0	0	3
	x₉	0	0	0	0	1	0	1	0	0	0	1	0	0	0	0	0	3
	x₁₀	0	0	0	0	0	0	0	0	0	0	5	0	0	0	0	0	5
	x₁₁	0	0	0	0	0	0	1	0	1	5	0	0	0	0	0	0	7
	x₁₂	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	2
	x₁₃	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	3	5
	x₁₄	0	0	0	0	0	1	1	0	0	0	0	0	1	0	1	0	4
	x₁₅	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	2
	x₁₆	0	0	1	0	0	0	0	0	0	0	0	0	3	0	1	0	5

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

		x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	x₁₅	x₁₆	ρ
	x₁	0	2	0	1	1	1	0	0	0	0	0	0	0	0	0	0	5
	x₂	2	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	5
	x₃	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	2
	x₄	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	2
	x₅	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	3
	x₆	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0	4
А⁰ =	x₇	0	0	0	0	0	0	0	2	1	0	1	0	0	1	0	0	5
	x₈	0	0	0	0	0	0	2	0	0	0	0	1	0	0	0	0	3
	x₉	0	0	0	0	1	0	1	0	0	0	1	0	0	0	0	0	3
	x₁₀	0	0	0	0	0	0	0	0	0	0	5	0	0	0	0	0	5
	x₁₁	0	0	0	0	0	0	1	0	1	5	0	0	0	0	0	0	7
	x₁₂	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	2
	x₁₃	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	3	5
	x₁₄	0	0	0	0	0	1	1	0	0	0	0	0	1	0	1	0	4
	x₁₅	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	2
	x₁₆	0	0	1	0	0	0	0	0	0	0	0	0	3	0	1	0	5

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

Г(x₁₁) = { x₁₁ , x₇, x₉, x₁₀}

		x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	x₁₅	x₁₆	ρ
	x₁	0	2	0	1	1	1	0	0	0	0	0	0	0	0	0	0	5
	x₂	2	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	5
	x₃	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	2
	x₄	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	2
	x₅	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	3
	x₆	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0	4
А⁰ =	x₇	0	0	0	0	0	0	0	2	1	0	1	0	0	1	0	0	5
	x₈	0	0	0	0	0	0	2	0	0	0	0	1	0	0	0	0	3
	x₉	0	0	0	0	1	0	1	0	0	0	1	0	0	0	0	0	3
	x₁₀	0	0	0	0	0	0	0	0	0	0	5	0	0	0	0	0	5
	x₁₁	0	0	0	0	0	0	1	0	1	5	0	0	0	0	0	0	7
	x₁₂	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	2
	x₁₃	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	3	5
	x₁₄	0	0	0	0	0	1	1	0	0	0	0	0	1	0	1	0	4
	x₁₅	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	2
	x₁₆	0	0	1	0	0	0	0	0	0	0	0	0	3	0	1	0	5

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

σ(x_j) = p(x_j) – a(x_j) = min σ (x_i).

		x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	x₁₅	x₁₆	ρ	σ
	x₁	0	2	0	1	1	1	0	0	0	0	0	0	0	0	0	0	5	5
	x₂	2	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	5	5
	x₃	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	1	2	2
	x₄	1	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	2	2
	x₅	1	1	0	0	0	0	0	0	1	0	0	0	0	0	0	0	3	2
	x₆	1	1	0	1	0	0	0	0	0	0	0	0	0	1	0	0	4	4
А⁰ =	x₇	0	0	0	0	0	0	0	2	1	0	1	0	0	1	0	0	5	3
	x₈	0	0	0	0	0	0	2	0	0	0	0	1	0	0	0	0	3	1
	x₉	0	0	0	0	1	0	1	0	0	0	1	0	0	0	0	0	3	1
	x₁₀	0	0	0	0	0	0	0	0	0	0	5	0	0	0	0	0	5	0
	x₁₁	0	0	0	0	0	0	1	0	1	5	0	0	0	0	0	0	7	0
	x₁₂	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	2	2
	x₁₃	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	3	5	5
	x₁₄	0	0	0	0	0	1	1	0	0	0	0	0	1	0	1	0	4	3
	x₁₅	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	2	2
	x₁₆	0	0	1	0	0	0	0	0	0	0	0	0	3	0	1	0	5	5

Т.е. элемент x_{8 .}

п.5. Количество элементов в массиве равно количеству элементов в первом куске разбиения, следовательно, кусок G₁ сформирован G₁ = {x₁₁, x₇ , x₉, x₁₀, x₈}

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

		x₁	x₂	x₃	x₄	x₅	x₆	x₁₂	x₁₃	x₁₄	x₁₅	x₁₆	ρ
	x₁	0	2	0	1	1	1	0	0	0	0	0	5
	x₂	2	0	1	0	1	1	0	0	0	0	0	5
	x₃	0	1	0	0	0	0	0	0	0	0	1	2
	x₄	1	0	0	0	0	1	0	0	0	0	0	2
	x₅	1	1	0	0	0	0	0	0	0	0	0	2
А¹ =	x₆	1	1	0	1	0	0	0	0	1	0	0	4
	x₁₂	0	0	0	0	0	0	0	1	0	0	0	1
	x₁₃	0	0	0	0	0	0	1	0	1	0	3	5
	x₁₄	0	0	0	0	0	1	0	1	0	1	0	3
	x₁₅	0	0	0	0	0	0	0	0	1	0	1	2
	x₁₆	0	0	1	0	0	0	0	3	0	1	0	5

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

		x₁	x₂	x₃	x₄	x₅	x₆	x₁₂	x₁₃	x₁₄	x₁₅	x₁₆	ρ
	x₁	0	2	0	1	1	1	0	0	0	0	0	5
	x₂	2	0	1	0	1	1	0	0	0	0	0	5
	x₃	0	1	0	0	0	0	0	0	0	0	1	2
	x₄	1	0	0	0	0	1	0	0	0	0	0	2
	x₅	1	1	0	0	0	0	0	0	0	0	0	2
А¹ =	x₆	1	1	0	1	0	0	0	0	1	0	0	4
	x₁₂	0	0	0	0	0	0	0	1	0	0	0	1
	x₁₃	0	0	0	0	0	0	1	0	1	0	3	5
	x₁₄	0	0	0	0	0	1	0	1	0	1	0	3
	x₁₅	0	0	0	0	0	0	0	0	1	0	1	2
	x₁₆	0	0	1	0	0	0	0	3	0	1	0	5

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