Применение пороговых приближений для решения систем нелинейных уравнений в методе разделяющих плоскостей

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

Таким образом, сделаем вывод о возможности применения метода эллипсоидов для распознавания пороговых булевых функций. Детальное изучение процесса его работы и сравнительный анализ с итеративными алгоритмами, в том числе в к-значной области, представляет актуальное направление для дальнейших исследований.

ЛИТЕРАТУРА

1. Хачиян Л. Г. Полиномиальные алгоритмы в линейном программировании // ЖВМиМФ. 1980. Вып. 20. №1. С. 51-68.

2. Зуев А. Ю. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. 1994. №5. С. 5-61.

3. Никонов В. Г. Пороговые представления булевых функций // Обозрение прикл. и про-мышл. математики. 1994. Вып. 1. №3. С. 458-545.

4. Кудрявцев Л. Г. Теория тестового распознавания // Дискретная математика. 2006. Вып. 18. №3. С. 3-34.

5. Бурделев А. В., Никонов В. Г., Лапиков И. И. Распознавание параметров узла защиты информации, реализованного пороговой к-значной функцией // Труды СПИИРАН. 2016. Вып. 46. С. 108-127 .

6. Дертоузос П. Пороговая логика. М.: Мир, 1967. 344 с.

7. Лапиков И. И., Никонов В. Г. Адаптивный алгоритм решения систем неравенств с к-знач-ными неизвестными // Труды Военно-космической академии им. А. Ф. Можайского. 2016. Вып. 1. С. 88-94.

УДК 512.55 Б01 10.17223/2226308Х/10/64

ПРИМЕНЕНИЕ ПОРОГОВЫХ ПРИБЛИЖЕНИЙ ДЛЯ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ В МЕТОДЕ РАЗДЕЛЯЮЩИХ ПЛОСКОСТЕЙ

В. Г. Никонов, А. Н. Шурупов

В методе разделяющих плоскостей предлагается перейти от системы линейных неравенств, эквивалентной нелинейному булеву уравнению, к системе линейных неравенств, являющейся следствием исходного уравнения. Вводится понятие им-пликативного к-приближения в пороговом базисе, которое характеризуется, с одной стороны, числом к линейных неравенств, а с другой стороны, дефицитом — мерой близости импликативного приближения к исходной системе неравенств. Предельный случай — 1-приближение, как и остальные, не является однозначным. Отказ от свойства импликативности позволяет ввести понятие статистического порогового приближения для булевой функции. Введённые понятия могут быть использованы для сокращения числа линейных неравенств в системе, порождённой исходным нелинейным уравнением, с сохранением возможности её решения.

Ключевые слова: метод разделяющих плоскостей, нелинейные булевы уравнения, пороговые функции, пороговые приближения.

Один из приёмов решения систем нелинейных булевых уравнений

/¿

основан на сведении их к равносильным системам линейных неравенств:

апх 1 + ... + а\пхп ^ Ъь ...

ат1х1 + ... + атпхп ^ Ът.

Данный приём получил название метода разделяющих плоскостей [1, 2] ввиду того, что с геометрической точки зрения каждому линейному неравенству соответствует секущая гиперплоскость в (п — 1)-мерном пространстве. К числу параметров, характеризующих сложность этого метода, относится число неравенств т в системе (2) и их информативность, понимаемая как число отсекаемых неравенством вершин [1, 3].

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

В работе рассматривается возможность использования в методе разделяющих плоскостей так называемых приближений исходных нелинейных уравнений системы (1) вида

Л

а^хх + ... + а^пхп ^ , г = 1,..., к,-,

неравенствами

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

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

Определение 1. Пусть к — фиксированное натуральное число. Для булева уравнения

Л

систему неравенств

ацхх + ... + агпхп ^ Ъг, г = 1 ,...,к,

назовём импликативным к-приближением в пороговом базисе, если все решения (5) являются решениями (6). Если система (6) состоит из одного неравенства (к = 1), то такое приближение назовём импликативным пороговым.

Пусть А$ — множество решений (5), Аф —множество решений (6), тогда А$ С Аф. Определение 2. Дефицитом импликативного приближения назовём

При фиксированном числе неравенств k в (6) можно говорить об оптимальном им-пликативном k-приближении, для которого дефицит d наименьший. Отметим, что если k не меньше порогового индекса tY функции f (xi,..., xn), то всегда существует оптимальное приближение с нулевым дефицитом. Так как количество неравенств в системе прямо влияет на трудоёмкость решения, то особый интерес представляет оптимальное импликативное пороговое приближение и значение соответствующего дефицита.

Замечание 1. Для конкретного булева уравнения оптимальное пороговое приближение определяется неоднозначно.

В качестве примера рассмотрим сбалансированную булеву функцию f (xi , x2, x3) = = xix2 V x2x3 и уравнение

f

На рис. 1 и 2 единичные вершины функции (7) отмечены чёрными точками. Функция не является пороговой, поэтому можно ставить вопрос о поиске импликативного порогового приближения для уравнения (7).

Одно из таких приближений задаётся неравенством

xi + x2 + 2x3 < 2,

отсекающим три нулевые вершины (011), (101), (111) с дефицитом d =1 (рис.1). Однако можно указать ещё одно импликативное пороговое приближение

-2xi + x2 - x3 < 1,

отсекающее вершины (101), (111), (100) и также имеющее дефицит d =1 (рис.2). Очевидно, что неравенства (8) и (9) задают оптимальные импликативные пороговые приближения, и они различны.

Рис. 1. Приближение

Эксперименты показали возможность эффективного применения импликативных приближений для некоторых классов систем, и этот вопрос требует дальнейшего изучения в непосредственной связи с конкретным алгоритмом решения систем линейных неравенств.

Определение 3. Статистическим пороговым приближением булевой функции f (х,..., хп) назовём пороговую булеву функцию т(х,..., хп), такую, что вероятность их совпадения равна

Р^

где 6 — мера близости приближения.

У произвольной булевой функции может быть несколько пороговых приближений с разными, вообще говоря, мерами близости.

Определение 4. Статистическое пороговое приближение т(хх,...,хп) булевой функции /(хх,... ,хп) назовём оптимальным, если мера его близости максимальная.

Как и в случае импликативного приближения, можно показать, что у конкретной булевой функции могут существовать различные оптимальные статистические пороговые приближения.

Особенности и параметры практического применения статистических пороговых приближений требуют изучения в непосредственной связи с конкретным методом решения результирующих систем линейных неравенств. В алгоритмах направленного перебора с минимизацией невязки ^(х) истинному решению будет отвечать уже не значение невязки, равное 0, а некоторое ненулевое определяемое конкретным алгоритмом, видом ^(х) и значением 8.

Обнаруженная авторами практическая эффективность как импликативных, так и статистических пороговых приближений приводит к постановке целого ряда актуальных задач не только экспериментального характера, но и теоретических, связанных с выбором оптимальных параметров методов, оценкой объёма необходимого материала, определением емкостной и временной сложностей.

ЛИТЕРАТУРА

1. Балакин Г. В., Никонов В. Г. Методы сведения булевых уравнений к системам пороговых соотношений // Обозрение прикладной и промышленной математики. 1994. Т. 1. №3. С.389-401.

2. Рыбников К. К. Оценки сложности некоторых схем метода разделяющих плоскостей при решении систем булевых уравнений // Обозрение прикладной и промышленной математики. 2002. Т. 2. №9. С. 442-443.

3. Анашкина Н. В., Шурупов А. Н. Применение алгоритмов локального поиска к решению систем псевдобулевых линейных неравенств // Прикладная дискретная математика. Приложение. 2015. №8. С. 136-138.

УДК 519.7 DOI 10.17223/2226308X/10/65

ДВУХФАЗНЫЙ АЛГОРИТМ МАРШРУТИЗАЦИИ В НЕСТАЦИОНАРНЫХ СЕТЯХ

А. А. Солдатенко

Рассмотрена задача Time-Dependent Shortest-Path (TDSP), которая является расширением известной задачи о кратчайшем пути в ориентированном графе, когда вес каждой дуги (x,y) этого графа — функция от времени отправления из вершины x. Предложено задачу TDSP решать с помощью двухфазного алгоритма ALT, который осуществляет целенаправленный поиск по ориентирам от стартовой вершины s до целевой вершины d. На первой фазе выполняется расстановка ориентиров в узлах сети и вычисляются потенциальные функции, на второй фазе находится точное значение (s, d)-пути с учётом вычисленных потенциальных функций. Предложены формулы вычисления потенциальных функций и способ задания неравенства треугольника, обеспечивающие корректность алгоритма ALT, и полиномиальная по времени адаптивная эвристика для расстановки ориентиров, которая использует историю обработки запросов при многократном решении задачи TDSP.