Жадібний алгоритм Радо-Едмондса — алгоритм знаходження бази мінімальної ваги у матроїді.
Якщо кожному елементу носія матроїда зіставлена його вага, і вага підмножини носія визначається як сума ваг елементів цієї підмножини, то алгоритм Радо-Едмондса дозволяє знайти базу мінімальної ваги серед всіх баз матроїда.
Реалізація
Нехай X — носій матроїда, І — сімейство незалежних множин. Для всіх i від 0 до рангу цього матроїду будується множина Аі ∈ I потужності i, вага якого є мінімальною серед ваг незалежних підмножин тієї ж потужності.
Очевидно,що А0 = ∅. Будуються ці множини так: Аi= Аi-1 + {x}, де x — мінімальний з елементів y ∈ X\Ai, таких що Aі ∪ {y} ∈ I.
Відповідь задачі — An , де n — ранг матроїду. Алгоритм Радо-Едмондса узагальнює жадібні алгоритми. Наприклад, у разі застосування для графічного матроїда, він перетворюється в алгоритм Крускала пошуку кістякового лісу мінімальної ваги.
Література
- R. Rado. A theorem on independence relations. Quart. J. Math., 13:83–89, 1942
- Edmonds J. Matroids and the Greedy Algorithms [ 25 грудня 2012 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет