Материал из Викиконспекты
|
|
| (не показано 11 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | {{Теорема
| + | #REDIRECT [[Теорема Радо-Эдмондса (жадный алгоритм)]] |
| − | |about=
| |
| − | жадный алгоритм поиска базы минимального веса
| |
| − | |statement=
| |
| − | Пусть на носителе матроида <tex>M = <X, I></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>B \leftarrow \emptyset</tex>
| |
| − | '''while''' (<tex>\exists x \notin B: B \cup x \in I</tex>):
| |
| − | <tex>y \leftarrow ArgOf(\min\limits _{x \notin B: B \cup x \in I} \omega(x))</tex>
| |
| − | <tex>B \leftarrow B \cup y</tex>
| |
| − | Понятно, что все базы имеют одинаковую мощность (иначе в меньшую можно было бы добавить элемент из большей по аксиоме матроидов, что противоречит определению базы). По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым.
| |
| − | }}
| |
Текущая версия на 20:07, 17 июня 2014
