Threshold interpolations in solving nonlinear boolean equation by method of separating planes.pdf Один из приёмов решения систем нелинейных булевых уравнений fi(xb...,xra) = Yi, i = 1,... , N, (1) основан на сведении их к равносильным системам линейных неравенств: anx1 + ... + a!„x„ ^ 61, ... (2) am1x1 + ... + amnxn ^ 6m. Данный приём получил название метода разделяющих плоскостей [1, 2] ввиду того, что с геометрической точки зрения каждому линейному неравенству соответствует секущая гиперплоскость в (n - 1)-мерном пространстве. К числу параметров, характеризующих сложность этого метода, относится число неравенств m в системе (2) и их информативность, понимаемая как число отсекаемых неравенством вершин [1, 3]. Несмотря на достаточно глубокое изучение, в методе разделяющих плоскостей можно выделить широкий круг актуальных задач с точки зрения как построения результирующих систем линейных неравенств (2), так и их последующего решения. В работе рассматривается возможность использования в методе разделяющих плоскостей так называемых приближений исходных нелинейных уравнений системы (1) вида f (x1,...,x„) = Yj (3) aj1x1 + ... + ajnx„ ^ , i = 1,..., kj, (4) неравенствами таких, что система (4) не обязательно равносильна уравнению (3). При этом предлагается исключить малоинформативные неравенства в предположении, что за счёт избыточности исходной системы (1) неотсечённые системой (4) вершины будут отсечены другими неравенствами высокой информативности в результирующей системе. Так как система нелинейных уравнений вида (1) равносильна одному нелинейному уравнению при отсутствии ограничений на функции, используемые в левых частях, то в дальнейшем будем рассматривать приближения в пороговом базисе для одного нелинейного уравнения. Определение 1. Пусть k - фиксированное натуральное число. Для булева уравнения f (xb...,x„) = y (5) систему неравенств aax1 + ... + airax„ ^ 6i, i = 1,...,k, (6) назовём импликативным k-приближением в пороговом базисе, если все решения (5) являются решениями (6). Если система (6) состоит из одного неравенства (k = 1), то такое приближение назовём импликативным пороговым. Пусть Af - множество решений (5), Аф -множество решений (6), тогда Af С Аф. Определение 2. Дефицитом импликативного приближения назовём d = |Аф| - |Af |. При фиксированном числе неравенств k в (6) можно говорить об оптимальном им-пликативном k-приближении, для которого дефицит d наименьший. Отметим, что если k не меньше порогового индекса функции f (x1,..., xn), то всегда существует оптимальное приближение с нулевым дефицитом. Так как количество неравенств в системе прямо влияет на трудоёмкость решения, то особый интерес представляет оптимальное импликативное пороговое приближение и значение соответствующего дефицита. Замечание 1. Для конкретного булева уравнения оптимальное пороговое приближение определяется неоднозначно. В качестве примера рассмотрим сбалансированную булеву функцию f (x1 , x2 , x3) = = x1 x2 V x2x3 и уравнение f (xi ,x2 ,x3) = 1. (7) На рис. 1 и 2 единичные вершины функции (7) отмечены чёрными точками. Функция не является пороговой, поэтому можно ставить вопрос о поиске импликативного порогового приближения для уравнения (7). Одно из таких приближений задаётся неравенством xi + x2 + 2x3 < 2, (8) отсекающим три нулевые вершины (011), (101), (111) с дефицитом d =1 (рис.1). Однако можно указать ещё одно импликативное пороговое приближение -2xi + x2 - x3 < 1, (9) отсекающее вершины (101), (111), (100) и также имеющее дефицит d =1 (рис.2). Очевидно, что неравенства (8) и (9) задают оптимальные импликативные пороговые приближения, и они различны. Рис. 1. Приближение (8) Рис. 2. Приближение (9) Эксперименты показали возможность эффективного применения импликативных приближений для некоторых классов систем, и этот вопрос требует дальнейшего изучения в непосредственной связи с конкретным алгоритмом решения систем линейных неравенств. Определение 3. Статистическим пороговым приближением булевой функции f (xi,..., xn) назовём пороговую булеву функцию т(xi,..., xn), такую, что вероятность их совпадения равна P[f (xi ,...,xn )= T (xi ,...,xn )] = 2+ 5, 5> 0, (10) У произвольной булевой функции может быть несколько пороговых приближений с разными, вообще говоря, мерами близости. Определение 4. Статистическое пороговое приближение т(x1 ,...,xn) булевой функции f (x1,... ,xn) назовём оптимальным, если мера его близости максимальная. Как и в случае импликативного приближения, можно показать, что у конкретной булевой функции могут существовать различные оптимальные статистические пороговые приближения. Особенности и параметры практического применения статистических пороговых приближений требуют изучения в непосредственной связи с конкретным методом решения результирующих систем линейных неравенств. В алгоритмах направленного перебора с минимизацией невязки ^(x) истинному решению будет отвечать уже не значение невязки, равное 0, а некоторое ненулевое определяемое конкретным алгоритмом, видом ^(x) и значением Обнаруженная авторами практическая эффективность как импликативных, так и статистических пороговых приближений приводит к постановке целого ряда актуальных задач не только экспериментального характера, но и теоретических, связанных с выбором оптимальных параметров методов, оценкой объёма необходимого материала, определением емкостной и временной сложностей.

Скачать электронную версию публикации