Жадный алгоритм поиска базы минимального веса — различия между версиями
Leugenea (обсуждение | вклад) |
Leugenea (обсуждение | вклад) |
||
Строка 10: | Строка 10: | ||
<tex>y \leftarrow ArgOf(\min\limits _{x \notin B: B \cup x \in I} \omega(x))</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>B \leftarrow B \cup y</tex> | ||
+ | |||
+ | По [[Теорема о базах|теореме о базах]] все базы имеют одинаковую мощность. По [[Теорема Радо-Эдмондса (жадный алгоритм)|теореме Радо-Эдмондса]] множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов из <tex>X</tex> так, чтобы после каждого добавления множество оставалось независимым. | ||
}} | }} |
Версия 23:47, 15 мая 2011
Теорема (жадный алгоритм поиска базы минимального веса): |
Пусть на носителе матроида задана весовая функция . Для любого выполнено: . Тогда база минимального веса матроида ищется жадно. |
Доказательство: |
Псевдокод алгоритма: По while ( ): теореме о базах все базы имеют одинаковую мощность. По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов из так, чтобы после каждого добавления множество оставалось независимым. |