Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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





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

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

Формализованная формулировка

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

Тип оптимизационной задачи

Это частный очень простой случай задачи ЦЛП.

Алгоритмы решения

1. Алгоритм Прима.

2. Алгоритм Краскала.

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

Описание проектной задачи расслоения монтажа

 

Термин " расслоение монтажа" означает распределение элементов монтажа по слоям коммутационной платы.

Такими элементами монтажа (объектами расслоения) могут быть следующие четыре:

1. Подсхемы.

2. Электрические цепи.

3. Электрические соединения.

4. Трассы (расслоение после прокладки трасс).

В учебной САПР CROCUS-3 объектами расслоения являются электрические соединения.

Входные данные

1. Список соединений.

2. Число коммутационных слоев платы.

Выходные данные

Вектор (кортеж) распределения соединений по слоям платы.

Критерии качества

1. Минимальная степень конфликтности между элементами монтажа в каждом слое. Под конфликтом понимается потенциальное пересечение проводников.

2. Минимальное число межслойных переходов.

3. Минимальное число слоев платы (если оно не задано в качестве ограничения).

Математические модели

Граф конфликтов.

Формализованная формулировка

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

Тип оптимизационной задачи

Экстремальная задача комбинаторного типа.

Алгоритмы решения

1. Метод Магу [12].

2. Итерационные алгоритмы (один из них рассмотрен в данном разделе).

 

Описание проектной задачи упорядочения соединений

Большинство алгоритмов прокладки трасс используют последовательную стратегию: трассы прокладываются поочередно.

Упорядочение соединений (может быть и цепей) заключается в определении очередности, в которой будут прокладываться трассы соединений.

Входные данные

Список соединений.

Выходные данные

Упорядоченный список соединений.

Критерии качества (критерии оценки, сравнения соединений)

1. Длина соединения.

2. Степень конфликтности соединений.

3. Степень отклонения соединения от заданного в слое направления.







Дата добавления: 2014-11-10; просмотров: 657. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

Тактические действия нарядов полиции по предупреждению и пресечению групповых нарушений общественного порядка и массовых беспорядков В целях предупреждения разрастания групповых нарушений общественного порядка (далееГНОП) в массовые беспорядки подразделения (наряды) полиции осуществляют следующие мероприятия...

Механизм действия гормонов а) Цитозольный механизм действия гормонов. По цитозольному механизму действуют гормоны 1 группы...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

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

Правила наложения мягкой бинтовой повязки 1. Во время наложения повязки больному (раненому) следует придать удобное положение: он должен удобно сидеть или лежать...

Studopedia.info - Студопедия - 2014-2025 год . (0.011 сек.) русская версия | украинская версия