Некоторые алгоритмы структурной декомпозиции управляющих систем | Вестн. Том. гос. ун-та. 2000. № 271.

Некоторые алгоритмы структурной декомпозиции управляющих систем

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

Some algorithms for solving structure decomposition problems of control systems.pdf Управляющие системы представляют собой объекты дискретной природы и характеризуются функцией и структурой. Способы задания функциональных харак-.теристик очень многообразны и включают в себя системы уравнений, формулы, микропрограммы и пр. Структура управляющей системы задаётся схемой. Под структурной декомпозицией управляющих систем в данной работе понимается задача декомпозиции соответствующих схем. Задачи структурной декомпозиции возникают при исследовании управляющих систем на стыке логического и конструкторского этапов проектирования, когда требуется распределить заданную схему устройства по конструктивным блокам - интегральным микросхемам, базовым ячейкам или стандартным элементам БИС, а те, в свою очередь, - по печатным платам, базовым кристаллам или матричным БИС в заданном монтажном пространстве с обеспечением конструкторских и технологических ограничений. Схема [ 1 ] задается тройкой объектов (X, Z, Zo), где X-множество элементов схемы, Z - множество её цепей и ZqcZ- множество её внешних цепей или полюсов. Элемент схемы определяется множеством своих полюсов и весом - некоторой количественной характеристикой сложности элемента. По определению, множества полюсов различных элементов в схеме не пересекаются. Цепь схемы - это подмножество множества полюсов элементов в схеме. Она может дополнительно характеризоваться весом - значением некоторого параметра её физического исполнения (толщины, кратности и т.п.). По определению, различные цепи схемы (элементы множества Z) не пересекаются, и их объединение есть множество всех полюсов элементов схемы. Схема S=(Y, U, U0) называется подсхемой схемы (X, Z Zo), если YcX, ие U тогда и только тогда, когда ucz для некоторого zeZ и в к входят все полюсы из Z, принадлежащие элементам в У, и Uoe U0 тогда и только тогда, когда uo«Z или u^eZo, в этом случае говорят, что подсхема S порождена подмножест-92 вом элементов Y. По определению, вес цепи и подсхемы совпадает с весом цепи z з и схемы. Поскольку порождающее подмножество определяет подсхему однозначно, имеется _ возможность там, где это не вызывает двусмысленности, рассматриваемые подсхемы отождествлять с их порождающими подмножествами, говоря, например, «подсхема У» вместо «подсхема (К, U, Щ». В дальнейшем для упрощения изложения мы будем пользоваться этой возможностью без дополнительных оговорок. Соответственно этому к подсхемам будем применять любые теоретико-м но-жественные операции и отношения. Задачи декомпозиции схем рассматриваются в следующей постановке. Заданы схема S=(X, Z, Zo), отношение несовместимости v на множестве X её элементов, тройка положительных чисел w, q и р и система подмножеств А,,...^4т из X; требуется разбить S на минимальное число подсхем так, что: a) любые два элемента в каждой подсхеме совместимы; b) сумма весов элементов каждой подсхемы не превосходит числа н>; c) сумма весов цепей каждой подсхемы не превосходит числа q; d) сумма весов полюсов каждой подсхемы не превосходит числа р\ e) элементный состав каждой подсхемы является подмножеством, содержащимся хотя бы в одном из заданных подмножеств А..,ЛтсЛг. Здесь и далее элементы схемы называются совместимыми, если они не находятся в заданном отношении v, и подмножество элементов называется множеством совместимости, если все они попарно совместимы. В известном смысле числа w, q и р ограничивают сложность компоненты искомого разбиения, а ограничение а) означает, что множество элементов каждой такой компоненты должно быть множеством совместимости. Различные подмножества множества ограничений {а, Ь, с, d, е} в постановке задачи определяют частные задачи. Некоторые из них являются хорошо известными комбинаторными задачами Так, ограничение а) определяют задачу раскраски графа [2] - в нашем случае графа С={Х, v), а ограничение Ь) - задачу разбиения множества чисел на классы с ограниченной суммой [3], известную как вариант задачи загрузки [4]. Ограничение е) определяет задачу покрытия булевой (с элементами 0 и 1) матрицы М=11 mj | задающей подмножества Lh содержащиеся в некоторых заданных множествах Ль..., А^оХ по правилу V/ е {1...../}vy е X = {1,..., п\ту = 1 j е I,). В каждой частной задаче, определяемой подмножеством Д ограничений из {a,b,c,d,e}, подсхемы, удовлетворяющие выбранному подмножеству Д, будем называть допустимыми. Ясно, что понятие допустимости в каждой такой задаче зависит от выбранного подмножества Д и распространяется только на рассматриваемую подзадачу. Понятие допустимости подсхемы (схемы) распространю* на множество порождающих еб, злемещоэ. Подсхемы или порождающие подмножества элементов в разбиении будем называть блоками разбиения, а блоки, удовлетворяющие заданному набору ограничений, - допустимыми блоками разбиения. Разбиение с минимальным числом классов в дальнейшем будем называть кратчайшим, а кратчайшее разбиение на допустимые блоки -кратчайшим допустимым разбиением. Тогда сформулированную выше задачу разбиения схемы S на минимальное число допустимых подсхем можно рассматривать как задачу кратчайшего разбиения множества элементов схемы на допустимые блоки. Наряду с рассмотренными задачами кратчайшей декомпозиции при исследовании управляющих систем возникает ещё одна разновидность декомпозиционных задач - задачи упорядоченной декомпозиции. Для их формулировки введём некоторые определения. Последовательность подмножествХь...,Хк множества X, в которой все непустые подмножества различны и образуют разбиение множества X, называется упорядоченным разбиением данного множества и обозначается (Х\,..., Л*); подмножества Х\,..., Xt суть классы этого разбиения. Обратим внимание на основные отличия упорядоченного разбиения от неупорядоченного: 1) классами упорядоченного разбиения может быть и пустое множество; 2) порядок перечисления классов в упорядоченном разбиении существен, любое его изменение порождает, вообще говоря, новое упорядоченное разбиение. Для формулировки задачи упорядоченного разбиения в условия предыдущей задачи добавим ещё некоторое заданное натуральное число Л>1 и числовую неотрицательную функцию F, определённую на любых упорядоченных разбиениях (Уь ... любого подмножества элементов YgX схемы S. Тогда задача заключается в нахождении такого упорядоченного разбиения K=(Xh..., Л*) множества X элементов схемы S на к блоков, для которого каждый непустой блок является допустимым в смысле ограничений {a,b,c,d,e} и числовая функция F\K) принимает на этом разбиении минимальное значение. Такое разбиение в дальнейшем называется минимальным допустимым разбиением. Сформулированную выше задачу о кратчайшей декомпозиции в дальнейшем для краткости будем называть задачей декомпозиции типа I, а задачу о минимальном упорядоченном разбиении - задачей декомпозиции типа П. Если в последней задаче значение функции F положить равным числу непустых блоков в разбиении Х^, то любая задача типа I сводится к задаче о минимальном упорядоченном разбиении. В принципе, любую задачу декомпозиции можно решить тривиальным перебором всех возможных разбиений множества X, выбором среди них допустимых, а среди последних - минимальных или кратчайших. Объём перебора при таком подходе оценивается числом всех возможных разбиений л-элементного множества, которое вычисляется по следующей рекуррентной формуле м [1]: Ля = £ С'~_\ Rn_t, где Ло=1. Число таких разбиений с i=i ростом п растёт значительно быстрее, чем 2я, поэтому тривиальный подход осуществим лишь для задач с чис-лрм, Э|/тементоч 9 разбиваемом множестве порядка нескольких десятков. Для практических же целей требуется находить декомпозиции множеств, содержащих сотни и даже тысячи элементов. Известны подходы к решению некоторых из рассматриваемых задач, основанные на использовании математического (часто нелинейного) программирования с булевыми переменными [5,6]. В этом случае любое разбиение представляется набором булевых переменных х,у, принимающих значение 1 если элемент ieX помешается в блок с номером je {1,..., />}, и значение 0 в противном случае, и строится путём последовательного определения компонент в наборе. Решение сформулированной задачи сводится к поиску таких значений переменных xljt которые представляют допустимые минимальные или кратчайшие разбиения. Однако «потолок» методов, использующих эти подходы, также не превышает нескольких десятков элементов в разбиваемом множестве. Среди комбинаторных подходов, получивших широкое развитие, известны [7,8] два альтернативных по способу построения разбиений подхода, использующих дерево поиска и некоторые приёмы сокращения числа перебираемых вариантов на нём. Подходы отличаются способом построения дерева поиска. В первом подходе на каждом шаге ветвления выбирается (формируется) очередной допустимый блок разбиения; число ярусов в дереве при этом не превышает числа блоков в искомых разбиениях, а коэффициент ветвления в каждой вершине равен числу вариантов выбора очередного допустимого блока. При втором подходе формирование блоков разбиения ведётся параллельно: на каждом шаге ветвления рассматривается очередной элемент множества X и для него подбирается подходящий блок, в который он может быть включён без нарушения условий допустимости. Количество ярусов в таком дереве равно и коэффициент ветвления в каждой вершине не превышает к, где к - наибольшее число блоков в строящихся разбиениях. Подход, развиваемый в данной работе, относится к первому способу организации дерева поиска. В его основе лежит метод сокращённого обхода дерева поиска [9]. В работе метод применяется для решения задач декомпозиции типа I и II. Для этого вводится общая математическая модель задач декомпозиции - так называемая Г-задача, формулируется параметрический метод и алгоритм сокращённого обхода дерева поиска и предлагается технология решения широкого класса задач декомпозиции. Г-задача Вводимая Г-задача ставится следующим образом. Пусть имеется тройка определённых каким-либо эффективным способом объектов Т=, где X есть конечное множество, Р - множество некоторых подмножеств в X и F - функция, сопоставляющая каждому (возможно, упорядоченному) разбиению любого подмножества Ус^на классы из Р некоторое неотрицательное число F(Ry), называемое сложностью разбиения В*. Требуется найти, если возможно, такое (упорядоченное) разбиение R множества X на классы из Р, которое доставляет минимум функции F. Под интерпретацией Г-задачи понимается всякая конкретная задача декомпозиции, которая может быть сформулирована как Г-задача для некоторой тройки Т=. Иначе говоря, некая задача А считается интерпретацией Г-задачи (сокращённо -Г-интерпретацией), если для неё возможно определить подходящую тройку объектов и указать какое-либо соответствие, относящее каждому ' решению Г-з'адачи'для этой'тро'йки'некоторые'ре-* шения задачи А и наоборот, каждому решению задачи А - некоторое решение Г-задачи. Многие классические комбинаторные задачи являются в действительности некоторыми Г-интер-претациями. Мы продемонстрируем это на примере лишь одной задачи - о покрытии булевой матрицы. Задача состоит в нахождении для заданной булевой (с элементами 0 и 1) матрицы А/такого наименьшего по мощности подмножества её строк, называемого кратчайшим покрытием матрицы, в котором для каждого столбца М имеется покрывающая его строка, т. е. строка, содержащая единицу в этом столбце. Пусть матрица М имеет п столбцов, обозначенных 1,..., п соответственно. ПоложимХ={\,...,п). Будем говорить, что булев вектор а{...а„ представляет собой множество КсЛ", если У/'еДа/=1 /еУ). Пусть множество Р содержит в себе каждое такое и только такое подмножество ¥ЬХ, для которого в матрице М существует строка, представляющая некоторое множество 2эУ. Пусть также F{RY)=lF?l. Тогда разбиению Ло=Рч,..., Xfi, являющемуся решением Г-задачи для указанной тройки Т=, соответствует кратчайшее покрытие матрицы М, состоящее из некоторых её строк Ьь..., представляемые которыми подмножества в X содержат классы Х\,...,Хк соответственно. Метод сокращённого обхода дерева поиска Сформулируем теперь метод сокращённого обхода дерева поиска. Для заданной тройки Т= рассмотрим некоторый алгоритм ф, перечисляющий в любом множестве YczX (возможно, в зависимости от некоторого условия а) некоторые подмножества, принадлежащие Р и (только в случае, когда упорядоченность искомого разбиения не существенна!) содержащие некоторый фиксированный элемент в Y. Совокупность всех подмножеств в Y, перечисляемых алгоритмом является ^^-минимальным разбиением в графе G. Параметры метода Каждое (

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Беляев Виктор АфанасьевичТомский государственный университетстарший преподаватель кафедры защиты информации и криптографии факультета прикладной математики и кибернетикиBelyaev@fpmk.tsu.ru
Всего: 1

Ссылки

Агибалов Г.П. Дискретные автоматы на полуреш&гках. Томск: Изд-во Том. ун-та, 1993.227 с.
Берж К. Теория графов и ее применения. М.: ИЛ, 1962.319 с.
Агибалов Г.П., Беляев В.А. Метод сокращенного обхода дерева поиска и его применение в синтезе интегральных схем // Управляющие системы и машины. 1977. № 6. С. 99-103.
Агибалов Г.П., Беляев В.А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Том. ун-та, 1981.125 с.
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.
A.M. Geoffrion, R.E. Marsten. Integer programming: a framework and state-of-the-art survey // Management Science. 1972. Vol. 18. № 9.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.
Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977. 288 с.
Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. 512 с.
 Некоторые алгоритмы структурной декомпозиции управляющих систем | Вестн. Том. гос. ун-та. 2000. № 271.

Некоторые алгоритмы структурной декомпозиции управляющих систем | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия