12.Жадные алгоритмы и матроиды

E – конечное множество, w: E ® R₊

Для XÍ E w(X) = , IÍ B(E) , w(X) ® min (max) , XÎ I

Жадный алгоритм

1.Выбираем элемент x₁ максимального веса такой, что {x₁}Î I.

2.Выбираем элемент x₂Î E\{x₁} максимального веса такой, что {x₁,x₂} Î I

i.Выбираем элемент x_i Î E\{x₁,…,x_i-1} максимального веса такой, что

{x₁,x₂,…,x_i-1,x_i} Î I

Матроид – это пара (X,B), где X – конечное множество, а B – непустое множество его подмножеств (элементы B - базы), удовлетворяющая следующим условиям:

1.Никакая база не содержится в другой базе (аксиома максимальности);

2.Если B₁ и B₂ – базы, то для любого элемента bÎ B₁ элемент сÎ B₂ такой, что B₁\{b}È{c} – база.

Матроид – это пара (X,I), где X – конечное множество, а I – непустое множество его подмножеств (элементы I - независимые множества), удовлетворяющая следующим условиям:

1.Для любого I₁Î I и I₂Í I₁ I₂ Î I

2.Если I₁ и I₂ – независимые множества и |I₁| < |I₂|, то элемент сÎ I₂\I₁ такой, что I₁È{c} Î I

Пара (X,I), для которой выполняется аксиома 1) – система независимости

Примеры матроидов

1/(X,{X})

2.X – конечное множество векторов некотороговекторного пространства, B – максимальные линейно независимые системы векторов из X (базисы X).

3.X – множество ребер некоторого графа G,B – подмножества ребер, составляющих остовные деревья G.

Теорема. Жадный алгоритм, примененный к системе независимости (E,I), всегда находит оптимальное решение тогда и только тогда, когда (E,I) – матроид.