- Жадный алгоритм Рада — Эдмондса
-
Жа́дный алгори́тм Ра́до—Э́дмондса — алгоритм нахождения в матроиде базы минимального веса.
Если каждому элементу носителя матроида сопоставлен его вес, и вес подмножества носителя определяется как сумма весов элементов этого подмножества, то алгоритм Радо—Эдмондса позволяет найти среди всех баз матроида базу минимального веса.
Реализация
— носитель матроида,
— семейство независимых множеств.
Для всех
от
до ранга матроида строится множество
мощности
, вес которого является минимальным среди весов независимых подмножеств той же мощности.
— очевидно.
Строятся эти множества так:
, где
— минимальный из элементов
таких, что
.
Ответ задачи —
, где
— ранг матроида.
Алгоритм Радо—Эдмондса обобщает жадные алгоритмы. Например, будучи применённым к графическому матроиду, он превращается в алгоритм Краскала поиска остовного леса минимального веса.
Wikimedia Foundation. 2010.