Дискретно-непрерывная математика (стр. 108 )

ЛО третьего рода вычисляется последовательным разложением по столбцу (4.41) или строке (4.42) либо по совокупности столбцов (4.43)

или строк (4.44) (ЛО вычисляется по двойственным разложениям). Процедура вычислений совпадает с аналогичной для ЛО второго рода. Остановимся лишь на определении оптимального числа rопт строк (столб­цов) , по которым выполняется разложение ЛО. Этому числу соответствует минимальная сложность вычисления ЛО. Как видно из оценки (4.49) сложности Nr (М) вычисления М × М-ЛО последовательным разложением по r строкам (столбцам), функция с ростом r убывает, когда N(r) растет медленнее, чем (такой рост можно обеспечить, например, вычислением r× r-ЛО разложением по столбцу, когда по (4.46)

Однако из уравнения (4.47) также видно, что значение f(r) не меняется при замене r на М - r, т. е. функция f(r) симметрична относи­тельно прямой и потому при возрастает. Итак,

(4.68)

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

М = 15, а дихотомическое раз­ложение по совокупности строк (столбцов) - ЛО порядка М = 20.

ЛО четвертого рода вычисляются последовательным разложением

по столбцу (4.59) или по совокупности столбцов (4.62) (ЛО вычисля­ются по двойственным разложениям). Процедура вычислений - как у ЛО второго рода. Дня определения оптимального числа столбцов, по которым выполняется разложение (4.62), распишем соответствующую оценку (4.67) сложности Nr (Р) вычисления

М × P-ЛO, полагая, что заключитель­ный М × r-ЛО будет вычисляться разложением по столбцу (так что N(r) = 2М r согласно (4.64)) и пренебрегая —1 в знаменаМы получим

(4.69)

Из (4.69) следует, что Nr (Р) монотонно убывает по r. Следовательно,

(4.70)

Согласно (4.70) оптимальной процедурой оказывается вычисление ЛО путем его разложения по совокупности всех Р столбцов, или, что то же самое (см. (4.62)), без разложения. В этом случае заключительным стано­вится весь M× Р-ЛО; его по нашему соглашению будем вычислять разло­жением по столбцу. Итак, оптимальной процедурой вычислений ЛО четвер­того рода является последовательное разложение по столбцу.

4.12. Приближенное вычисление логических определителей

Сложность вычисления ЛО методами § 4.11 растет c увеличением разме­ров ЛО. Поэтому вычисление больших ЛО нередко затруднительно. В этих случаях, целесообразен переход к приближенному вычислению ЛО, слож­ность которого растет с увеличением размеров ЛО достаточно медленно.

Рассмотрим, например, ЛО третьего рода Исходим из формулы (4.42) разложения ЛО. Опустим в разложении (4.42) часть двучленных сумм. Тогда заключительный максимум (дизъюнкция БЛ) будет браться по суженной сравнительно с первоначальной области так, что ее значение может лишь уменьшиться. В итоге получим разложение — оценку ЛО снизу, выраженное через меньшие ЛО. Последовательно применяя это разложение, получим явное выражение, служащее оценкой исходного ЛО снизу. По нему и вычисляется приближенно ЛО.

Возможны различные принципы исключения двучленных сумм в разло­жении (4.42). Примем такой принцип: в первую очередь опускаем в (4.42) суммы с относительно малыми значениями элементов т. е. считаем, что в определяющую сумму в первую очередь должны попадать максимальные элементы своих строк ЛО. Обозначим kr (i) номер столбца, в ко­тором стоит r-й порядковый элемент i-й строки ЛО Этот элемент обо­значим так что a — минимальный, а — максималь­ный элементы г-й строки. По нашему принципу можно в разложении (4.42) сохранить лишь одну сумму — ту, которая содержит максимальный эле­мент i-й строки. При этом получим для ЛО приближенное разложение первого порядка по i-й строке

(4.71)

Сохранив в разложении (4.42) две суммы - те, которые содержат макси­мальный и предмаксимальный элементы i-й строки, — получим приближен­ное разложение второго порядка по i-й строке

(4.72)

и т. д. Разложим ЛО по i-й строке с порядком pi. Получившиеся в раз­ложении ЛОснова разложим по j-й строке с поряд­ком p2 и т. д. В итоге получим явное выражение — оценку ЛО снизу, по которому можно вычислить приближенно ЛО.

Рассмотрим простейший случай, когда все разложения первого поряд­ка Тогда в разложении участвуют только максималь­ные элементы строк. Обозначим их Разложим по первой строке:

Логическое дополнение снова разложим по его первой строке (по второй строке Здесь — максимальный элемент второй строки ЛО, полученного из вычеркиванием k(1)-го столбца (элемент стоит в k(2)-м столбце - ЛО, полученный вычеркиванием в строк 1, 2 и столбцов k(1), k(2). Последний ЛО можно раз­ложить по его первой строке и т. д. Подставив каждое следующее разложе­ние в предыдущее, найдем выражение — оценку

(4.73)

Согласно (4.73) алгоритм приближенного вычисления М × М –ЛО та­ков: 1) выделить в первой строке максимальный элемент вы­черкнуть столбец k (1), содержащий этот элемент; 2) во второй строке по­лучившегося М × (М — 1)-ЛО выделить максимальный элемент и вычеркнуть столбец k (2), содержащий этот элемент; 3) в третьей строке получившегося М × (М - 2)-ЛО выделить максимальный элемент и вычеркнуть столбец k (3), содержащий этот элемент;...; М) взять единственный элемент оставшийся в послед­ней, М-й строке ЛО после указанных вычеркиваний столбцов k(1),... ..., k(М— 1). Совокупность всех выделенных элементов дает приближенно определяющую сумму ЛО а сумма этих элементов - приближенное значение Изменив порядок просмотра строк, получим другое при­ближенное значение Алгоритм приближенного вычисления ЛО отли­чается от изложенного тем, что выделяются минимальные элементы строк. Сложность изложенного способа вычисления ЛО

(4.74)

Таким образом, этим способом можно вычислять ЛО практически неогра­ниченного размера М. Точность способа тем выше, чем больше в ЛО строк, максимальные (минимальные) элементы которых расположены в столб­цах, не содержащих аналогичных элементов других строк. Заметим, что вместо строк можно просматривать столбцы.