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

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

1.2 Математическое описание алгоритма

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

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

Пусть каждому элементу $e_j$ из множества E приписан вес $p(e_j) \gt 0$ . Весом покрытия называется число $P(M) = p(e_j)$. Задача нахождения покрытия минимального веса называется задачей о покрытии.