ВВЕДЕНИЕ

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

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


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. Среди столбцов, покрывающих эту строку, ищется столбец с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких столбцов несколько, то выбирается любой из них (для определенности, допустим, самый левый).


Информация о работе «Алгоритмы поиска кратчайших покрытий булевых матриц»
Раздел: Информатика, программирование
Количество знаков с пробелами: 31648
Количество таблиц: 0
Количество изображений: 19

Похожие работы

Скачать
158931
0
1

... дискретного программирование для решения задач проектирование систем обработки данных. -  Сформулированы задачи диссертационного исследования. 2. БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ В данном разделе рассматриваются общая постановка блочно-симметричной задачи дискретного программирования, её особенности и свойства. Разработан общий подход решения задач ...

Скачать
29902
0
5

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

Скачать
169202
31
29

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

Скачать
84679
0
11

... (ШД), адресов (ША) и управления (ШУ). Однокристальные микропроцессоры получаются при реализации всех аппаратных средств процессора в виде одной БИС или СБИС (сверхбольшой интегральной схемы). По мере увеличения степени интеграции элементов в кристалле и числа выводов корпуса параметры однокристальных микропроцессоров улучшаются. Однако возможности однокристальных микропроцессоров ограничены ...

0 комментариев


Наверх