Жадібний алгоритм Радо-Едмондса — алгоритм знаходження бази мінімальної ваги у матроїді.
Якщо кожному елементу носія матроїда зіставлена його вага, і вага підмножини носія визначається як сума ваг елементів цієї підмножини, то алгоритм Радо-Едмондса дозволяє знайти базу мінімальної ваги серед всіх баз матроїда.
Реалізація
Нехай 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, Інтернет
Zhadibnij algoritm Rado Edmondsa algoritm znahodzhennya bazi minimalnoyi vagi u matroyidi Yaksho kozhnomu elementu nosiya matroyida zistavlena jogo vaga i vaga pidmnozhini nosiya viznachayetsya yak suma vag elementiv ciyeyi pidmnozhini to algoritm Rado Edmondsa dozvolyaye znajti bazu minimalnoyi vagi sered vsih baz matroyida RealizaciyaNehaj X nosij matroyida I simejstvo nezalezhnih mnozhin Dlya vsih i vid 0 do rangu cogo matroyidu buduyetsya mnozhina Ai I potuzhnosti i vaga yakogo ye minimalnoyu sered vag nezalezhnih pidmnozhin tiyeyi zh potuzhnosti Ochevidno sho A0 Buduyutsya ci mnozhini tak Ai Ai 1 x de x minimalnij z elementiv y X Ai takih sho Ai y I Vidpovid zadachi An de n rang matroyidu Algoritm Rado Edmondsa uzagalnyuye zhadibni algoritmi Napriklad u razi zastosuvannya dlya grafichnogo matroyida vin peretvoryuyetsya v algoritm Kruskala poshuku kistyakovogo lisu minimalnoyi vagi LiteraturaR Rado A theorem on independence relations Quart J Math 13 83 89 1942 Edmonds J Matroids and the Greedy Algorithms 25 grudnya 2012 u Wayback Machine