Жадный алгоритм Радо

Жа́дный алгори́тм Ра́до—Э́дмондса — алгоритм нахождения в матроиде базы минимального веса.

Если каждому элементу носителя матроида сопоставлен его вес, и вес подмножества носителя определяется как сумма весов элементов этого подмножества, то алгоритм Радо—Эдмондса позволяет найти среди всех баз матроида базу минимального веса.

Реализация

$X\,\!$ — носитель матроида, $I\,\!$ — семейство независимых множеств.

Для всех $i\,\!$ от $0\,\!$ до ранга матроида строится множество $A_i \in I\,\!$ мощности $i\,\!$, вес которого является минимальным среди весов независимых подмножеств той же мощности.

$A_0 = \varnothing \,\!$ — очевидно.

Строятся эти множества так: $A_i=A_{i-1}+\left\{x\right\}\,\!$, где $x\,\!$ — минимальный из элементов $y \in X \setminus A_i\,\!$ таких, что $A_i \cup \left\{y\right\} \in I\,\!$.

Ответ задачи — $A_n\,\!$, где $n\,\!$ — ранг матроида.

Алгоритм Радо—Эдмондса обобщает жадные алгоритмы. Например, будучи применённым к графическому матроиду, он превращается в алгоритм Краскала поиска остовного леса минимального веса.

Литература

• R. Rado. A theorem on independence relations. Quart. J. Math., 13:83–89, 1942
• Edmonds J. Matroids and the Greedy Algorithms // Math Programming . 1971. - P.127-136. doi:10.1007/BF01584082

Ссылки

• В.Е. Алексеев, В.А. Таланов, Графы и алгоритмы // Intuit, 2006 - ISBN 5-9556-0066-3. 14. Лекция: Жадные алгоритмы и матроиды. Теорема Радо-Эдмондса.
• www.math.nsc.ru/LBRT/k5/DM/lec9.pdf

Для улучшения этой статьи по математике желательно?: Проставив сноски, внести более точные указания на источники. Проставить интервики в рамках проекта Интервики.