АЛГОРИТМ ЛОКАЛЬНЫЙ

Расстановка ударений: АЛГОРИ`ТМ ЛОКА`ЛЬНЫЙ

АЛГОРИТМ ЛОКАЛЬНЫЙ - алгоритм, устанавливающий свойства элементов множества и использующий на каждом шаге при этом только информацию об окрестности элемента. В терминах А. л. естественно формулируются и решаются задачи о существовании или несуществовании эффективных алгоритмов для различных дискретных экстремальных задач.

Пусть задано семейство {: ∈ М) множеств, и пусть каждой паре (, ), где ∈ , сопоставлено множество S(, ) такое, что: 1) ∈ S(, ), 2) S(, ) ⊆ , 3) если ∈ ₁, ∈ ₂ и S(, ₁) ⊆ ₂ ⊆ ₁, то S(, ₁) = S(, ₂). Тогда множество S(, ) наз. окрестностью в . Примерами окрестностей служат окрестности конъюнкции в сокращенной нормальной форме (см. Булевых функций минимизация).

Пусть Г - конечный неориентированный граф, Г = М₁ ∪ М₂, М₁ = {a₁, ..., a_q} - множество вершин Г, M₂ = {(a_i1, a_i2), ..., (a_rp, a_rt)} - множество ребер Г. Окрестность S₁ (R, Г) ребра R = (а_i, а_j) графа Г состоит из всех вершин ребер, инцидентных ребру R, а также из всех ребер, вершины к-рых входят в окрестность S₁ (R, Г). Пусть определена окрестность S_{n - 1} (R, Г), тогда окрестность S_n (R, Г) состоит из всех вершин ребер, инцидентных вершинам окрестности S_{n - 1} (R, Г), и всех ребер, вершины к-рых принадлежат окрестности S_n (R, Г). Аналогично вводятся окрестности S₁ (а_j, Г), ..., S_n (a_j, Г),... для произвольной вершины a_j графа Г.

Пусть на парах (, ), ∈ , определена система двуместных предикатов Р₁ (, ), ..., Р_l (, ), к-рая разбита на два непересекающихся подмножества < P₁, ..., P_r > и < P_{r + 1}, ..., P_l >. Элементы первого подмножества наз. основными предикатами, второго - вспомогательными предикатами. Вектор α̃ = (α₁, ..., α_l) наз. информационным, если α ∈ {0, 1, Δ }, i = 1, 2, ..., l. Вектор α̃ наз. допустимым для в , если для всех α_i ≠ Δ выполнено равенство α_i = Р_i (, ). Множество J(, ) всех информационных векторов, допустимых для в , наз. информационным множеством в .

Пусть = {₁, ..., _q} и (α_i1, ..., α_il) ∈ J(_i, ), i = 1, 2, q. Множество * = {₁^{α₁₁, ..., α_1l}, ..., _q^{α_q1, ..., α_ql}} наз. допустимым для . Класс J() всех допустимых для множеств * наз. информационным классом множества по системе предикатов P₁, ..., P_l . Очевидно, что окрестность S(, ) определяет окрестность S(^{α₁, ..., α_l}, *).

Введем систему функций φ₁, ..., φ_l таких, что φ_i (^{α₁, ..., α_l}, S(^{α₁, ..., α_l}, *)) = (β₁, ..., β_l). Функции φ_i определены на всех парах (^{α₁, ..., α_l}, S(^{α₁, ..., α_l}, *)) таких, что ^{α₁, ..., α_l} ∈ *, * ∈ J(), и удовлетворяют следующим условиям: 1) α_i = β_j, если j ≠ j, 2) множество ̃ *, которое получается из * заменой элемента ^{α₁, ..., α_l} на^{β₁, ..., β_l} допустимо для , т. е. ̃ * ∈ J(). Для краткости пары (^{α₁, ..., α_l}, S(^{α₁, ..., α_l}, *)) обозначаются через (, α₁, ..., α_l, S, *).

На нек-рых из описанных множеств вводится частичный порядок: 1) на множестве M₁ = {0, 1, Δ } - Δ < 0, Δ < 1, 2) на множестве М₂ информационных векторов длины l - (α₁, ..., α_l) ≤ (β₁, ..., β_l), если α_i ≤ α_i, i = 1, 2, ..., l; 3) на множестве элементов с отметками - ^{α₁, ..., α_l} ≤ ^{β₁, ..., β_l}, если (α₁, ..., α_l) ≤ (β₁, ..., β_l); 4) на множестве M* = ∪ _{∈ M} J() - *₁ ≤ *₂, если, во-первых, *₁ и *₂ принадлежат одному информационному классу J() и, во-вторых, из того, что ^{α₁, ..., α_l} ∈ *₁ и ^{β₁, ..., β_l} ∈ *₂, следует (α₁, ..., α_l) ≤ (β₁, ..., β_l); 5) на множестве окрестностей вида S(^{α₁, ..., α_l}, *) - S₁ ≤ S₂, где S₁ = S (^{α₁, ..., α_l}, *₁) и S₂ = S (^{β₁, ..., β_l}, *₂), тогда и только тогда, когда S(, ₁) = S(, ₂) и из условий ^{γ₁, ..., γ_l} ∈ S₁, ^{δ₁, ..., δ_l} ∈ S₂ следует, что γ₁, ..., γ_l ≤ δ₁, ..., δ_l .

Пусть А и В - элементы одного из множеств 1)-5). Если A ≤ B и А ≥ В, то элементы A и В наз. равными по информации, что обозначается АB. Функция φ (, α₁, ..., α_l, S, *) наз. монотонной, если из соотношения S₁ ≤ S₂ следует, что для i = 1, 2, ..., l. φ_i (, α₁, ..., α_l, S₁, *₁) ≤ φ_i (, β₁, ..., β_l, S₂, *₂).

Для определения А. л. необходимо также ввести алгоритм А_π упорядочивания. Пусть М - произвольное множество, составленное из элементов с информационными векторами, а N = {1, 2, ..., l}. Рассмотрим множество MN всех пар (^{α₁, ..., α_l}, j) таких, что ^{α₁, ..., α_l} ∈ M, j ∈ N, α_j = Δ. Алгоритм А_π упорядочивает множество MN. А. л. А полностью определяется системой предикатов P₁, ..., P_l, разбиением этой системы на основные P₁, ..., P_r и вспомогательные P_{r + 1}, ..., P_l предикаты, системой монотонных функций φ₁, ..., φ_l, φ_i = φ_i (, α₁, ..., α_l, S, *), и алгоритмом А_π .

Пусть . Первый шаг А. л. состоит в следующем. К множеству MN, где M = *, применяется алгоритм А_π ; для первой по порядку пары (^{α₁, ..., α_l}, j) вычисляется фу (, α₁, ..., α_l, S, *) = (β₁, ..., β_l) и элемент^{α₁, ..., α_l} заменяется на^{β₁, ..., β_l} если (α₁, ..., α_l) = (β₁, ..., β_l), то берется вторая пара, и т. д. ; если для всех элементов (^{γ₁, ..., γ_l}, i) выполнено равенство φ_i (, γ₁, ..., γ_l, S, *) = (γ₁, ..., γ_l), то А. л. А заканчивается после просмотра всех пар из MN. В противном случае, после замены вектора (α₁, ..., α_l) на новый вектор (β₁, ..., β_l), если нет больше элементов, у к-рых на первых r местах в информационных векторах имеется хотя бы один символ Δ, алгоритм А заканчивается; если они есть, то заканчивается первый шаг А. л. Пусть выполнено n шагов А. л. А. Описание (n + 1)-го шага в точности повторяет описание первого, если вместо множества * рассматривать множество *_n в к-рое перешло * после первых n шагов А. л. А. В силу монотонности функций φ_i, i = 1, 2, ..., l, А. л. А закончится после конечного числа шагов.

Исходными теоремами для А. л. являются теорема единственности и теорема существования наилучшего алгоритма. Первая теорема утверждает, что результат вычислений основных предикатов не зависит от алгоритма А_π (порядка обхода элементов множества *). Вторая теорема утверждает существование в весьма общих предположениях наилучшего А. л., т. е. А. л., к-рый по заданной фиксированной системе окрестностей вычисляет заданные основные предикаты при фиксированных вспомогательных предикатах всегда, когда это делает любой другой А. л. с той же системой окрестностей, основных и вспомогательных предикатов.

Задача получения наилучшего А. л. в явной форме решена для алгоритмов синтеза минимальных покрытий. Пусть задан набор < ₁, ..., _q, μ₁, ..., μ_q, М >, где _i - множество, μ_i - сложность _i, μ_i > 0, i = 1, 2, ..., q, M ⊆ ∪^q_{i = 1} M_i Сложность набора (_i1, ..., _ip есть Требуется построить покрытие М множествами из числа ₁, ..., _q с минимальной сложностью. Система окрестностей S₁, ..., S_n,... для каждого _i вводится аналогично системе окрестностей для конъюнкций. Наилучший А. л. строится для системы окрестностей S_k при фиксированных предикатах: множество вспомогательных предикатов пусто; в качестве основных рассматриваются предикаты Р₁ (, М) (« не входит ни в одно минимальное покрытие М») и Р₂ (, М) (« входит во все минимальные покрытия М»). Наилучшие А. л. построены также для вычисления простых свойств ребер графа. Большое число различных А. л. было предложено для решения задач минимизации булевых функций, дискретного линейного программирования и т. д.

Важное место в теории А. л. занимают задачи о невычислимости экстремальных свойств в классе А. л. Если на парах (, ), ∈ , ∈ M, задана система вложенных окрестностей: S₁ (, ) ⊆ S₂ (, ) ⊆... ⊆ S_n (, ) ⊆... и А. л. работает по системе окрестностей S (, ), где S_{k - 1} (, ) ⊆ S(, ) ⊆ S_k (, ), то говорят, что А. л. имеет индекс k. Число предикатов Р₁, ..., Р_l в определении А. л. естественно считать величиной памяти А. л. Пусть задано множество предикатов Р(, ). Считается, что все предикаты, участвующие в определении А. л., принадлежат . Пусть А(*) - результат применения А. л. A к *, * ∈ J(), ∈ M. Про предикат Р₁ (, ) говорят, что он не является (k, l)-вычислимым, если для всякого А. л. индекса k с величиной памяти l, основным предикатом Р₁ и вспомогательными Р₂, ..., Р_l из найдется множество * такое, что в А (*) предикат Р₁ будет вычислен не для всех элементов.

Пусть f(x₁, ..., x_n) - совокупность всех булевых функций от переменных x₁, ..., x_n и Р₁ (, f(x₁, ..., x_n)) - предикат «конъюнкция входит хотя бы в одну минимальную дизъюнктивную нормальную форму». При естественных ограничениях на класс предикатов установлено, что предикат Р₁ (, f(х₁, ..., x_n)) не является (k, l)-вычислимым, если kl < const ⋅ 2n. Интересно отметить, что предикат Р (, f(x₁, ..., x_n)) «конъюнкция входит хотя бы в одну тупиковую дизъюнктивную нормальную форму f» (см. Булевых функций нормальные формы) является (2, 1)-вычислимым, но не (1, 1)-вычислимым. Аналогичные результаты получены для предикатов, описывающих вхождение ребра в минимальный путь между заданными вершинами графа.

Лит. : [1] Журавлев Ю. И., «Кибернетика», 1965, № 1, с. 12-19; 1966, №2, с. 1-11; [2] Хуторянская И. В., «Кибернетика», 1971, № 1, с. 29-33; [3] Журавлев Ю. И., сб. «Проблемы кибернетики», 1962, вып. 8, с. 5-44.

См. также лит. при статье Булевых функций минимизация.

Ю. И. Журавлев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.