OK_metodichka_part_1 (1132796), страница 7
Текст из файла (страница 7)
Рассмотрим сначала метод выделения из заданного покрытия конечного множества всех еготупиковых подпокрытий, основанный на построении сокращенной ДНФ для специальной монотонной ФАЛ, связаннойс исходным покрытием.Пусть N = {α1 , . . . , αs } — конечное множество, а N == (N1 , . .
. , Np ) — система его подмножеств, образующих покрытие множества N. Сопоставим паре (N, N) матрицу M, M ∈§5. Построение всех тупиковых ДНФ43B p,s , для которой M hi, ji = 1 тогда и только тогда, когдаNi 3 αj . Заметим, что матрица M не имеет нулевых столбцов, так как система N образует покрытие множества N.Будем считать, что i-я строка (j-й столбец) матрицы M соответствует подмножеству Ni системы N (элементу αj множества N) и не будем делать между ними существенныхразличий.
Так, будем говорить, что i-я строка матрицы Mпокрывает ее j-й столбец, если M hi, ji = 1, то есть Ni 3 αj ,и что система строк с номерами из I, I ⊆ [1, p], образуетпокрытие матрицы M , если каждый ее столбец покрывается хотя бы одной строкой с номером из I, то есть системаподмножеств {Ni }i∈I задает покрытие множества N. Аналогичным образом понимается покрытие одного множествастрок матрицы M другим множеством ее строк и т. п.Покрытие матрицы M , в котором ни одна строка не покрывается другой строкой, считается неприводимым, а покрытие, не имеющее собственных подпокрытий, называется тупиковым и т. п. Заметим, что задача выделения всехтупиковых подпокрытий из покрытия N множества N эквивалентна задаче построения всех тупиковых покрытий матрицы M , соответствующей паре (N, N). Для решения этойзадачи по аналогии с ДНФ можно ввести понятие ядрового и регулярного столбцов, а также ядровой и регулярнойстроки, для которых будут справедливы утверждения, аналогичные лемме 2.1 и теореме 4.1.Пусть M, M ∈ B p,s — матрица без нулевых столбцов.Сопоставим i-й строке, i ∈ [1, p], матрицы M БП yi , а каждому набору β, β ∈ B p , значений этих переменных y =(y1 , .
. . , yp ), — множество строк матрицы M с номерами измножества I = I (β) ⊆ [1, p], где i ∈ I (β) тогда и толькотогда, когда β hii = 1. Рассмотрим ФАЛ F (y), для которойF (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует ее покрытие, и будемназывать эту ФАЛ функцией покрытия матрицы M . Заме-44Глава 1. Дизъюнктивные нормальные формытим, что ФАЛ покрытия F (y) является монотонной ФАЛ, аее «нижние единицы» соответствуют тупиковым покрытиямматрицы M . Действительно, из неравенства β 0 6 β 00 вытекает, что I (β 0 ) ⊆ I (β 00 ) и потому F (β 0 ) 6 F (β 00 ), то есть ФАЛF является монотонной.
Из определений следует также, чтонабор β, β ∈ B p , являющийся «нижней единицей» ФАЛ F ,соответствует множеству I (β), которое задает тупиковое покрытие матрицы M , и обратно. Таким образом, в силу леммы 5.1, каждая простая импликанта вида K = yi1 yi2 · · · yir ,где 1 6 i1 < · · · < ir 6 p, ФАЛ покрытия F (y) соответствует тупиковому покрытию матрицы M , состоящему из строкс номерами из множества I = {i1 , .
. . , ir }, и обратно.Лемма 5.2. Функция покрытия F (y1 , . . . , yp ) матрицы M, M ∈B p,s , без нулевых столбцов задается КНФ вида:F (y1 , . . . , yp ) =s ^j=1_yi .(5.1)16i6pM hi,ji=1Доказательство. Для каждого j, j ∈ [1, s], положимJj (y) =_yi ,16i6pM hi,ji=1где y = (y1 , . . . , yp ). Легко видеть, что Jj (β) = 1 для произвольного набора β, β ∈ B p , тогда и только тогда, когдамножество строк с номерами из I (β) покрывает j-й столбецматрицы M, j ∈ [1, s]. Отсюда следует, что КНФ в правой части (5.1) обращается в 1 на наборе β тогда и толькотогда, когда множество строк с номерами из I(β) образуетпокрытие матрицы M , то есть тогда и только тогда, когдаF (β) = 1.Лемма доказана.§5.
Построение всех тупиковых ДНФ45Следствие. В результате раскрытия скобок и приведения подобных из КНФ (5.1) можно получить сокращеннуюДНФ ФАЛ F (y), простые импликанты которой взаимнооднозначно соответствуют тупиковым покрытиям матрицы M .Задача построения всех тупиковых ДНФ ФАЛ f из P2 (n)на основе ее сокращенной ДНФ сводится к рассмотреннойвыше задаче о покрытии, если в качестве множества N взятьмножество Nf , а в качестве его покрытия N — систему всехмаксимальных граней ФАЛ f .
Матрица M , соответствующая указанной паре (N, N), называется, обычно, таблицейКвайна ФАЛ f . Заметим, что ядровой столбец (строка) таблицы Квайна связан с ядровой точкой (соответственно гранью) ФАЛ f , что регулярный столбец (строка) этой таблицы задает регулярную точку (соответственно грань) ФАЛ f ,что строка, покрываемая ядровыми строками, соответствует грани, покрываемой ядром и т. п.Рассмотрим, для примера, задачу построения всех тупиковых ДНФ для ФАЛ g (x1 , x2 , x3 ) из ее сокращенной ДНФ,полагая (см. рис. 2.1a, (2.10), (4.1) и (4.2)), чтоNg = {α1 = (100) , α2 = (110) , α3 = (010) ,α4 = (011) , α5 = (001) , α6 = (101)},N = {N1 , .
. . , N6 } ,где Ni = NKi = {αi , αi+1 } для всех i, i ∈ [1, 6], причемα7 = α1 = (100). Паре (Ng , N) указанным выше способомсопоставим таблицу Квайна1 1 0 0 0 00 1 1 0 0 00 0 1 1 0 0M =0 0 0 1 1 0 ,0 0 0 0 1 11 0 0 0 0 146Глава 1. Дизъюнктивные нормальные формыФАЛ покрытия которой в соответствии с (5.1) задается следующей КНФ от переменных y = (y1 , . . .
, y6 ):F (y) = (y6 ∨ y1 ) (y1 ∨ y2 ) (y2 ∨ y3 ) (y3 ∨ y4 ) (y4 ∨ y5 ) (y5 ∨ y6 ) .Раскрывая в этой КНФ скобки и приводя подобные, получим сокращенную ДНФ ФАЛ F (y) видаF (y) = y1 y3 y5 ∨ y2 y4 y6 ∨ y1 y2 y4 y5 ∨ y2 y3 y5 y6 ∨ y1 y3 y4 y6 ,слагаемые которой взаимно однозначно соответствуют тупиковым ДНФ ФАЛ g (см. (4.1), (4.2)).В общем случае при построении всех тупиковых ДНФФАЛ f , f ∈ P2 (n), с помощью леммы5.2 на основе ее сокращенной ДНФ используют, обычно, следующую модификацию рассмотренного выше подхода, которая позволяет уменьшать размеры матрицы M .
Пусть NK1 , . . . , NKq — все максимальные грани ФАЛ f , причем грани NKp+1 , . . . , NKt , где1 6 p 6 t 6 q, являются ядровыми, а грани NKt+1 , . . .. . . , NKq — регулярными гранями ФАЛ f , и пусть множеb состоит из всех ядровых и регулярных точек ФАЛство Nf . ПоложимbN = Nf \ N,N = {N1 , . . . , Np } ,b при всех i, i ∈ [1, p], и заметим, что задагде Ni = NKi \ Nча построения всех тупиковых ДНФ ФАЛ f эквивалентназадаче выделения всех тупиковых подпокрытий из покрытия N множества N. Действительно, если система подмножеств Ni1 , . .
. , Nir , где 1 6 i1 < · · · < ir 6 p, является тупиковым покрытием множества N, то система максимальных граней NKi1 , . . . , NKir , NKp+1 , . . . , NKt задает тупиковоепокрытие множества Nf , то есть соответствует тупиковойДНФ ФАЛ f , и обратно.§6. Градиентный алгоритм47Так, применяя указанную модификацию к ФАЛ g 0 изP2 (4), показанной на рис.
3.1 (см. также (3.1) и (4.3)), получим тривиальную задачу о покрытии множества N == {(1000)} двумя совпадающими с ним подмножествами N1и N2 .§6Градиентный алгоритм и оценка длины градиентного покрытияВыделение всех тупиковых подпокрытий из заданного покрытия и, в частности, построение всех тупиковых ДНФявляется трудоемкой задачей. В связи с этим, вместо того, чтобы строить все тупиковые ДНФ и выбирать срединих, например, кратчайшую, часто используют эвристические алгоритмы, позволяющие получать не очень «длинные» ДНФ. К числу таких алгоритмов относится и градиентный алгоритм, ориентированный на выделение из заданного покрытия достаточно «коротких» подпокрытий, или,иначе, на построение достаточно «коротких» покрытий длязаданной матрицы.
На каждом шаге градиентного алгоритма в матрице выбирается и включается в покрытие такаястрока, которая покрывает наибольшее число еще не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером). Алгоритм заканчиваетсвою работу после того шага, на котором получилось покрытие.Следующее утверждение дает верхнюю оценку длиныпокрытия, получаемого с помощью градиентного алгоритма для матриц с заданной «густотой».Теорема 6.1 ([6]). Пусть для действительного γ, 0<γ 61,в каждом столбце матрицы M, M ∈ B p,s , имеется неменьше, чем γ · p, единиц. Тогда покрытие матрицы M , получаемое с помощью градиентного алгоритма, имеет дли-48Глава 1.
Дизъюнктивные нормальные формыlmну не больше, чем1 γ1 ln+ (γs) + γ1 .Доказательство. Пусть для построения покрытия матрицы M с помощью градиентного алгоритма потребовалосьсделать q шагов, причем на шаге с номером t, t ∈ [1, q], была выбрана строка с номером it . Для каждого t, t ∈ [1, q),рассмотрим матрицу Mt , которая получается из матрицы Mв результате удаления строк с номерами {i1 , . . . , it }, а такжепокрываемых ими столбцов, и которая принадлежит множеству B pt ,st , где pt = p − t и st = s · δt , 0 6 δt 6 1. Для определенности будем считать, что M0 = M, p0 = p, s0 = s, δ0 = 1и pq = p−q, sq = δq = 0.
Заметим, что при любом t, t ∈ [0, q],справедливо неравенствоq 6 t + δt · s,(6.1)так как после выполнения первых t шагов алгоритма остаются не покрытыми δt · s столбцов матрицы M , а на каждомследующем шаге покрывается не менее одного столбца.Заметим, далее, что в каждом столбце матрицы Mt , t ∈ [0, q),имеется не менее, чем γ · p, единиц и поэтому общее числоединиц в матрице Mt не меньше, чем γpsδt , а значит среднее число единиц в ее строках не меньше, чем γsδt . Отсюдавытекает, что строка матрицы M с номером it+1 , котораявыбирается на (t + 1)-м шаге алгоритма и является строкой матрицы Mt с наибольшим числом единиц, содержит неменьше, чем γsδt , единиц, то есть покрывает не меньше, чемγsδt , еще не покрытых столбцов матрицы M .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
