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

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

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

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

Реализация

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\,\! — ранг матроида.

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Жадный алгоритм Рада — Эдмондса" в других словарях:

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


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»