Метод нахождения всех тупиковых покрытий максимальными интервалами

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

Рассмотрим таблицу покрытия. Пусть функция f (,…, ) от n переменных имеет s единиц ,…, , и m максимальных интервалов ,…, . Таблица будет содержать s столбцов, каждый столбец будет соответствовать определенной единице функции и будет содержать m строк, каждая строка соответствует определенному максимальному интервалу.

	,…	,…

На пересечении строки и столбца, который соответствует единице функции поставим интервал , если интервал покрывает . И пусто, если интервал не покрывает единицу . Таким образом, в столбце непустые элементы в точности все максимальные интервалы, которые покрывают единицу .

Например,

K₂

-передняя грань , - ребро

Определение: Выборкой называют упорядоченный набор интервалов

, ,…, , Î (каждый индекс принимает значения из множества чисел , причем значения некоторых индексов могут повторяться), что есть не нулевой элемент первого столбца, и т. д., - ненулевой элемент последнего s – того столбца.

Например:

- выборки.

Утверждение 1: Интервалы любой выборки являются покрытием.

Рассмотрим произвольную выборку , , …, . Все интервалы данного множества допустимы, и все единицы функции покрыты.

Действительно, первая единица функции покрыта интервалом , вторая , и т. д., последняя единица покрыта .

Утверждение 2: Взяв в некотором порядке некоторые интервалы покрытия, можно получить выборку.

Рассмотрим произвольное покрытие. Рассмотрим интервал, который покрывает первую единицу функции, обозначим его .

Рассмотрим и обозначим , который покрывает вторую единицу функции и т. д. Рассмотрим интервал , который покрывает последнюю s – ую единицу функции.

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

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

Из этих утверждений следует

Утверждение 3: Множество тупиковых покрытий содержится среди выборок.

Действительно, каждое тупиковое покрытие есть выборка, которую оно содержит. Интервалы тупикового покрытия можно упорядочить, и при этом получим выборку.

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

Множество оставшихся выборок и есть требуемое множество тупиковых покрытий.

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

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