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


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

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

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

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

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

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

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

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

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

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

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

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

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

Задача получения наилучшего А. л. в явной форме решена для алгоритмов синтеза минимальных покрытий. Пусть задан набор , где - множество, - сложность Сложность набора есть Требуется построить покрытие М множествами из числа с минимальной сложностью. Система окрестностей для каждого вводится аналогично системе окрестностей для конъюнкций. Наилучший А. л. строится для системы окрестностей при фиксированных предикатах: множество вспомогательных предикатов пусто; в качестве основных рассматриваются предикаты (" не входит ни в одно минимальное покрытие М").и Р г.(" входит во все минимальные покрытия М"). Наилучшие А. л. построены также для вычисления простых свойств ребер графа. Большое число различных А. л. было предложено для решения задач минимизации булевых функций, дискретного линейного программирования и т. д.

Важное место в теории А. л. занимают задачи о невычислимости экстремальных свойств в классе А. л. Если на парах , задана система вложенных окрестностей: и А. л. работает по системе окрестностей где , то говорят, что А. л. имеет индекс k. Число предикатов в определении А. л. естественно считать величиной па мят и А. л. Пусть задано множество предикатов Считается, что все предикаты, участвующие в определении А. л., принадлежат . Пусть - результат применения А. л. А к. Про предикат говорят, что он не является -вычислимым, если для всякого А. л. индекса kс величиной памяти l, основным предикатом и вспомогательными из найдется множество такое, что в предикат будет вычислен не для всех элементов.

Пусть - совокупность всех булевых функций от переменных и - предикат "конъюнкция входит хотя бы в одну минимальную дизъюнктивную нормальную форму". При естественных ограничениях на класс предикатов установлено, что предикат
не является -вычислимым, если . Интересно отметить, что предикат ) "конъюнкция входит хотя бы в одну тупиковую дизъюнктивную нормальную форму f" (см. Булевых функций нормальные формы).является (2, 1)-вычислимым, но не (1, 1)-вычислимым. Аналогичные результаты получены для предикатов, описывающих вхождение ребра в минимальный путь между заданными вершинами графа.

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

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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АЛГОРИТМ ЛОКАЛЬНЫЙ" в других словарях:

  • Алгоритм муравейника — Поведение муравьёв явилось вдохновением для создания мета эвристической технологии оптимизации Алгоритм муравейника (англ. Ant colony optimization algorithm или ACO)  является вероятностной техникой для решения вычислительных задач, которая… …   Википедия

  • Локальный поисковик — Tracker Локальный поисковик или персональный поиск  программное обеспечение для быстрого поиска информации в файлах пользователя, то есть п …   Википедия

  • Алгоритм Лукаса — Канаде широко используемый в компьютерном зрении дифференциальный локальный метод вычисления оптического потока. Основное уравнение оптического потока содержит две неизвестных и не может быть однозначно разрешено. Алгоритм Лукаса Канаде обходит… …   Википедия

  • Локальный поиск (оптимизация) — Алгоритмы локального поиска  группа алгоритмов, в которых поиск ведется только на основании текущего состояния, а ранее пройденные состояния не учитываются и не запоминаются. Основной целью поиска является не нахождение оптимального пути к… …   Википедия

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

  • АЛГОРИТМ, — алгорифм, Ч точное предписание, к рое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из нек рой совокупности возможных для данного А. исходных данных) и направленный на… …   Математическая энциклопедия

  • Генетический алгоритм — (англ. genetic algorithm)  это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих… …   Википедия

  • Муравьиный алгоритм — Поведение муравьёв явилось вдохновением для создания метаэвристической технологии оптимизации Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO)  од …   Википедия

  • БУЛЕВЫХ ФУНКЦИИ МИНИМИЗАЦИЯ — представление булевых функций нормальными формами (см. Булевых функций нормальные формы). простейшими относительно нек рой меры сложности. Обычно под сложностью нормальной формы понимается число букв в ней. В этом случае простейшая форма наз.… …   Математическая энциклопедия

  • БУЛЕВЫХ ФУНКЦИИ МЕТРИЧЕСКАЯ ТЕОРИЯ — направление, связанное с изучением числовых характеристик и метрич. свойств булевых функций. Основные разделы этой теории посвящены исследованию свойств почти всех булевых функций (см. Булевых функций минимизация), свойств совокупности всех… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.