Математическая энциклопедия - алгоритм локальный

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

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

Пусть Г конечный неориентированный граф, множество вершин Г, множество ребер Г. Окрестность 'ребра графа Г состоит из всех вершин ребер, инцидентных ребру R, а также из всех ребер, вершины к-рых входят в окрестность I. Пусть определена окрестность , тогда окрестность состоит из всех вершин ребер, инцидентных вершинам окрестности и всех ребер, вершины к-рых принадлежат окрестности . Аналогично вводятся окрестности для произвольной вершины графа Г.

Пусть на парах определена система двуместных предикатов к-рая разбита на два непересекающихся подмножества . Элементы первого подмножества наз. основными предикатами, второго вспомогательными предикатами. Вектор наз. информационным, если . Вектор наз. д о-пустимым для " ...., если для всех выполнено равенство . Множество всех информационных векторов, допустимых для А. в , наз. информационным множеством в

Пусть и , i= =1, 2, ..., q. Множество наз. допустимым для . Класс всех допустимых для множеств наз. информационным классом множества по системе предикатов Очевидно, что окрестность определяет окрестность

Введем систему функций таких, что Функции определены на всех парах таких, что и удовлетворяют следующим условиям: 1) ; 2) множество , которое получается из заменой элемента , допустимо для , т. е. . Для краткости пары обозначаются через .

На нек-рых из описанных множеств вводится частичный порядок: 1) на множестве 2) на множестве информационных векторов длины , если 3) на множестве элементов с отметками . , если 4) на множестве , если, во-первых, принадлежат одному информационному классу и, во-вторых, из того, что и , следует ; 5) на множестве окрестностей вида и , тогда и только тогда, когда и из условий следует, что

Пусть Аи В - элементы одного из множеств 1) 5). Если то элементы Аи Вназ. равными по информации, что обозначается Функция наз. монотонной, если из соотношения следует, что для i= 1, 2, ..., l

Для определения А. л. необходимо также ввести алгоритм упорядочивания. Пусть Мпроизвольное множество, составленное из элементов с информационными векторами, а

Рассмотрим множество всех пар таких, что Алгоритм А л упорядочивает множество . А. л. Аполностью определяется системой предикатов разбиением этой системы на основные и вспомогательные предикаты, системой монотонных функций и алгоритмом .

Пусть . Первый шаг А. л. состоит в следующем. К множеству , где , применяется алгоритм ; длк первой по порядку пары вычисляется и элемент заменяется на если то берется вторая пара, и т. д.; если для всех элементов выполнено равенство то А. л. Азаканчивается после просмотра всех пар из . В противном случае, после замены вектора на новый вектор если нет больше элементов, у к-рых на первых rместах в информационных векторах имеется хотя бы один символ Д, алгоритм Азаканчивается; если они есть, то заканчивается первый шаг А. л. Пусть выполнено nшагов А. л. А. Описание шага в точности повторяет описание первого, если вместо множества рассматривать множество в к-рое перешло после первых пшагов А. я. А. В силу монотонности функций , А. л. Азакончится после конечного числа шагов.