|
|
| Строка 1: |
Строка 1: |
| − | {{Теорема
| + | #REDIRECT [[Теорема Радо-Эдмондса (жадный алгоритм)]] |
| − | |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>sort(X)</tex> // сортируем элементы по возрастанию веса
| |
| − | <tex>B \leftarrow \varnothing</tex>
| |
| − | '''for''' <tex>i \leftarrow 0</tex> '''to''' <tex>|X|-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(|X| \log(|X|))</tex>. На сортировку элементов из <tex>X</tex> по возрастанию весов уходит <tex>O(|X| \log(|X|))</tex> и <tex>O(|X|)</tex> шагов цикла, каждый из которых работает <tex>O(1)</tex> времени (если считать, что проверка множества на независимость происходит за <tex>O(1)</tex>).
| |
| − | }}
| |
| − | | |
| − | | |
| − | [[Категория:Алгоритмы и структуры данных]]
| |
| − | [[Категория:Матроиды]]
| |
