Просмотр исходного текста страницы Теорема Радо-Эдмондса (жадный алгоритм)

== Теорема Радо-Эдмондса == 
{{Теорема
|about=
Радо-Эдмондса
|statement=
На носителе матроида <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Пусть <tex>A \in I</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k</tex>. Возьмем <tex>x: A \cup x \in I</tex>, <tex>x \notin A</tex>, <tex>\omega (x)</tex> {{---}} минимальна.
<br> Тогда <tex>A \cup x</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
|proof=
Рассмотрим <tex>B \in I</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>. 

Из определения матроида: <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.

Тогда верны два неравенства:
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) \geqslant \omega (B) \Rightarrow \omega (A) \geqslant \omega (B) - \omega (y)</tex>,
<br><tex>\omega (B \setminus y) = \omega (B) - \omega (y) \geqslant \omega (A)</tex>.

Заметим, что величина <tex>\omega (A)</tex> с двух сторон ограничивает величину <tex>\omega (B) - \omega (y)</tex>. Значит, эти величины равны: 
<tex>\omega (A) = \omega (B) - \omega (y) \Rightarrow \omega (A) + \omega (y) = \omega (B)</tex>.

Следовательно,
<tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>.

Таким образом получаем, что если объединить  множество <tex>A</tex> с <tex>x</tex> — минимальным из таких, что <tex>A \cup x \in I</tex>, — то получим множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
}}

== Жадный алгоритм поиска базы минимального веса ==
{{Теорема
|about=
жадный алгоритм поиска базы минимального веса
|statement=
Пусть на носителе матроида <tex>M = \langle X, I \rangle</tex> задана весовая функция <tex>\omega: X \to \mathbb R</tex>. Для любого <tex>A \subset X</tex> выполнено: <tex>\omega(A) = \sum\limits _{x \in A} \omega(x)</tex>. Тогда база минимального веса матроида <tex>M</tex> ищется жадно.
|proof=
Пусть <tex>n = |X|</tex>¸ а <tex>m</tex> — время, за которое выполняется проверка множества на независимость.

Псевдокод алгоритма:
 sort(X)    <span style="color:green">// сортируем элементы по возрастанию веса</span>
 <tex>B \leftarrow \varnothing</tex>
 '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n-1</tex>
   '''if''' <tex>B \cup X[i] \in I</tex>
     <tex>B \leftarrow B \cup X[i]</tex>
Рассмотрим шаг алгоритма, на котором мы пытаемся добавить элемент <tex>X[i]</tex>. Заметим, что если при его добавлении сохраняется независимость множества <tex>B</tex>, то это элемент минимального веса не из <tex>B</tex>. В самом деле, пусть <tex>X[j]</tex> — элемент минимального веса не из <tex>B</tex>, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.

Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.

Алгоритм работает за <tex>O(n \log n + mn)</tex>. На сортировку элементов из <tex>X</tex> по возрастанию весов уходит <tex>O(n \log n)</tex>. После чего, построение базы  выполняется <tex>O(n)</tex> шагов цикла, каждый из которых работает <tex>O(m)</tex> времени. Однако, если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>, асимптотика алгоритма будет <tex>O(n \log n)</tex>
}}

== Примеры ==

=== Графовый матроид ===
Типичным примером задачи, которая решается с помощью жадного алгоритма, является поиск остовного дерева. Остовное дерево — это база в графовом матроиде. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]

=== Матроид паросочетаний ===
Еще одной типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с трансверсальным матроидом. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| Алгоритма Куна]].

=== Матричный матроид ===
Последней задачей, которую мы рассмотрим, будет нахождение максимального количества линейно независимых строк в матрице. Рассмотрим матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — матроид. Задача решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss e-maxx:ru:Метод Гаусса]</ref> 

== См. также == 
* [[Теорема о базах]]
* [[Теорема Эдмондса-Лоулера]]

== Примечания == 
<references />

== Источники информации ==
* [[wikipedia:ru:Жадный алгоритм Радо — Эдмондса | Википедия — Жадный алгоритм Радо-Эдмондса]]
* [http://www.mathematik.hu-berlin.de/~wilhelm/greedy-vortrag.pdf| Greedy Algorithm And Edmonds Matroid Intersection Algorithm]
* [http://habrahabr.ru/post/120343/| Habrahabr:Жадные алгоритмы]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]