<<
>>

Термины и определения

1. Задачи о покрытии классифицируются следующим обра­зом: задача о покрытии путями, задача о вершинном покрытии, задача о покрытии множествами.

Пусть дан граф G = (X, U), где X = {xi| i = 1,2,..., n}— множество вершин, a U = {uj| j = 1,2,..., m}— множество ре­бер. Покрытием путями ориентированного графа Gнaзывaется множество путей Pс таким свойством: каждая вершина xi∈X принадлежит ровно одному пути из P. Пути могут начинаться и заканчиваться где угодно и иметь любую длину, в том числе и нулевую.

Покрытие наименьшим возможным числом путей называется минимальным покрытием путями[4.1].

Множество вершин Xv⊆X графа G = (X, U) называется вершинным покрытием графа, если у любого ребра графа хотя бы один из концов входит в Xv. Если считать, что вершина «покрывает» инцидентные ей ребра, то вершинное покрытие гра­фа G — это множество вершин, которые покрывают все его ребра [4.1]. Размером вершинного покрытия называется число входящих в него вершин. Задача о вершинном покрытии требует указать минимально возможный размер вершинного покрытия для заданного графа.

Исходными данными задачи о покрытии множествами явля­ются конечное множество X, а также семейство его подмножеств F = {Xi| i = 1,2,..., n}таких, что Xi⊆X и ∣JXi= X. Задача о минимальном покрытии множествами закЛючается в отыс­

кании набора P ⊆Fс минимальным числом подмножеств Xi∈P и Xi∈F такого, чтобы U Xi= X.

Xi∈P

Непосредственное обобщение этой задачи состоит в припи­сывании подмножествам Xiопределенных весов и требования многократного покрытия элементов множества X. В таком слу­чае задача заключается в нахождении покрывающего набора минимальной стоимости [4.2, 4.3, 4.4].

Задача покрытия является NP-полной. В течение последних лет были предложены различные подходы к решению проблемы планирования. В основном это алгоритмы, основанные на эври­стиках, обеспечивающих получение приемлемого результата за полиномиальное время [4.5, 4.6, 4.7]. Тем не менее, возросшие сложность решаемых задач и требования к качеству решения делают актуальной разработку новых более эффективных ме­тодов. Перспективным направлением в этой области является использование методов поисковой адаптации.

2. Одной из первых задач, решаемых на этапе конструктор­ского проектирования СБИС, является преобразование функци­ональной схемы в электрическую. Это есть покрытие функцио­нальной схемы ячейками из заданного набора.

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

Известные в литературе алгоритмы покрытия функциональ­ной схемы ячейками из заданного набора оптимизируют следую­щие показатели [4.8, 4.9]:

— суммарную стоимость ячеек, покрывающих схему;

— общее число ячеек, необходимое для реализации схемы;

— число типов используемых ячеек;

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

Пусть задана функциональная схема S = {si| i = 1,2,..., w}, состоящая из элементов si,и множество E = {ei| i = 1,2,...,n} типов элементов, входящих в состав покрываемой функциональ­ной схемы. Количественный состав схемы по типам элементов опишем вектором B = {bi| i = 1,2,..., n}, где bi— число элемен­тов типа ei, входящих в состав схемы.

Кроме того, задан набор покрывающих ячеек T = {tj| j = = 1,2,..., m}. Каждая ячейка имеет свой набор элементов из E. Элементы внутри ячейки между собой не соединены. Количественный состав ячеек опишем с помощью матрицы - число элементов типа eiв ячейке типа ti. C помощью вектора C = {cj∙ | j = 1,2,..., m} зададим для каждой ячейки tj ЄЄ стоимость Cj.

Схема считается покрытой ячейками из набора T, если каж­дый элемент функциональной схемы реализуется элементами, входящими в состав выбранных ячеек.

Построим математическую модель. Введем целочисленную переменную Xj, определяющую число ячеек типа tj, входящих в покрывающий набор. Тогда задача покрытия формулируется следующим образом:

Решением задачи является набор значений параметров xj∙, j = 1,2,..., m, при которых функция F(суммарная стоимость ячеек покрывающего набора) имеет минимальное значение.

Если в качестве показателя cj∙ принять общее число элемен­тов, входящих в состав ячейки tj∙ , т. єто функция

F определяет общее число элементов, входящих в состав покры­вающего набора ячеек.

4.2.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Термины и определения:

  1. Определение твердости по Бринеллю
  2. Определение твёрдости
  3. Определение прочности на растяжение
  4. 3.4.3 Определение удельного сопротивления монокристаллов германия.
  5. Определение предела прочности при поперечном изгибе
  6. Определение секущих модулей и коэффициентов поперечных деформаций при отсутствии трещин
  7. 1. Понятие и правовое положение органа исполнительной власти
  8. 1.1. Классификация оптических аномалий в кристаллах.
  9. § 1. Понятие и правовая природа банка
  10. 1. Производство по делам об административных правонарушениях: общая характеристика
  11. 1. Понятие государственного управления
  12. 3. Классификация органов исполнительной власти. Факторы, влияющие на построение системы органов
  13. 3. Основы административно-правового статуса граждан
  14. Заключение
  15. §1.1 Профессиографический подход к анализу деятельности менеджера коммерческой организации
  16. § 1. Генезис принципа зависимости в теории и международной практике
  17. 3. Судебный порядок рассмотрения обращений граждан
  18. 44. Договор возмездного оказания услуг.
  19. 1. Понятие и принципы государственной службы
  20. Методика использования МИКФ