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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Реализация[править | править код]

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

Для всех от до ранга матроида строится множество мощности , вес которого является минимальным среди весов независимых подмножеств той же мощности.

 — очевидно.

Строятся эти множества так: , где  — минимальный из элементов таких, что .

Ответ задачи — , где  — ранг матроида.

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

Литература[править | править код]

  • 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

Ссылки[править | править код]