ЛЕКЦИЯ 16. МЕТОД ГРУППОВЫХ РЕЗОЛЮЦИЙ


Метод групповых резолюций [1] позволяет найти решение задачи о минимальном покрытии 0,1-матрицы B множеством строк. Пусть дана система дизъюнктов

 

D1= x1 v Øx2,

D2= x2 v x3,

D3= Øx1 v x2 v x3,

D4= Øx2 v Øx3.

 

 

Для нее строим 0,1-матрицу B следующим образом. Строки матрицы соответствуют литерам xi и их отрицаниям Øxi . Таким образом, число строк составит 2×n, где n – число различных булевских переменных. Столбцы матрицы соответствуют дизъюнктам системы Dj , причем столбец содержит единицу в строке xk xk) ,если переменная xk входит в Dj без отрицания (с отрицанием). Кроме того, матрица дополнительно содержит n столбцов, соответствующих тавтологическим дизъюнктам xk v Øxk. С учетом сказанного, матрица B для рассматриваемого примера имеет вид, изображенный на рис. 16.1.

 

  D1 D2 D3 D4 D5 D6 D7
x1          
x2        
x3        
Øx1          
Øx2        
Øx3          

 

Рис. 16.1

Определение. Под минимальным покрытием матрицы B понимается минимальное по числу строк множество pmin, такое, что для каждого столбца матрицы B найдется как минимум одна строка в pmin , которая содержит в данном столбце “1” (иными словами, покрывает данный столбец).

Утверждение. Пусть дана матрица B, построенная для системы дизъюнктов с n>1 переменными. Если минимальное покрытие pmin матрицы B содержит более n строк, то данная система дизъюнктов не выполнима; в противном случае – выполнима.

 

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

В качестве эвристического алгоритма можно использовать следующий. На каждой итерации p отыскиваем столбец (из числа не вычеркнутых) с минимальным числом единиц. Обозначим этот столбец rp и назовем его синдромным. Найдем невычеркнутую строку ip, покрывающую rp и такую, что из всех других строк, покрывающих rp, она содержит наибольшее число единиц. Включим ip в отыскиваемое на данной итерации p покрытие. Вычеркнем все строки, содержащие в столбце rp “1”, а также все столбцы, покрываемые строкой ip. Итерация ведется до тех пор, пока имеется хотя бы один невычеркнутый столбец и одна не вычеркнутая строка.

Так, выберем столбец D1 и строку Øx2 , которую включим в отыскиваемое покрытие на итерации 1. Вычеркнем строки и столбцы согласно описанному правилу – рис. 16.2.

 

  D2 D3 D5 D7
x1      
x2    
x3  
Øx1    
Øx3      

 

Рис. 16.2

Выполним теперь вторую итерацию. Выберем столбец D2 и строку x3. Вычеркнем строки и столбцы согласно описанному правилу – рис. 16.3. Остается единственный не вычеркнутый столбец, так что включим, например, строку x1 в предполагаемое минимальное покрытие. Таким образом, итерация завершается отысканием покрытия p1 = {Øx2, x3, x1}. Согласно представленному выше Утверждению, данное покрытие минимально и дает выполняющую интерпретацию для исходной системы дизъюнктов.

 

 

  D5
x1
x2  
x3  
Øx1
Øx3  

 

Рис. 16.3

Описанный эвристический алгоритм не всегда отыскивает минимальное покрытие и необходимо выполнять этап построения групповой резольвенты. Это делается так. Берем текущее найденное покрытие и оставляем в нем любые n+1 строку. Формируем матрицу R из синдромных столбцов, найденных для этих строк. Формируем столбец-резольвенту, исходя из следующего: он содержит “1” в тех и только тех строках, которые в R имеют две или более единиц; в противном случае строка содержит “0”. Этот столбец присоединяется к матрице B и итерации возобновляются снова (все вычеркнутые строки и столбцы восстанавливаем на новой итерации). Так, найденное покрытие p1 = {Øx2, x3, x1} содержит ровно n = 3 строки. Тем не менее, построим для него матрицу R (рис. 16.4) на синдромных столбцах D1, D2, D5.

 

  D1 D2 D5 Резольвента
x1  
x2      
x3      
Øx1      
Øx2      
Øx3        

Рис. 16.4

 

В данном случае групповая резольвента содержит единственную “1” в строке x1. Поэтому при возобновлении итераций (если бы это было необходимо), следовало добавить данную резольвенту к матрице B.

Недостатком описанного метода является рост размеров матрицы при присоединении новых резольвент.

 

 

ЛИТЕРАТУРА

1. Герман, О. В. Введение в теорию экспертных систем и обработку знаний / О. В. Герман. – Минск. : Дизайн-Про, 1995. – 256 с.

 

 



Дата добавления: 2022-02-05; просмотров: 276;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.013 сек.