Алгоритмы поиска кратчайших покрытий булевых матриц

ВВЕДЕНИЕ

Микроэлектроника является одним из наиболее быстро и эффективно развивающихся направлений науки и техники. Однако вместе с развитием схемотехники увеличивается и сложность разрабатываемых схем. Существуют элементы схемы, логической моделью которых является матрица, в частности, булева. Площадь микросхемы и ее быстродействие во многом зависят от параметров матрицы. Поэтому приоритетной задачей является уменьшение размеров элемента, например, путем нахождения кратчайшего покрытия булевых матриц. Целесообразность поиска кратчайших покрытий возникает и при минимизации ДНФ булевых функций, при синтезе логических схем некоторых типов, при решении систем логических уравнений, при поиске простейших диагностических тестов, а так же во многих других задачах, эффективность методов решения которых, оказывается, существенно зависящей от совершенства используемых алгоритмов поиска кратчайших покрытий.

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

1. ПОСТАНОВКА ЗАДАЧИ

Рассмотрим задачу о переводчиках [1]. Допустим, из некоторого числа переводчиков, каждый из которых владеет несколькими определенными языками, требуется скомплектовать минимальную по числу членов группу такую, чтобы она смогла обеспечить перевод с любого из интересующих нас языков.

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

Если обозначить множество переводчиков, из которого можно производить выбор, через A={a, б, в, г, д}, а множество интересующих нас языков через B={1,2,3,4,5,6}. То можно ввести булеву матрицу C отношения переводчиков к языкам.

 1  2  3  4  5  6

.

Это означает, что переводчик а знает языки 1,3, переводчик б – языки 4,5 и т.д.

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

2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Булевой матрицей называется матрица, элементы которой – либо 0, либо 1.

 , {0, 1}.

Говорят, что i-я строка покрывает j-й столбец, если на их пересечении стоит единица, то есть =1. Причем каждая строка обязательно покрывает некоторое подмножество столбцов, а каждый столбец покрывается хотя бы одной строкой.

Подмножество строк матрицы B, в совокупности покрывающее все ее столбцы, образует строчное покрытие этой матрицы.

Подмножество столбцов матрицы B, в совокупности покрывающее все ее строки, образует столбцовое покрытие этой матрицы.

Покрытие, содержащее минимальное число строк (столбцов) матрицы B, называется кратчайшим покрытием матрицы B.

Пример1.

1 2 3 4 5 6 7 8 9 10

 .

Множество строк матрицы B {а, в, г, е, ж} – одно из строчных покрытий этой матрицы. Множество же строк {д, е, з} – одно из кратчайших строчных покрытий матрицы B.

3.  АЛГОРИТМЫ ПОИСКА КРАТЧАЙШИХ ПОКРЫТИЙ

Ниже приведены алгоритмы нахождения кратчайших покрытий методом Патрика [5] и методом Закревского [1].

3.1 Метод Патрика

Если требуется найти все кратчайшие покрытия булевой матрицы, можно найти все ее покрытия и выделить из них кратчайшие. Это реализуется на следующем примере.

Пример 2. Для матрицы

.

распишем, какие строчки покрывают определенный столбец в виде дизъюнкций.

Первый столбец могут покрыть а Ú д, второй – в Ú д, третий – а Ú г Ú д, четвертый – б Ú в, пятый – б Ú г Ú д, и шестой – г. Теперь составим конъюнкцию данных дизъюнкций и раскроем скобки:

(а Ú д)(в Ú д)(а Ú г Ú д)(б Ú в)(б Ú г Ú д)г = авг Ú бгд Ú вгд Ú абвг Ú бвгд Ú абвгд.

Отсюда видно, что кратчайшее покрытие булевой матрицы С – либо {а, в, г}, либо {б, г, д}, либо {в, г, д}.

Это нахождение покрытий перебором на ЭВМ реализуется для исходной матрицы небольшого размера (до 7 х 7), чтобы реализовать метод Патрика для немногим больших матриц, рекомендуется оптимизировать матрицу.

3.2 Метод Закревского

Аркадий Дмитриевич Закревский предложил довольно эффективный и простой способ нахождения малой величины покрытия булевой матрицы (так называемое разложение по минимальному столбцу и минимальной строке).

Замечание: все случаи просчитывались как вручную, так и на ЭВМ при помощи разработанной программы.

3.2.1 Строчное покрытие

Алгоритм нахождения строчного покрытия методом Закревского:

1. Ищется столбец с минимальным числом единиц. Если таковых несколько, то выбирается любой (для определенности, допустим, самый левый).

2. Среди строк, покрывающих этот столбец, ищется строка с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких строк несколько, то выбирается любая из них (для определенности, допустим, самая верхняя).

3. Удаляются все столбцы, которые покрывает полученная строка.

Действия продолжаем до тех пор, пока не удалится вся матрица.

Пример 3. Найдем кратчайшее строчное покрытие матрицы С:

1 2 3 4 5 6

.

1. Столбец 6 содержит минимальное число единиц – 1.

2. Строка г заносится в покрытие и удаляется из матрицы.

3. Удаляются столбцы 3, 5, 6.

Получаем матрицу

 1 2 4

 .

Далее проводим аналогичные действия с матрицей С:

1.  Столбец 1 (самый левый) содержит только 2 единицы.

2.  Строка д, покрывающая этот столбец, покрывает 2 столбца, заносится в покрытие и удаляется из матрицы.

3.  Удаляются столбцы 1, 2.

Остался только один столбец матрицы – 4. Можно выбрать как строку б, так и строку в, в обоих случаях мы имеем покрытие матрицы, состоящее из 3 строчек.

Итого получаем покрытия {б, г, д} и {в, г, д } – как показал метод Патрика – кратчайшие покрытия.

Замечание: Не всегда метод Закревского дает кратчайшее покрытие, оно может состоять и из большего числа строк, но находится быстрее.

Столбцовое покрытие

Алгоритм нахождения столбцового покрытия методом Закревского:

1. Ищется строка с минимальным числом единиц. Если таковых несколько, то выбирается любая (для определенности, допустим, самая верхняя).

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