Жадібний алгоритм Радо-Едмондса

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Жадібний алгоритм Радо-Едмондса — алгоритм знаходження бази мінімальної ваги у матроїді.

Якщо кожному елементу носія матроїда зіставлена його вага, і вага підмножини носія визначається як сума ваг елементів цієї підмножини, то алгоритм Радо-Едмондса дозволяє знайти базу мінімальної ваги серед всіх баз матроїда.

Реалізація

[ред. | ред. код]

Нехай X — носій матроїда, І — сімейство незалежних множин. Для всіх i від 0 до рангу цього матроїду будується множина Аі ∈ I потужності i, вага якого є мінімальною серед ваг незалежних підмножин тієї ж потужності.

Очевидно,що А0  = ∅. Будуються ці множини так: Аi= Аi-1 + {x}, де x — мінімальний з елементів y ∈ X\Ai, таких що Aі ∪ {y} ∈ I.

Відповідь задачі — An , де n — ранг матроїду. Алгоритм Радо-Едмондса узагальнює жадібні алгоритми. Наприклад, у разі застосування для графічного матроїда, він перетворюється в алгоритм Крускала пошуку кістякового лісу мінімальної ваги.

Література

[ред. | ред. код]