ется значение переменной xt+3 ; пусть конкретизированное значение xt+3 равно b

(b g {0, 1}). Подструктура 77t (Гг) , по предположению индукции, является объединени-

t

ем t-пересечений Bi (Гг) ( i = 1, 2, ... , dt (Гг) ). В nt (Гг) можно выделить подструктуры: 77t (Гг , b) и 77t (Гг , — b), объединяющие, соответственно, t-пересечения со значением xt+3 = b и t-пересечения со значением xt+3 = — b . Соотношения (2) - (4), согласно индукционной гипотезе, выполняются для вершины Vt и в том частном случае, если переменная xt+3 = b во всех подструктурах, участвующих в формировании подструктуры 77t (Гг). Следовательно, выделение подструктуры nt (Гг , b) достигается следующими средствами:

а)конкретизация переменной в вершине Vt : 77t (xt+3 — b);

б)проецирование ярусов 1, 2, ... , t - 1 на подструктуру nt с xt+3 = b , с унификацией всех промежуточных и результирующих подструктур.

(Та же подструктура 77t (Гг , b) может быть выделена путем конкретизации одновременно двух переменных: xt+2 и xt+3 (xt+3 — b) при формировании подструктур, приписанных ребрам, подходящим к вершине Vt от вершин (t - 1)-го яруса (см. замечание 2 в разделе 4). Очевидно, что увеличение числа конкретизируемых переменных до двух при продвижении подструктур на один ярус не влияет на содержание и результативность применения согласующих правил.)

Но в соответствии с правилами продвижения и согласованного продвижения подструктура-ребро nt;t+1 (Гг) совпадает с подструктурой nt (Гг , b), что означает выполнение (2) - (4) для 77у+! (Гг). Поскольку nt;t+1 (Гг) = 77t (Гг) n nt+1 (Гг), в вершину Vt+1 по ребру (Vt , Vt+1) продвинуто объединение (t + 1)-пересечений, сформированных в подструктуре nt (Гг , b).

Все приведенные рассуждения сохраняют свою силу и по отношению ко второму, возможно, существующему, ребру гиперструктуры, которое соединяет вершину Vt+1 с вершиной Vt t -го яруса. Итак, соотношения (2) - (4) верны для всех вершин каждой ГС системы. Таким образом, любая подструктура-вершина (n - 2)-го яруса в каждой из ГС Г2 , ... , Гк представляет собой объединение одноименных (n - 2)-пересечений, т. е. совместных выполняющих наборов для СКТ S1 , S2 , ... , Sk . Этот вывод завершает доказательство достаточности в общем случае.

Дадим краткую содержательную интерпретацию доказательства теоремы 2. В терминах вершин и ребер базисного графа в ГС Г2 , ... , Гк определены эквивалентные множества допустимых маршрутов. Следовательно, для каждой из СКТ S2 , ... , Sk определено множество выполняющих наборов, которое тождественно отображается на одно и то же множество выполняющих наборов для СКТ S1 .

Конкретный СВН, удостоверяющий выполнимость формулы F, может быть определен при согласованном продвижении подструктуры (n - 2)-го яруса на ярус 1 в системе гиперструктур, с уточнением значений переменных в порядке, обратном принятому при построении СГС.

Процедура отыскания СВН для формулы F рассматриваемого примера базируется на унифицированных СКТ S1, S2 и S3 , представленных в таблице 4 (основой для

формирования структур таблицы 4 служит таблица 2). Формирование первого яруса гиперструктур Г2 и Г3 с унификацией подструктур, приписанных вершинам каркаса, помеченным значениями 001 и 101 для тройки a, b, c, сразу же приводит к получению элементарных СКТ, соответствующих двум СВН: 00111011 и 10111100 для исходной нумерации переменных. Дальнейшее формирование системы ГС становится излишним, поскольку такое начало указывает на то, что будет построена оптимальная СГС. Легко видеть, что каждый из полученных наборов не покрывает ни одной строки таблицы 1.

Таблица 4. Унифицированные СКТ S1, S2 и S3

S1S2S3

6. Сложность вычислений

Число переменных в задаче определяет максимальный размер формируемых гиперструктур. Гиперструктура состоит из не более чем 8(n - 2) подструктур; каждая подструктура включает не более 8(n - 2) строк. Из всех операций над СКТ, введенных в разделе 2, унификация имеет сложность, пропорциональную n2 , поскольку связана с перебором сочетаний из n по 2; остальные операции сводятся к обработке упорядоченных строк отдельных ярусов и при оптимальной реализации имеют линейную сложность относительно параметра n .

На этапе построения СГС, состоящей из к - 1 гиперструктур, при формировании j -го яруса используются j - 1 предшествующих ярусов (j = 2, . , n - 2). С учетом тождества 1 + 2 + . + (n - 3) = (n - 2)(n - 3) / 2 , указывающего на квадратичный рост относительно n числа фактически обрабатываемых подструктур, получаем асимптотическую оценку сложности построения упомянутых гиперструктур - O(n4 к). В терминах параметров задачи, определяющих размер входа, эта оценка трансформируется в O(n4 m), так как к < m (реально к << m).

Таким образом, в целом сложность алгоритма, включающего предложенные процедуры, растет полиномиально относительно размера входа.

7. Апробация алгоритма и выводы

Тестирование программы, реализующей системную эффективную процедуру, выполнялось на ПК на базе микропроцессора Athlon, 900 MHz, при входных параметрах, изменяющихся в интервалах: n = 5 100, m = 10 3000. Апробация алгоритма не носила характера статистических испытаний и имела целью выявление его временных характеристик, прежде всего, при больших "размерах входа". Система генерации данных при заданных значениях n и m чередовала (случайным образом, с помощью ГСЧ) формирование произвольных формул с формированием заведомо выполнимых и заведомо невыполнимых формул. Было выполнено около 500 тестовых прогонов программы для формул с параметрами n > 25, 100 < m < 1000, в том числе при n = 100, m = 1000 одновременно. Характерное время вычислений в минутах: т < 3 для n < 50, т < 8 для n = 64, т < 20 для n = 80, т < 60 для n = 100.

Машинный эксперимент дал стопроцентно положительный результат. При каждом запуске программа либо сообщала о невыполнимости формулы - в том случае, когда построение СГС не завершалось (см. необходимое условие теоремы 2), либо объявляла формулу выполнимой с обязательной выдачей выполняющего набора переменных. Следует подчеркнуть, что испытывались формулы, которые описываются потенциально существующими таблицами истинности, содержащими до 2100 строк!

Использованный метод решения NP-полной задачи можно назвать принципом тождественного отображения множеств компонент несогласованных структур на базисное множество. Термин несогласованные здесь характеризует структуры, не вступающие в непосредственные операции друг с другом; исключение составляет операция унификации. Отображаемыми компонентами являются (n - 2)-пересечения в системе гиперструктур. Работа первична по используемым средствам и не опирается на какие-либо предшествующие работы (кроме фундаментальных постановочных работ, в первую очередь [1, 2]). Результаты исследования модели рассчитаны на обобщения в силу полиномиальной сводимости трудноразрешимых задач друг к другу. Последние занимают все большее место при моделировании технологических и производственных систем, имеющих дискретное, в частности, комбинаторное описание [3].

ЛИТЕРАТУРА

1.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

2.Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.

2. Dimopoulos C., Zalzala Ali M.S., Recent deVelopments in eVolutionary computation for manufacturing optimization // IEEE Transactions on EVolutionary Computation, 2000. V.4, № 2. P.93-113.