close

Вход

Забыли?

вход по аккаунту

?

3-Шахов(1)

код для вставкиСкачать
Федеральное агентство по образованию
Тверской государственный технический университет
Кафедра ЭВМ
Конструкторско-Техническое Обеспечение.
Лабораторная работа ( 3
"РЕШЕНИЕ ЗАДАЧИ ПОКРЫТИЯ СХЕМЫ БИС ЭВРИСТИЧЕСКИМ АЛГОРИТМОМ ПРИ КОМПОНОВКЕ"
Выполнил: Шеховцов С., ФАС-0303
Проверил: Тверь 2006 г.
Задание:
Выполните размещение схемы, представленной ниже, а также представьте эту схему лесом Т.
Размер монтажной сетки: длина - 4, высота - 3
Результаты:
Размещение схемы:
Представление схемы лесом Т:
Ответы на теоретические вопросы:
1. Критерии оптимизации схемы при размещении.
Суть задачи размещения заключается в определении оптимального положения элементов, а также связи между ними в монтажном пространстве.
При удовлетворении конструкторско-технических ограничений:
- Зоны запрещённого монтажа (трассировки)
Используют следующие критерии определения качества решения задачи размещения:
1. Минимум суммарной длины всех соединений
2. Минимум длины самой длинной связи
3. Минимум числа пересечений
4. Максимум числа цепей с возможно более простой конфигурацией
5. Максимально близкое расположение модулей, имеющих наибольшее количество связей между собой.
Будем считать, что соединение, исходящее из геометрических центров конструктивных элементов, где расстояние по горизонтали и вертикали одинаково. По данной математической модели монтажного пространства, будет граф решётка , а расстояние между позициями определяется матрицей расстояний . Внешним выводам элементов поставим в соответствии элемент , а соединение с ним элементов их множества E учтём вектором столбцов взвешенных связей. Контактные площадки (кроме разъёмов) инвариантны. Тогда для некоторого размещения суммарная взвешенная длина соединений будет равна: - элемент матрицы , который определяет расстояние между позициями установки и - номер вертикального ряда (ордината), в котором расположен элемент Главная цель размещения - создание наилучших условий для трассировки.
2. Суть алгоритма улучшения размещения схемы итерационным алгоритмом.
Для улучшения некоторого начального размещения меняют местами те элементы, перестановка которых приводит к оптимизации критериев качества.
Правила окончания перестановок:
1. Не существует перестановок улучшающих критерии качества
2. Разных значений критериев качества для двух соседних итераций меньше некоторого заданного значения
Исходные данные: - Соединение элементов определяется матрицей смежностей R
- Расстояние между соседними элементами определяется матрицей позиций - Элементы матрицы R и должны полностью соответствовать друг другу по индексам. При этом элементы матрицы R должны располагаться в соответствии с порядковыми номерами, позицией и установкой, т.е. в матрице R 1-ая строка характеризует связанность элемента R с .
При перестановке элементов местами происходит перестановка соответствующих строк и столбцов матрицы .
Суммарная взвешенная длина соединений L(a) рассчитывается поэлементно перемножением матриц R и .
В выражении для подсчёта значения приращения функционала будет иметь вид: S - индекс элемента не участвующего в перестановке
Для уменьшения числа возможных перестановок, элементы упорядочивают по суммарной длине связи каждого элемента с остальными.
Где номера или индексы нумеруют по убыванию После окончания итераций подсчитают новое значение суммарной длины связи, и процесс повторяется.
Основные пункты алгоритма
1. Определяем порядок просмотра элементов. Для заданного размещения находим суммарную длину связей по формуле (2) и упорядочиваем индекс по убыванию (суммарной длины связи), т.е. формируем последовательность индексов 2. Для текущего элемента последовательности по формуле (1) определяем приращение функционала , где 3. Находим максимальное приращение функционала 4. Проверяем условие , если "ДА", то в последовательности I меняем местами и , "ИНАЧЕ" на пункт 6.
5. Корректируем матрицу , при этом переставляем местами строки и столбцы с индексами и .
6. Проверяем окончание цикла итераций , если "ДА", то пункт 7, "ИНАЧЕ" k=k+1 и пункт 2.
7. Проверяем окончание итерационного процесса , если "ДА", то на пункт 8, "ИНАЧЕ" на пункт 1.
8. Конец работы алгоритма
2
Документ
Категория
Рефераты
Просмотров
13
Размер файла
170 Кб
Теги
шахов
1/--страниц
Пожаловаться на содержимое документа