Метод нахождения всех тупиковых покрытий максимальными интервалами
Мы представляем регулярный способ перечисления всх тупиковых покрытий посредством ограниченного перебора. Рассмотрим таблицу покрытия. Пусть функция f ( ,…, ) от n переменных имеет s единиц ,…, , и m максимальных интервалов ,…, . Таблица будет содержать s столбцов, каждый столбец будет соответствовать определенной единице функции и будет содержать m строк , каждая строка соответствует определенному максимальному интервалу.
На пересечении строки и столбца, который соответствует единице функции поставим интервал , если интервал покрывает . И пусто, если интервал не покрывает единицу . Таким образом, в столбце непустые элементы в точности все максимальные интервалы, которые покрывают единицу . Например,
-передняя грань , - ребро
Определение:Выборкой называют упорядоченный набор интервалов , ,…, , Î (каждый индекс принимает значения из множества чисел , причем значения некоторых индексов могут повторяться), что есть не нулевой элемент первого столбца , и т. д., - ненулевой элемент последнего s – того столбца . Например : - выборки. Утверждение 1 :Интервалы любой выборки являются покрытием. Рассмотрим произвольную выборку , , … , . Все интервалы данного множества допустимы, и все единицы функции покрыты. Действительно, первая единица функции покрыта интервалом , вторая , и т. д., последняя единица покрыта . Утверждение 2 : Взяв в некотором порядке некоторые интервалы покрытия, можно получить выборку. Рассмотрим произвольное покрытие. Рассмотрим интервал, который покрывает первую единицу функции, обозначим его . Рассмотрим и обозначим , который покрывает вторую единицу функции и т. д. Рассмотрим интервал , который покрывает последнюю s – ую единицу функции. Такие интервалы обязательно найдутся, потому что рассматриваемое множество является покрытием. Тогда полученное множество интервалов , , … , является выборкой.
Из этих утверждений следует Утверждение 3 :Множество тупиковых покрытий содержится среди выборок.
Действительно, каждое тупиковое покрытие есть выборка, которую оно содержит. Интервалы тупикового покрытия можно упорядочить, и при этом получим выборку. Таким образом, чтобы найти множество тупиковых покрытий нужно найти множество всех выборок, исключить из них нетупиковые выборки. Множество оставшихся выборок и есть требуемое множество тупиковых покрытий. Таким образом, мы должны разработатьметод перечисления всех выборок и удаления нетупиковых выборок.
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (511)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |