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

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

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

Реализация

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

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

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

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

Ссылки

Лекция 9. Матроиды, Курс "Дискретная математика", Новосибирский государственный университет, 2009

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.