Жадный алгоритм поиска базы минимального веса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 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