Algoritmus Cuthill – McKee - Cuthill–McKee algorithm

Cuthill-McKee uspořádání matice

RCM řazení stejné matice

v numerická lineární algebra, Algoritmus Cuthill – McKee (CM), pojmenovaný pro Elizabeth Cuthill a James^[1] McKee,^[2] je algoritmus permutovat a řídká matice který má symetrický řídký vzor do a pásmová matice formulář s malým šířka pásma. The obrácený algoritmus Cuthill – McKee (RCM) kvůli Alanu Georgovi je stejný algoritmus, ale výsledná čísla indexů jsou obrácená.^[3] V praxi to obvykle vede k méně vyplnit než uspořádání CM, když je použita Gaussova eliminace.^[4]

Algoritmus Cuthill McKee je variantou standardu vyhledávání na šířku algoritmus používaný v grafových algoritmech. Začíná to periferním uzlem a poté se generuje úrovně ${ displaystyle R_ {i}}$ pro ${ displaystyle i = 1,2, ..}$ dokud nejsou vyčerpány všechny uzly. Sada ${ displaystyle R_ {i + 1}}$ je vytvořen ze sady ${ displaystyle R_ {i}}$vypsáním všech vrcholů sousedících se všemi uzly v ${ displaystyle R_ {i}}$. Tyto uzly jsou seřazeny podle předchůdců a stupně.

Algoritmus

Vzhledem k tomu, symetrický ${ displaystyle n krát n}$ matici vizualizujeme matici jako matice sousedství a graf. Algoritmus Cuthill – McKee je potom přetvářením vrcholy grafu ke snížení šířky pásma matice sousedství.

Algoritmus vytváří uspořádaný n-tuple ${ displaystyle R}$ vrcholů, což je nové pořadí vrcholů.

Nejprve zvolíme a periferní vrchol (vrchol s nejnižším stupeň ) ${ displaystyle x}$ a nastavit ${ displaystyle R: = ( {x })}$.

Pak pro ${ displaystyle i = 1,2, tečky}$ následující kroky opakujeme ${ displaystyle | R |$

• Vytvořte sadu sousedství ${ displaystyle A_ {i}}$ z ${ displaystyle R_ {i}}$ (s ${ displaystyle R_ {i}}$ the i-tá složka ${ displaystyle R}$) a vyloučit vrcholy, které již máme v ${ displaystyle R}$

${ displaystyle A_ {i}: = operatorname {Adj} (R_ {i}) setminus R}$

• Třídit ${ displaystyle A_ {i}}$ vzestupně minimálním předchůdcem (již navštívený soused s nejčasnější pozicí v R) a jako tiebreak vzestupně stupeň vrcholu.^[5]
• Připojit ${ displaystyle A_ {i}}$ do sady výsledků ${ displaystyle R}$.

Jinými slovy, číslujte vrcholy podle konkrétního struktura úrovně (vypočítá vyhledávání na šířku ) kde jsou vrcholy v každé úrovni navštěvovány v pořadí podle číslování jejich předchůdců od nejnižší po nejvyšší. Pokud jsou předchůdci stejní, vrcholy se rozlišují podle stupně (opět seřazené od nejnižšího po nejvyšší).

Viz také

• Šířka pásma grafu
• Řídká matice

Reference

• Dokumentace Cuthill – McKee pro Zvyšte knihovny C ++.
• Podrobný popis algoritmu Cuthill – McKee.
• symrcm Implementace RCM ze strany MATLABu.
• reverse_cuthill_mckee RCM rutina z SciPy napsáno v Cython.