Girig Rado-Edmonds algoritm

Den giriga Rado-Edmonds- algoritmen är en algoritm för att hitta minimivikten i en matroidbas .

Om varje element i bäraren för en matroid är associerad med dess vikt, och vikten av en delmängd av bäraren definieras som summan av vikterna av elementen i denna undermängd , tillåter Rado-Edmonds-algoritmen att hitta basen för minimivikten bland alla baser i matroiden.

Implementering

$X$ är stöd för matroid, är familjen av oberoende uppsättningar . $jag$

För alla matroidranger från till rang konstrueras en uppsättning kardinalitet vars vikt är minimal bland vikterna av oberoende delmängder av samma kardinalitet. $i$ $0$ $A_{i}\in I$ $i$

$A_{0}=\varnothing$ - självklart.

Dessa uppsättningar är konstruerade enligt följande: , där är ett minimum av element så att . $A_{i+1}=A_{i}+\left\{x\right\}$ $x$ ${\displaystyle y\in X\setminus A_{i))$ $A_{i}\cup \left\{y\right\}\in I$

Svaret på problemet är , var är matroidens rang. $En}$ $n$

Rado-Edmonds-algoritmen är en generalisering av giriga algoritmer . Till exempel, när den appliceras på en grafisk matroid , blir den Kruskals algoritm för att hitta en minimivikt som spänner över skog .

Litteratur

R. Rado. Ett teorem om oberoende relationer. Quart. J. Math., 13:83–89, 1942
Edmonds J. Matroids and the Greedy Algorithms // Matematikprogrammering. 1971. - S. 127-136. doi:10.1007/BF01584082
Novikov F. A. Diskret matematik för programmerare . - 3:e uppl. - St Petersburg. : Peter, 2009. - S. 74-77. — 384 sid. - ISBN 978-5-91180-759-7 . (ryska)

Länkar

Föreläsning 9. Matroider , Kurs "Diskret matematik", Novosibirsk State University, 2009