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

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

Теорема (жадный алгоритм поиска базы минимального веса):
Пусть на носителе матроида [math]M = \lt X, I\gt [/math] задана весовая функция [math]\omega: X \to \mathbb R[/math]. Для любого [math]A \subset X[/math] выполнено: [math]\omega(A) = \sum\limits _{x \in A} \omega(x)[/math]. Тогда база минимального веса матроида [math]M[/math] ищется жадно.
Доказательство:
[math]\triangleright[/math]

Псевдокод алгоритма:

[math]B \leftarrow \emptyset[/math]
while ([math]\exists x \notin B: B \cup x \in I[/math]):
  [math]y \leftarrow ArgOf(\min\limits _{x \notin B: B \cup x \in I} \omega(x))[/math]
  [math]B \leftarrow B \cup y[/math]
По теореме о базах все базы имеют одинаковую мощность. По теореме Радо-Эдмондса множество минимального веса, имеющее мощность базы, (то есть база минимального веса) ищется последовательным добавлением в изначально пустое множество элементов из [math]X[/math] так, чтобы после каждого добавления множество оставалось независимым.
[math]\triangleleft[/math]