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

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

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

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

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

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

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

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