Информационная система "Конференции"

Тезисы докладов

вычислительная математика

Техническое проектирование радиоэлектронных средств (РЭС) предполагает в первую очередь решение задачи компоновки модулей в определённые конструктивные единицы. Для решения данной задачи используется математическая модель в виде графа, которым заменяется принципиальная электрическая схема проектируемого РЭС. Множество вершин обозначает радиоэлектронные компоненты (РЭК) проектируемого изделия, а множество рёбер – связи между ними в соответствии с принципиальной электрической схемой. Компоновка, т.е. распределение РЭК по определённым конструктивным электронным модулям, моделируется разрезанием графа на куски с заданным количеством вершин в каждом из них. Для оценки качества решения задачи разрезания графа используются количественные оценки, в частности, минимум внешних связей между сформированными кусками и коэффициент разрезания.

Разрезание графов осуществляется различными методами, чаще всего последовательными и итерационными. Последовательные методы легко реализуются на ЭВМ, отличаются простотой и высокой производительностью, но в большинстве случаев не обеспечивают оптимальных результатов [1, с. 61]. Итерационные методы позволяют получить лучшие результатов, однако полученные результаты также не всегда оптимальны. Среди итерационных методов наибольшей эффективностью обладает матричный метод [2, с. 62-70], но он применяется крайне редко. Ограниченность его использования объясняется тем, что кроме матрицы смежности исходного графа необходимо построить шесть вспомогательных матриц. Таким образом, в течение одной итерации обрабатываются семь матриц. Количество итераций зависит от чередования строк и столбцов в начальной матрице смежности и может быть неопределённо большим. Необходимость обработки больших числовых массивов накладывает существенные ограничения на номенклатуру проектируемых изделий по такому параметру, как количество РЭК, распределяемых по электронным модулям, а также на производительность процесса.

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

1. Матрица смежности в соответствии с заданным разрезанием разбивается на n подматриц, расположенных по главной диагонали. Порядок каждой подматрицы соответствует количеству вершин в формируемых кусках графа.
2. Для каждой вершины графа определяются числа связности с вершинами всех остальных кусков.
3. По числам связности вычисляются элементы матрицы перестановочных коэффициентов.
4. Формируется множество двухэлементных подмножеств, состоящих из пар вершин с положительным перестановочным коэффициентом.
5. Из полученного множества выявляют возможные варианты множеств, состоящих из двухэлементных непересекающихся подмножеств.
6. Для каждого полученного множества вычисляют сумму oepeqr`mnbnwm{u коэффициентов входящих в него пар вершин.
7. Выбирают множество, имеющее максимальную сумму перестановочных коэффициентов.
8. Попарно переставляют строки и столбцы матрицы смежности, соответствующие вершинам двухэлементных подмножеств из полученного на предыдущем шаге множества.

Описанные действия выполняются до тех пор, пока в матрице перестановочных коэффициентов не останется ни одного положительного перестановочного коэффициента.

Дополнительные материалы:

Полный текст доклада

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2005, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2005, Сибирское отделение Российской академии наук, Новосибирск