Метод нахождения всех выборок

Пусть ,…, ненулевые элементы первого столбца в таблице покрытия.

,…, ненулевые элементы второго столбца в таблице покрытия.

…

,…, ненулевые элементы последнего s – того столбца в таблице покрытия.

Рассмотрим функцию покрытия . Это есть КНФ от переменных, которые соответствуют максимальным интервалам таблицы покрытия.

Это КНФ есть произведение по всем столбцам покрытия, где каждому столбцу соответствует множитель равный дизъюнкции ненулевых элементов

( Ú…Ú )( Ú…Ú )…( Ú…Ú ).

Пример: максимальные интервалы- есть следующие ребра

₂

()( Ú )( Ú )( Ú )() - КНФ

Раскроем скобки в полученной КНФ, т.е. перейдем от КНФ к ДНФ.

Утверждение: Множество слагаемых полученной ДНФ и есть множество всевозможных выборок.

Действительно, каждое слагаемое при раскрытии скобок получается при выборе в первом множителе КНФ одного из интервалов , которые по построению покрывают первую вершину. Во втором множителе КНФ при выборе некоторого интервала , который по построению покрывает вторую вершину и т. д. В последнем множителе при выборе интервала , который по построению покрывает последнюю s – тую вершину.

Полученное множество интервалов есть выборка.

Множество всевозможных таких слагаемых и есть множество всех выборок.

После нахождения всех выборок удаляем нетупиковые выборки. Выборка будет нетупиковой, если из нее можно удалить некоторые интервалы так, что все равно получится выборка.

Т. е. по-другому говоря, слагаемое, которое соответствует нетупиковой выборке поглощается слагаемым, которое соответствует тупиковой выборке.

Например:

Множество интервалов является выборкой.

- является выборкой.

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

Т. е. интервал поглощает .

Таким образом, чтобы получить все тупиковые выборки нужно в построенной ДНФ применить все возможные поглощения.

Множество оставшихся слагаемых и будут всевозможные тупиковые покрытия.

Дата добавления: 2017-01-13