Алговики - Вклад [ru]

Участник:Щекалев Алексей Андреевич/Поиск минимального покрытия булевой матрицы

2017-10-23T20:06:23Z

Щекалев Алексей Андреевич: /* Литература */

= Свойства и структура алгоритма =
== Общее описание алгоритма ==

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

== Математическое описание алгоритма ==
Пусть <math>V = {v_1,v_2,...,v_m}, E = {e_1,e_2,...,e_n}</math> два конечных множества и <math>P (x, y)</math> некоторый предикат заданный на множестве <math>V \times E </math>. Обычно множество <math>E</math> – называют покрывающим, а множество <math>V</math> – покрываемым. Если <math>P (v_i,e_j) = 1</math>, то говорят, что <math>e_j</math> покрывает <math>v_i</math>, а <math>v_i</math> покрывается <math>e_j</math>. Пусть <math>M \subseteq E</math>. Обозначим через <math>\mu_M(v_i)</math> число всех элементов <math>e_i</math> из <math>M</math> , которые покрывают элемент <math>v_i</math>, т.е. <math>\mu_M(v_i) = |\{e_j \in M|P(v_i,e_j) = 1\}|</math>.

'''Определение 1.''' Множество <math>M</math> называется покрытием множества <math>V</math>, если <math>\forall v_i \in V: \mu_M(v_i) \ge 1</math> Другими словами каждый элемент множества <math>V</math> покрывается по крайней мере одним элементом из <math>M</math>.
'''Определение 2.''' Покрытие называется неприводимым, если при удалении любого его элемента данное покрытие перестает быть покрытием.

Пусть каждому элементу <math>e_j</math> из множества E приписан вес <math>p(e_j) > 0</math> . Весом покрытия называется число <math>P(M) = p(e_j)</math>. Задача нахождения покрытия минимального веса называется задачей о покрытии.
== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

1. Дюкова Е.В., Журавлев Ю.И., Сотнезов Р.М., Construction of an Ensemble of Logical Correctors of the Basis of Elementaty Classifiers

2. R.M. Sotnesov, "Genetic Algorithms in Problems of Discrete Optimisation and Recognition"

[[en:Description of algorithm properties and structure]]

Участник:Щекалев Алексей Андреевич/Поиск минимального покрытия булевой матрицы

2017-10-23T20:01:05Z

Щекалев Алексей Андреевич: Новая страница: «= Свойства и структура алгоритма = == Общее описание алгоритма == Работа посвящена исследо…»

= Свойства и структура алгоритма =
== Общее описание алгоритма ==

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

== Математическое описание алгоритма ==
Пусть <math>V = {v_1,v_2,...,v_m}, E = {e_1,e_2,...,e_n}</math> два конечных множества и <math>P (x, y)</math> некоторый предикат заданный на множестве <math>V \times E </math>. Обычно множество <math>E</math> – называют покрывающим, а множество <math>V</math> – покрываемым. Если <math>P (v_i,e_j) = 1</math>, то говорят, что <math>e_j</math> покрывает <math>v_i</math>, а <math>v_i</math> покрывается <math>e_j</math>. Пусть <math>M \subseteq E</math>. Обозначим через <math>\mu_M(v_i)</math> число всех элементов <math>e_i</math> из <math>M</math> , которые покрывают элемент <math>v_i</math>, т.е. <math>\mu_M(v_i) = |\{e_j \in M|P(v_i,e_j) = 1\}|</math>.

'''Определение 1.''' Множество <math>M</math> называется покрытием множества <math>V</math>, если <math>\forall v_i \in V: \mu_M(v_i) \ge 1</math> Другими словами каждый элемент множества <math>V</math> покрывается по крайней мере одним элементом из <math>M</math>.
'''Определение 2.''' Покрытие называется неприводимым, если при удалении любого его элемента данное покрытие перестает быть покрытием.

Пусть каждому элементу <math>e_j</math> из множества E приписан вес <math>p(e_j) > 0</math> . Весом покрытия называется число <math>P(M) = p(e_j)</math>. Задача нахождения покрытия минимального веса называется задачей о покрытии.
== Вычислительное ядро алгоритма ==
== Макроструктура алгоритма ==
== Схема реализации последовательного алгоритма ==
== Последовательная сложность алгоритма ==
== Информационный граф ==
== Ресурс параллелизма алгоритма ==
== Входные и выходные данные алгоритма ==
== Свойства алгоритма ==
= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
= Литература =

<references />

[[en:Description of algorithm properties and structure]]