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

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

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

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

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

Пусть [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) \gt 0[/math] . Весом покрытия называется число [math]P(M) = p(e_j)[/math]. Задача нахождения покрытия минимального веса называется задачей о покрытии.