О построении неортодоксальных моделей для задач дискретной оптимизации

Романов В.Ф. (romvf@vpti.vladimir.ru)

Владимирский государственный университет

1. Постановка задачи. Табличные формулы

Известно, что в число средств анализа и классификации по сложности дискретных оптимизационных задач входит метод сведения одних задач к другим. В частности, в теории трудноразрешимых задач широко применяется полиномиальное сведение, основанное на рассмотрении моделей, использующих компоненты специального назначения [1, 2]. Нетрадиционное представление задач с модификацией структур данных может способствовать углублению анализа и выявлению тех особенностей задач, которые позволяют строить для них наиболее целесообразные алгоритмы.

В работе рассмотрена неортодоксальная графо-комбинаторная модель для классической трудноразрешимой задачи 3-ВЫПОЛНИМОСТЬ и эффективный (полиномиальный) алгоритм построения этой модели. Предложенный метод анализа булевой формулы выявляет возможность классификации формулы в широком диапазоне ее параметров, характеризующих "размер входа" задачи.

Задача 3-ВЫПОЛНИМОСТЬ (далее 3-ВЫП), формулируется следующим образом: для данных m элементарных дизъюнкций С1, ... , Ст , каждая из которых содержит в точности три литерала, относящихся к булевым переменным x1 , ... , xn , определить, выполнима ли формула

F = C1& C2&...&Cm.

Для формулы, представленной в КНФ, введем условную запись в виде таблицы (табличной формулы), содержащей n столбцов, отмеченных именами переменных, и m строк, каждая из которых представляет терм Ci последовательностью из нулей и единиц: 0 в j-м столбце и i-й строке обозначает появление переменной xj в терме Ci без инверсии, 1 - со знаком инверсии. Так, формуле

F = (— x1 v x2 v — x4 )( x2 v x3 v — x5 )(— x3 v — x4 v x5 )

соответствует табличная формула:

x1 x2 x3 x4 x5 1 0 1 0 0 1 1 1 0 .

Очевидно, что если 0 обозначает ложь, а 1 - истину (независимо от обозначений, принятых для табличной формулы), то F = 0 на тех и только тех наборах значений переменных, где в качестве подмножества присутствует хотя бы одна строка из табличной формулы.

2. Структуры компактных троек

Рассмотрим сначала формулу, термы которой при некоторой подходящей нумерации переменных представляют собой компактные тройки, т. е. тройки литералов lj , , lj+2 с номерами, расположенными подряд; lj е { xj, — xj }, 1 < j < (n - 2). Такую формулу назовем формулой компактных троек (ФКТ). Идея разрешения ФКТ, заданной таблицей для F, заключается в ее преобразовании (полиномиальном по сложности) в структуру компактных троек (СКТ). Элементами СКТ являются строки - компактные тройки значений переменных, расположенные на n - 2 ярусах. Ярусы включают соответственно переменные с номерами 1, 2, 3; 2, 3, 4; n - 2, n - 1, n . При построении СКТ каждый ярус заполняется только теми двоичными наборами трех переменных, которые отсутствуют в ФКТ. Далее выполняется очищение структуры -удаление из СКТ строк, не образующих конкатенации (сочленения по совпадающим значениям переменных) хотя бы с одной строкой каждого соседнего яруса.

Если хотя бы один ярус СКТ оказывается пустым, вся структура объявляется пустым множеством, а формула F - невыполнимой. СКТ, содержащая n - 2 яруса, может быть сформирована тогда и только тогда, когда формула F выполнима. Действитель-

n

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

Например, для ФКТ F1 преобразование приводит к СКТ Z; в промежуточной структуре Q зачеркнуты строки, удаленные согласно процедуре очищения. В рассмотренном примере выявляются два выполняющих набора: 01101 и 10011.

F1QZ

x1 x2 x3 x4 x5x1 x2 x3 x4 x5x1 x2 x3 x4 x5

0 0 00-4-00 1 1

00 10 1 11 0 0

10 11 0 01 1 0 1 1 14-+-00 0 1

00 00 0 11 0 1

10 00-4-00 1 1

1 0 10-4-^-

1 1 11 1 0

01 00-0-0

10 00-0-41 1 10 1 1

1 0 1 4-+-0

Определим на множестве СКТ, построенных на основе фиксированной нумерации n переменных, понятие равенства СКТ, а также операции объединения, пересечения и конкретизации. Равенство двух СКТ S1 и S2 (S1 = S2) устанавливается при равенстве множеств строк на каждом из ярусов. Объединение и пересечение СКТ выполняются по обычным правилам для теоретико-множественных операций, при условии, что элементами множеств являются строки одноименных ярусов структур-операндов; пересечение завершается очищением результирующей СКТ. Ниже приведены примеры выполнения операций.

S1

x1 x2 x3 x4 x5 0 1 0 0 1 1

1 01

1 10

01 1

10 0 10 1

S3 = S1 u S2 x1 x2 x3 x4 x5 0 1 0

011

100 10 1 11 0 00 1

01 1

10 0 1 0 1

В S4 последняя строка вычеркивается согласно процедуре очищения.

Операция конкретизации в СКТ S переменной xj , 1 < j < n , заключается в присваивании этой переменной определенного (константного) значения: xj = 0 или xj = 1, что влечет удаление из СКТ всех строк с инверсным значением xj , с последующим очищением структуры. Формальные обозначения для этой операции: S (xj — 0) или S (xj — 1). Так, для СКТ из приведенного примера справедливо:

S3 (x3 — 1) x1 x2 x3 x4 x5 0 1 1 1 1 0

1 0 0

1 0 1 ,

S2

x1 x2 x3 x4 x5

01 1

10 0

1 1 0

00 1

1 0 1

01 1

S4 = S1 n S2

x1 x2 x3 x4 x5 0 1 1

11 0

10 1 0-4-^-