Изменения
Перейти к:
навигация
,
поиск
← Предыдущая правка
Жадный алгоритм поиска базы минимального веса
685 байт убрано
,
20:07, 17 июня 2014
Перенаправление на
Теорема Радо-Эдмондса (жадный алгоритм)
{{
#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>
}}
]]
Firespace
34
правки
Навигация
Персональные инструменты
Создать учётную запись
Войти
Пространства имён
Статья
Обсуждение
Варианты
Просмотры
Читать
Просмотр вики-текста
История
Ещё
Поиск
Навигация
Заглавная страница
Свежие правки
Случайная статья
Справка
Инструменты
Спецстраницы
Версия для печати