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

Текущая версия на 20:07, 17 июня 2014

Перенаправление на:

@@ Строка 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>
-}}