34
правки
Изменения
Нет описания правки
== Жадный алгоритм поиска базы минимального веса ==
{{Теорема
|about=
Пусть на носителе матроида <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>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
Алгоритм работает за <tex>O(m \cdot n \log n)</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>
}}
== Примеры задач ==
* [http://informatics.mccme.ru/mod/statements/view.php?id=3580| informatics:mccme:ru:Остовное дерево]
== См. также ==
* [[Теорема о базах]]
* [[Теорема Эдмондса-Лоулера]]
== Источники информации ==
* [http://www.mathematik.hu-berlin.de/~wilhelm/greedy-vortrag.pdf| Greedy Algorithm And Edmonds Matroid Intersection Algorithm]
* [http://habrahabr.ru/post/120343/| Habrahabr:Жадные алгоритмы]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
