34
правки
Изменения
Нет описания правки
sort(X) <span style="color:green">// сортируем элементы по возрастанию веса</span>
<tex>B \leftarrow \varnothing</tex>
'''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>n-1</tex> '''do'''
'''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>B</tex> при добавлении). В самом деле, пусть <tex>X[j]</tex> — элемент минимального веса не из <tex>B</tex>, который можно добавить к <tex>B</tex> с сохранением его независимости, тогда <tex>j<i</tex>. Но тогда он уже был бы добавлен на <tex>j</tex>-ом шаге алгоритма.
Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов минимального веса из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
Алгоритм работает за <tex>O(m n \cdot 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>
}}
== Примеры Простейшие примеры задач ==
* [http://informatics.mccme.ru/mod/statements/view.php?id=3580| informatics:mccme:ru:Остовное дерево]
