Меню Главная Случайная статья Настройки Жадный алгоритм Радо — Эдмондса Материал из https://ru.wikipedia.org Жадный алгоритм Радо — Эдмондса — алгоритм нахождения в матроиде базы минимального веса. Если каждому элементу носителя матроида сопоставлен его вес, и вес подмножества носителя определяется как сумма весов элементов этого подмножества, то алгоритм Радо — Эдмондса позволяет найти среди всех баз матроида базу минимального веса. Реализация ${\displaystyle X}$— носитель матроида, ${\displaystyle I}$ — семейство независимых множеств. Для всех ${\displaystyle i}$ от ${\displaystyle 0}$ до ранга матроида строится множество ${\displaystyle A_{i}\in I}$ мощности ${\displaystyle i}$, вес которого является минимальным среди весов независимых подмножеств той же мощности. ${\displaystyle A_{0}=\varnothing }$ — очевидно. Строятся эти множества так: ${\displaystyle A_{i+1}=A_{i}+\left\{x\right\}}$, где ${\displaystyle x}$ — минимальный из элементов ${\displaystyle y\in X\setminus A_{i}}$ таких, что ${\displaystyle A_{i}\cup \left\{y\right\}\in I}$. Ответ задачи — ${\displaystyle A_{n}}$, где ${\displaystyle 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 Новиков Ф. А. Дискретная математика для программистов (рус.). — 3-е изд. — СПб.: Питер, 2009. — С. 74-77. — 384 с. — ISBN 978-5-91180-759-7. Ссылки Лекция 9. Матроиды, Курс "Дискретная математика", Новосибирский государственный университет, 2009