WikiSort.ru - Не сортированное

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

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

Реализация

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

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

${\displaystyle A_{0}=\varnothing }$  — очевидно.

Строятся эти множества так: ${\displaystyle A_{i}=A_{i-1}+\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
• Ф. А. Новиков, "Дискретная математика для программистов", 2000 - стр. 74-77

Ссылки

• В.Е. Алексеев, В.А. Таланов, Графы и алгоритмы // Intuit, 2006 - ISBN 5-9556-0066-3. 14. Лекция: Жадные алгоритмы и матроиды. Теорема Радо-Эдмондса.
• Лекция 9. Матроиды, Курс "Дискретная математика", Новосибирский государственный университет, 2009

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