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

Статья может быть слишком трудной для понимания большинством читателей.
Пожалуйста, не жертвуя подробностью, приведите её к более доступному для неспециалистов виду.

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

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

Реализация

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

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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home