About the potential for the ellipsoid method application to the threshold function recognition.pdf Предложенный в 1979 году Л. Г. Хачияном алгоритм решения систем линейных неравенств с целочисленными коэффициентами и действительными неизвестными ааЖ1 + ... + ai„x„ ^ bi, i = 1,..., m, (1) позволил классифицировать сложность данной задачи как полиномиальную [1]. Сложность алгоритма характеризуется значением максимального количества итераций w = 6n2L, где L Е bg2(k,j1 + 1) + Ebg2(N + 1) +1о§2 mn ij=1 i=1 т.е. количество битов, необходимых для записи системы (1) в двоичном виде. Алгоритм основан на построении последовательности эллипсоидов убывающего объёма. Важно подчеркнуть, что после выполнения указанного числа итераций алгоритм либо обнаруживает искомое решение, либо позволяет заключить, что система (1) несовместна. Метод эллипсоидов допускает множественное применение для решения различных прикладных математических задач. Рассмотрим важную проблему пороговой логики - задачу распознавания принадлежности произвольной булевой функции к классу пороговых [2 - 4]. Определение 1. Булева функция т(x1,...,xn) называется пороговой, если для неё существует линейное неравенство с действительными коэффициентами aiXi + ... + а„ж„ > b, (2) которое выполняется на тех и только тех наборах (x1,...,xn), для которых т(x1,..., xn) = 1. Коэффициенты « называются весами, а b - порогом. Задача проверки, является ли произвольная булева функция f (x1,... , xn) пороговой, несмотря на простоту постановки, является сложной. Для её решения предложены итеративные алгоритмы [5, 6]. Стоит отметить, что данная задача может быть сведена к анализу и решению систем линейных неравенств вида (1). Действительно, произвольная булева функция f (x1,... , xn) может быть задана таблично. В предположении, что f - пороговая, подстановка в неравенство (2) наборов (е^,... , е^), на которых функция равна 1, приведёт к выполнению неравенства, а наборов ($(i),... , $(i)), на которых функция равна 0, - к его невыполнению. Таким образом, будет построена система ai£(1i) + ... + araeii) ^ b, + ... + «n^ < b, + 1 -длина входа алгоритма, которая по существу является системой вида (1). Таким образом, применение метода эллипсоидов позволяет решить задачу характеризации пороговой функции с полиномиальной и заведомо известной сложностью. Отмечая высокую принципиальную значимость этого результата, следует, тем не менее, признать, что для пороговых функций, как показывают эксперименты, итеративные алгоритмы, как правило, выигрывают у метода эллипсоидов. Однако ни один из известных на сегодняшний день итеративных алгоритмов не позволяет дать отрицательного ответа, то есть что заданная произвольная булева функция не является пороговой, в то время как метод эллипсоидов эту задачу решает. Практические примеры применения алгоритма Хачияна и его модификаций выявили ещё одну особенность этого метода - рост модуля коэффициентов aj в ходе работы алгоритма. п - (i) С целью получения дискретных значений текущие действительные выражения для aj требуют корректировки, для которой необходимо построение самостоятельной процедуры. Корректировка может включать процедуры деноминации текущих значений и их округления. Определение 2. Под деноминацией будем понимать снижение значения ai за счёт деления на 10d при подходящим образом выбранном d. Коэффициент d будем называть порядком деноминации. Рассмотрим процедуры распознавания принадлежности булевой фукции к классу пороговых и деноминации на примере. Пусть булева функция f от трёх переменных задана таблично: Х1 Х2 x3 f (жьж2,жз) Xl X2 X3 f (xi, X2, X3) 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 По описанной выше методике сформируем систему линейных неравенств: bo ^ 0, аз - bo ^ -1, а2 - bo ^ -1, а2 + аз - bo ^ -1, (3) ' -ai + bo ^ 0, (3) -ai - a3 + bo ^ 0, ai + a2 - bo ^ -1, ai + a2 + a3 - bo ^ -1. Решим систему (3) модифицированным методом эллипсоидов [7]. Алгоритм находит решение системы за 6 итераций и получает вектор решений X = (a1, a2, a3, bo) = = (411789793,477, -445309873,255, -207254306,819, -5919482,343). Проведём процедуру деноминации полученного решения с порядком d = 6 и округление. В результате получим вектор X = (a1, a2, a3, bo) = (411, -445, -207, -6) и пороговое представление булевой функции f: f (£i, £2,£3) = 0 ^ L(ei,£2,£3) < -6. Здесь L(£i,£2,£3) = 411£i - 445£2 - 207£3. В данном примере порядок деноминации равен только 6, но практические эксперименты показывают значительный рост порядка деноминации при увеличении количества аргументов функции. Это обусловливает необходимость проверки принадлежности полученного в результате деноминации и округления решения к многограннику решений рассматриваемой системы неравенств. Поскольку в примере найдено решение системы (3), принадлежащее многограннику её решений, можно сделать вывод, что функция f принадлежит к классу пороговых; если бы метод эллипсоидов показал несовместность системы (3), то можно было бы утверждать, что функция не является пороговой. Таким образом, сделаем вывод о возможности применения метода эллипсоидов для распознавания пороговых булевых функций. Детальное изучение процесса его работы и сравнительный анализ с итеративными алгоритмами, в том числе в к-значной области, представляет актуальное направление для дальнейших исследований.

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