Алгоритм DR-miner
Все семейство бимножеств, упорядоченное по отношению


и верхним элементом


множество подрешеток из



и

Алгоритм 2.3.1. DR-miner
Алгоритм DR-miner начинает работу с полной решетки

и затем рекурсивно распространяет ограничения, используя функцию Prop. Далее проверяется соответсвие полученной подрешетки введенным ограничениям посредством функции Prune, и порождаются две новых подрешетки, благодаря функции Enum (см. Алгоритм 2.3.1).
Процедура Enumeration. Пусть

таким образом, где

или


возвращает один элемент





Процедура Pruning. Подрешетка более не рассматривается, если среди ее бимножеств нет удовлетворяющих ограничениям. Пусть функция

возвращает

тогда и только тогда, когда монотонному ограничению

(по отношению


Пусть функция

возвращает

тогда и только тогда, когда aнтимонотонному ограничению

(по отношению


Антимонотонное ограничение

используется в качестве


не является ни монотонным, ни антимонотонным ограничением.

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

определяется следующим образом:
![]() |
В алгоритме DR-Miner используется функция

, определённая так.
Процедура Propagation.

и

могут быть использованы для уменьшения размера подрешетки посредством перемещения объектов из

в

или вне


и

![]() |

, определяемая как


называется листом, когда она содержит только одно бимножество, т.е.

Назад Содержание Вперёд