Курсовая работа: Алгоритмы поиска кратчайших покрытий булевых матриц
1. Ищется строка с минимальным числом единиц. Если таковых несколько, то выбирается любая (для определенности, допустим, самая верхняя).
2. Среди столбцов, покрывающих эту строку, ищется столбец с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких столбцов несколько, то выбирается любой из них (для определенности, допустим, самый левый).
3. Удаляются все строки, которые покрывает полученный столбец.
Данные действия продолжаются до тех пор, пока не удалится вся матрица.
Итого получим покрытие {3,4}-столбцовое покрытие исследуемой матрицы.
4. Метод предварительного редуцирования булевой матрицы
При поиске кратчайшего покрытия целесообразно уменьшить матрицу, если такое возможно. Можно удалить как определенные строки, так и определенные столбцы. Отметим, что в практических задачах не требуется найти все кратчайшие покрытия, достаточно только одно или несколько. Это упрощает алгоритм упрощения (сокращения) матрицы.
1. Говорят, что i-я строка булевой матрицы поглощает j-ю строку этой матрицы (
), если на позициях единиц j-й строки в i-й – тоже «единицы», причем число единиц в i-й строке больше числа единиц в j-й строке (если же число единиц одинаково, то данные строки называются равными).
Аналогичное утверждение можно сформировать и для столбцов.
2. Говорят, что i-й столбец булевой матрицы поглощает j-й столбец этой матрицы (), если на позициях единиц j-го столбца в i-м – тоже единицы, причем число единиц в i-м столбце больше числа единиц в j-м столбце (если же число единиц одинаково, то данные столбцы называются равными).
Алгоритм: удаляются все строки, которые могут быть поглощены какими-либо другими строками матрицы, и столбцы, которые могут поглотить какие-либо другие столбцы этой матрицы, из равных строк и столбцов оставляют по одному, остальные тоже удаляют, затем в полученной матрице делаются аналогичные действия, и так до тех пор, пока матрицу нельзя будет дальше сократить.
Замечание: при реализации данного алгоритма на ЭВМ программа не удаляет строки (столбцы), что приводит к требующему ресурсы процессора созданию новых массивов, а «зануляет» их, затем игнорируя.
При поиске кратчайших покрытий предварительно сокращенной матрицы некоторые кратчайшие покрытия теряются, но это не имеет практической ценности, но объем вычислений сокращается.
Пример 4. Пусть дана булева матрица A (10 х 10):
1 2 3 4 5 6 7 8 9 10
.
Удаляем строки б и е (поглощаются строкой к), строки в, д, ж (поглощаются строкой и) и строку з (поглощается строкой г). Получим матрицу 
, уже меньшую по размерам:
1 2 3 4 5 6 7 8 9 10
.
Удаляем столбец 1 (поглощает любой другой столбец), столбцы 2, 8 и 10 (поглощают столбец 4), столбцы 3 и 7 (равны столбцу 9) и столбец 6 (равен столбцу 4). В итоге получаем матрицу 
(4 х 3):
4 5 9
.
Удаляем строки а, к (поглощаются строкой г). Получаем матрицу 
( 2 х 3 ):
4 5 9
.
Из последней матрицы удаляем столбец 9 (равен столбцу 5) и получаем не упрощаемую матрицу 
( 2 х 2 ):
4 5
.
Единственное покрытие последней матрицы – она сама. Итого, строки г и и составляют одно из кратчайших (даже единственное) покрытий матрицы A.