Рассмотрим решение этой задачи при условии, что каждый элемент схемы li реализуется элементом того же типа в модулях набора T. В качестве дополнительного критерия при компоновке примем число межмодульных соединений. Решение задачи разобьем на два этапа:
1) Определение необходимого числа модулей с минимальной суммарной стоимостью.
2) Минимизация числа связей между модулями.
а) Допустим, что каждый из модулей T содержит элементы одного типа k, тогда минимальное число модулей для покрытия схемы, определяющее и минимальную стоимость покрытия, равно
, (1.4)
где а к – число элементов в модуле Tk; bk – число элементов типа k в схеме; { } – символ ближайшего большого целого; xk – число использованных модулей типа k. Отметим, что для модулей с однотипными элементами получаем квадратную матрицу 
, причем ak = 0 при 
, и 
.
б) Практический интерес представляют наборы модулей с разнотипными элементами.
Пусть известны:
1) Библиотека типовых элементов, содержащая m типов интегральный микросхем (ИМС). Общее число типов элементов в ИМС библиотеки l. Тогда библиотеку зададим матрицей вида 
.
2) Электрическая схема узла, состоящая из соединения элементов одинаковых типов. Зададим схему вектором 
.
АЛГОРИТМ 1
1. Составить вектор 
количественного состава схемы по типам элементов: 
.
2. Упорядочить модули (микросхемы) Tk библиотеки по возрастанию их стоимостей:
.
3. Составить матрицу описания состава библиотеки в соответствии с их стоимостью; 
.
4. Выполнить поэлементное деление вектора на строку 
матрицы A:
для 
, 
.
5. Найти 
и на данном шаге использовать 
модулей типа k.
6. Найти вектор непокрытых элементов
, где 
; 
.
7. Если элементы 
, перейти к 
, если 
, перейти к 
.
8. Определить количество использованных ячеек каждого типа
(
– определяет число итераций) и вычислить их суммарную стоимость: 
.
Конец.
ПРИМЕР 1.1
Пусть дана электрическая схема (рис.1.1), которая состоит из элементов типа t1, t2, t3, и t4 (рис.1.2). Существует библиотека ИМС 
(рис.1.3), причем их условные стоимости равны соответственно: 
; 
; 
; 
; 
условных единиц стоимости.
Требуется выполнить покрытие с минимальной стоимостью схемы на рис.1.1 набором микросхем из библиотеки рис.1.3.
Решение
Сосчитаем количество элементов каждого типа в схеме: 
, 
, 
, 
и составим вектор количественного состава: 
.
Для покрытия выберем микросхемы 
как наиболее дешевые. 
В необходимый набор не включаем, поскольку два 
из трех ее элементов реализуют функцию, которая отсутствует в схеме рис.1.1.
Упорядочим выбранные ИМС по возрастанию их стоимостей: T1, T2, T3.
Составим матрицу описания состава ИМС библиотеки с учетом их стоимостей:
.
Выполним поэлементное деление вектора 
на строку 
матрицы A. В делении участвуют только значащие числа, а в результатах делений учитываются только целые части
.
В результате для ИМС имеем 
, 
.
Берем min из значащих чисел {2, 4}: . Следовательно, для покрытия схемы назначаем 2 шт. ИМС . Формируем строку 
.
Находим вектор непокрытых элементов 
. Для этого из вектора поэлементно вычитаем удвоенную строку – 
.
Далее выполним аналогичные действия для ИМС 
, стоимость которой 
.
Рис. 1.1
Рис. 1.2
Рис. 1.3
Вектор поделим поэлементно на строку :
.
Значащими в результате деления будут 
, 
. Минимум из них 
, поэтому для покрытия схемы назначаем 1 шт. .
Определяем вектор непокрытых элементов 
:
.
Произведем покрытия оставшихся элементов ИМС 
, так как 
. Поделим вектор поэлементно на строку :
.
Поскольку 
, 
, получим 
, и для покрытия схемы назначаем 1шт. .
Вектор непокрытых элементов 
будет:
.
Поскольку 
, вновь выполним покрытие самой дешевой ИМС . Поделим на строку :
.
. Назначаем еще 1 шт. . Вектор непокрытых элементов 
:
Наличие отрицательного элемента (-2) в указывает на избыточность двух элементов 
в покрывающих ИМС. Итак, процесс покрытия закончен. В итоге получили 3 шт. , 1 шт. и 1 шт. . Коэффициент покрытия схемы G = 11/5 = 2,2.
Результаты расчетов сведены в табл.1.1. В скобках указано число элементов (по типам) в исходной схеме рис.1.1.
Таблица 1.1
| Тип микросхемы | Число микросхем | Число элементов | Всего | |||
|
| 
| 
| 
| |||
|
| ||||||
|
| ||||||
|
| ||||||
| Всего | 7(5) | 4(4) | 1(1) | 1(1) | 13(11) |
