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

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

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

Реалізація

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

Очевидно,що А₀ = ∅. Будуються ці множини так: А_i= А_i-1 + {x}, де x — мінімальний з елементів y ∈ X\A_i, таких що A_і ∪ {y} ∈ 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

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