Теорема Радо-Эдмондса (жадный алгоритм) — различия между версиями
Firespace (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 8 промежуточных версий 4 участников) | |||
Строка 4: | Строка 4: | ||
Радо-Эдмондса | Радо-Эдмондса | ||
|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= | ||
Строка 29: | Строка 29: | ||
жадный алгоритм поиска базы минимального веса | жадный алгоритм поиска базы минимального веса | ||
|statement= | |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> ищется жадно. | + | Пусть на носителе матроида <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= | |proof= | ||
Пусть <tex>n = |X|</tex>¸ а <tex>m</tex> — время, за которое выполняется проверка множества на независимость. | Пусть <tex>n = |X|</tex>¸ а <tex>m</tex> — время, за которое выполняется проверка множества на независимость. | ||
Строка 49: | Строка 49: | ||
=== Графовый матроид === | === Графовый матроид === | ||
− | Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это [[ | + | Примером задачи, которая решается с помощью жадного алгоритма, является поиск [[Лемма о безопасном ребре| остовного дерева]]. Остовное дерево — это база в [[Примеры матроидов#.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> | |
== См. также == | == См. также == | ||
Строка 67: | Строка 67: | ||
* [[wikipedia:ru:Жадный алгоритм Радо — Эдмондса | Википедия — Жадный алгоритм Радо-Эдмондса]] | * [[wikipedia:ru:Жадный алгоритм Радо — Эдмондса | Википедия — Жадный алгоритм Радо-Эдмондса]] | ||
* [http://www.mathematik.hu-berlin.de/~wilhelm/greedy-vortrag.pdf| Greedy Algorithm And Edmonds Matroid Intersection Algorithm] | * [http://www.mathematik.hu-berlin.de/~wilhelm/greedy-vortrag.pdf| Greedy Algorithm And Edmonds Matroid Intersection Algorithm] | ||
− | * [http://habrahabr.ru/post/120343/| Habrahabr | + | * [http://habrahabr.ru/post/120343/| Habrahabr — Жадные алгоритмы] |
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
+ | [[Категория:Основные факты теории матроидов]] |
Текущая версия на 19:33, 4 сентября 2022
Теорема Радо-Эдмондса
Теорема (Радо-Эдмондса): |
На носителе матроида задана весовая функция . Пусть — множество минимального веса среди независимых подмножеств мощности . Возьмем , , — минимальна.
Тогда — множество минимального веса среди независимых подмножеств мощности . |
Доказательство: |
Рассмотрим — множество минимального веса среди независимых подмножеств мощности .Из определения матроида: .Тогда верны два неравенства:
Заметим, что величина с двух сторон ограничивает величину . Значит, эти величины равны: .Следовательно, Таким образом получаем, что если объединить множество . с — минимальным из таких, что , — то получим множество минимального веса среди независимых подмножеств мощности . |
Жадный алгоритм поиска базы минимального веса
Теорема (жадный алгоритм поиска базы минимального веса): |
Пусть на носителе матроида база минимального веса матроида ищется жадно. задана весовая функция . Для любого выполнено: . Тогда |
Доказательство: |
Пусть ¸ а — время, за которое выполняется проверка множества на независимость.Псевдокод алгоритма: sort(X) // сортируем элементы по возрастанию веса for to if Рассмотрим шаг алгоритма, на котором мы пытаемся добавить элемент . Заметим, что если при его добавлении сохраняется независимость множества , то это элемент минимального веса не из . В самом деле, пусть — элемент минимального веса не из , который можно добавить к с сохранением его независимости, тогда . Но тогда он уже был бы добавлен на -ом шаге алгоритма.Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из так, чтобы после каждого добавления множество оставалось независимым. Алгоритм работает за . На сортировку элементов из по возрастанию весов уходит . После чего, построение базы выполняется шагов цикла, каждый из которых работает времени. Однако, если считать, что проверка множества на независимость происходит за , асимптотика алгоритма будет |
Примеры
Графовый матроид
Примером задачи, которая решается с помощью жадного алгоритма, является поиск остовного дерева. Остовное дерево — это база в графовом матроиде. Данная задача решается с помощью алгоритма Краскала. Код данного алгоритма совпадает с псевдокодом алгоритма поиска базы минимального веса, который был приведен выше.
Матроид паросочетаний
Типичной задачей из этого класса, является поиск наибольшего паросочетания в двудольном графе. Здесь мы имеем дело с трансверсальным матроидом. Решается эта задача с помощью алгоритма Куна.
Матричный матроид
Рассмотрим задачу о нахождении максимального количества линейно независимых строк в матрице. Возьмем матрицу с действительными кэффициентами матричный матроид. Данная задача, как и задача о решении системы линейных алгебраических уравнений, решается с помощью метода Гаусса[1]
. Пусть — множество её строк, — семейство множеств линейно независимых строк. Тогда —