Алгоритм DR-miner

Все семейство бимножеств, упорядоченное по отношению

, образует решетку с нижним элементом

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

. Обозначим через

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

, , такие что

и

, где первая компонента бимножество являющееся нижним элементом, а вторая — верхним элементом. Алгоритм DR-miner использует такие решетки в качестве поискового пространства; основными этапами такого поиска являются перечисление (enumeration), отсечение (pruning) и распространение (propagation).

Алгоритм 2.3.1. DR-miner

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

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

Процедура Enumeration. Пусть

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

или

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

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

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

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

возвращает

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

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

) удовлетворяет верхний элемент подрешетки: .

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

возвращает

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

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

) удовлетворяет нижний элемент подрешетки: .

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

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

. Однако

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

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

определяется следующим образом:

<
В алгоритме DR-Miner используется функция

, определённая так.

Процедура Propagation.

и

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

в

или вне . Для этого используются функции

и :



, определяемая как , рекурсивно применяется к подрешетке до тех пор, пока результат не перестанет изменяться. Подрешетка

называется листом, когда она содержит только одно бимножество, т.е. . DR-бимножества являются такими максимальными бимножествами. В статье [19] доказывается корректность и полнота алгоритма.

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


Содержание раздела

---

---

Главная сайта

---