Ahne Rado-Edmonds -algoritmi

Ahne Rado-Edmonds- algoritmi on algoritmi matroidipohjan minimipainon löytämiseksi .

Jos matroidin kantoaallon jokainen elementti liittyy sen painoon ja kantoaallon osajoukon paino määritellään tämän osajoukon elementtien painojen summaksi , niin Rado-Edmonds-algoritmi mahdollistaa kantajan löytämisen. vähimmäispaino matroidin kaikkien kannasten joukossa.

Toteutus

$X$ on tuki matroidille, on itsenäisten sarjojen perhe . $minä$

Kaikille matroid -luokille pisteestä järjestykseen muodostetaan kardinaalisuusjoukko , jonka paino on minimaalinen saman kardinaalisuuden riippumattomien osajoukkojen painojen joukossa. $i$ $0$ $A_{i}\in I$ $i$

$A_{0}=\varnothing$ - ilmeisesti.

Nämä joukot muodostetaan seuraavasti: , jossa on alkioiden vähimmäismäärä , jotta . $A_{i+1}=A_{i}+\left\{x\right\}$ $x$ ${\displaystyle y\in X\setminus A_{i))$ $A_{i}\cup \left\{y\right\}\in I$

Vastaus ongelmaan on , missä on matroidin sijoitus. $A_{n}$ $n$

Rado-Edmonds-algoritmi on yleistys ahneista algoritmeista . Esimerkiksi, kun sitä käytetään graafiseen matroidiin , siitä tulee Kruskalin algoritmi metsää kattavan vähimmäispainon löytämiseksi .

Kirjallisuus

R. Rado. Lause itsenäisyyssuhteista. Quart. J. Math., 13:83–89, 1942
Edmonds J. Matroidit ja ahneet algoritmit // Matemaattinen ohjelmointi. 1971. - s. 127-136. doi: 10.1007/BF01584082
Novikov F. A. Diskreetti matematiikka ohjelmoijille . - 3. painos - Pietari. : Peter, 2009. - S. 74-77. — 384 s. - ISBN 978-5-91180-759-7 . (Venäjän kieli)

Linkit

Luento 9. Matroidit , kurssi "Diskreetti matematiikka", Novosibirskin valtionyliopisto, 2009