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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

1. Подсхемы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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