Теорема Радо-Эдмондса (жадный алгоритм) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Графовый матроид)
(не показано 19 промежуточных версий 6 участников)
Строка 1: Строка 1:
 +
== Теорема Радо-Эдмондса ==
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
 
Радо-Эдмондса
 
Радо-Эдмондса
 
|statement=
 
|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> - минимальна.
+
На носителе [[Определение матроида| матроида]] <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>.
+
<br> Тогда <tex>A \cup x</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
 
|proof=
 
|proof=
Рассмотрим <tex>B \in I</tex> - множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.  
+
Рассмотрим <tex>B \in I</tex> {{---}} множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.  
<br>Очевидно, что <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.
+
 
<br>Тогда верны два неравенства:
+
Из определения матроида: <tex>\exists y \in B\setminus A : A \cup y \in I</tex>.
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) \ge \omega (B) \Rightarrow \omega (A) \ge \omega (B) - \omega (y)</tex>
+
 
<br><tex>\omega (B \setminus y) = \omega (B) - \omega (y) \ge \omega (A)</tex>
+
Тогда верны два неравенства:
<br>Заметим, что величина <tex>\omega (A)</tex> с двух сторон ограничивает величину <tex>\omega (B) - \omega (y)</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 (A) = \omega (B) - \omega (y) \Rightarrow \omega (A) + \omega (y) = \omega (B)</tex>
+
<br><tex>\omega (B \setminus y) = \omega (B) - \omega (y) \geqslant \omega (A)</tex>.
<br>Следовательно
+
 
<br><tex>\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)</tex>
+
Заметим, что величина <tex>\omega (A)</tex> с двух сторон ограничивает величину <tex>\omega (B) - \omega (y)</tex>. Значит, эти величины равны:  
<br>Таким образом получаем, что если объединить  множество <tex>A</tex> с <tex>x</tex> - минимальным из таких, что <tex>A \cup x \in I</tex>, то получим множество минимального веса среди независимых подмножеств <tex>X</tex> мощности <tex>k + 1</tex>.
+
<tex>\omega (A) = \omega (B) - \omega (y) \Rightarrow \omega (A) + \omega (y) = \omega (B)</tex>.
<br>Теорема доказана.
+
 
 +
Следовательно,
 +
<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>
 +
}}
 +
 +
== Примеры ==
 +
 +
=== Графовый матроид ===
 +
Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это база в [[Примеры матроидов#.D0.93.D1.80.D0.B0.D1.84.D0.BE.D0.B2.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| графовом матроиде]]. Данная задача решается с помощью [[Алгоритм Краскала| алгоритма Краскала]]. Код данного алгоритма совпадает с псевдокодом алгоритма поиска базы минимального веса, который был приведен выше.
 +
 +
=== Матроид паросочетаний ===
 +
Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с [[Примеры матроидов#.D0.A2.D1.80.D0.B0.D0.BD.D1.81.D0.B2.D0.B5.D1.80.D1.81.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| трансверсальным матроидом]]. Решается эта задача с помощью [[Алгоритм Куна для поиска максимального паросочетания| алгоритма Куна]].
 +
 +
=== Матричный матроид ===
 +
Рассмотрим задачу о нахождении максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами <tex>[a_{ij}]</tex>. Пусть <tex>E</tex> — множество её строк, <tex>I</tex> — семейство множеств линейно независимых строк. Тогда <tex>M = \langle E, I \rangle</tex> — [[Примеры матроидов#.D0.9C.D0.B0.D1.82.D1.80.D0.B8.D1.87.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4| матричный матроид]]. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса<ref>[http://e-maxx.ru/algo/linear_systems_gauss MAXimal :: algo :: Метод Гаусса]</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 — Жадные алгоритмы]
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]
 +
[[Категория:Основные факты теории матроидов]]

Версия 19:39, 25 мая 2015

Теорема Радо-Эдмондса

Теорема (Радо-Эдмондса):
На носителе матроида [math]M = \langle X, I \rangle[/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Пусть [math]A \in I[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k[/math]. Возьмем [math]x: A \cup x \in I[/math], [math]x \notin A[/math], [math]\omega (x)[/math] — минимальна.
Тогда [math]A \cup x[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим [math]B \in I[/math] — множество минимального веса среди независимых подмножеств [math]X[/math] мощности [math]k + 1[/math].

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

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

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

Следовательно, [math]\omega (A \cup y) = \omega (A) + \omega (y) = \omega (B)[/math].

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

Жадный алгоритм поиска базы минимального веса

Теорема (жадный алгоритм поиска базы минимального веса):
Пусть на носителе матроида [math]M = \langle X, I \rangle[/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Для любого [math]A \subset X[/math] выполнено: [math]\omega(A) = \sum\limits _{x \in A} \omega(x)[/math]. Тогда база минимального веса матроида [math]M[/math] ищется жадно.
Доказательство:
[math]\triangleright[/math]

Пусть [math]n = |X|[/math]¸ а [math]m[/math] — время, за которое выполняется проверка множества на независимость.

Псевдокод алгоритма:

sort(X)    // сортируем элементы по возрастанию веса
[math]B \leftarrow \varnothing[/math]
for [math]i \leftarrow 0[/math] to [math]n-1[/math]
  if [math]B \cup X[i] \in I[/math]
    [math]B \leftarrow B \cup X[i][/math]

Рассмотрим шаг алгоритма, на котором мы пытаемся добавить элемент [math]X[i][/math]. Заметим, что если при его добавлении сохраняется независимость множества [math]B[/math], то это элемент минимального веса не из [math]B[/math]. В самом деле, пусть [math]X[j][/math] — элемент минимального веса не из [math]B[/math], который можно добавить к [math]B[/math] с сохранением его независимости, тогда [math]j\lt i[/math]. Но тогда он уже был бы добавлен на [math]j[/math]-ом шаге алгоритма.

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

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

Примеры

Графовый матроид

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

Матроид паросочетаний

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

Матричный матроид

Рассмотрим задачу о нахождении максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами [math][a_{ij}][/math]. Пусть [math]E[/math] — множество её строк, [math]I[/math] — семейство множеств линейно независимых строк. Тогда [math]M = \langle E, I \rangle[/math] матричный матроид. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса[1]

См. также

Примечания

Источники информации