Cuthill-Mackey-algoritmi

Cuthill - McKee algoritmi on nauhan pienennysalgoritmi harvoille symmetrisille matriiseille _ Nimetty kehittäjien Elizabeth Cuthillin ja James McKeen mukaan.

Reverse Cuthill-McKee ( RCM , käänteinen Cuthill-McKee ) on sama algoritmi käänteisellä indeksinumeroilla.

Algoritmi

Alkuperäistä symmetristä matriisia käsitellään graafin vierekkäisyysmatriisina . Cuthill-McKee-algoritmi numeroi graafin kärjet uudelleen siten, että alkuperäisen matriisin sarakkeiden ja rivien vastaavan permutoinnin seurauksena sen nauhan leveys pienenee . $n\ kertaa n$ $(V, E)$

Algoritmi rakentaa järjestetyn joukon pisteitä, jotka edustavat uutta kärkiluetteloa. Yhdistetylle kaaviolle algoritmi näyttää tältä: $R$

valitse perifeerinen kärki (tai pseudo-perifeerinen kärki ) monikon alkuarvoksi ; $v$ $R:=(v)$
, kun ehto täyttyy , suorita vaiheet 3-5: $i=1,2,...$ $|R|<n$
rakentaa viereisyysjoukko , jossa on -th komponentti , ja sulkea pois kärjet, jotka jo sisältyvät , eli: ; $\operaattorin nimi {Adj} (R_{i})$ $R_i$ $R_i$ $i$ $R$ $R$ $A_{i}:=\operaattorin nimi {Adj} (R_{i})\setminus R$
lajitella kärkiasteiden nousevaan järjestykseen ; $A_{i}$
lisää tulokseen monikko . $A_{i}$ $R$

Toisin sanoen, algoritmi luettelee kärjet leveysensimmäisessä haussa , jossa vierekkäiset kärjet kulkevat niiden potenssien kasvavassa järjestyksessä .

Kytkemättömälle graafille algoritmia voidaan soveltaa erikseen jokaiseen yhdistettyyn komponenttiin [1] .

RCM-algoritmin aikalaskennan monimutkaisuus edellyttäen, että järjestykseen käytetään lisäyslajittelua , missä on kärjen maksimiaste, on graafin reunojen lukumäärä [2] . $O(m|E|)$ $m$ $|E|$

Aloituspisteen valinta

Hyvien tulosten saamiseksi sinun on löydettävä graafin reunapiste . Tämä tehtävä on yleensä melko vaikea, joten sen sijaan he yleensä etsivät pseudo-perifeeristä kärkeä käyttämällä yhtä Gibbsin et al. heuristisen algoritmin modifikaatioista. $(V, E)$

Algoritmin kuvaamiseksi otetaan käyttöön juuretun tason rakenteen käsite . Tietylle pisteelle tasorakenne, jonka juuret ovat pistejoukon osio : $v$ $v$ $\mathcal{L}$ $V$

{\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\},

jossa osajoukot määritellään seuraavasti: $L_{i}(v)$

L_{0}(v)=\{v\},

L_{1}(v)=\operaattorin nimi {Adj} (L_{0}(v))

L_{i}(v)=\operaattorinimi {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots ,l (v).

Algoritmi näennäisen reunapisteen löytämiseksi [3] :

valitse mielivaltainen kärki ; $r$ $V$
rakentaa tasorakenne juurille : ; $r$ ${\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots ,L_{l(r)}(r)\}$
valitse huippupiste, jolla on pienin aste ; $v$ $L_{l(r)}(r)$
rakentaa tasorakenne juurille : ; $v$ ${\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\}$
jos , määritä ja siirry vaiheeseen 3; $l(v)>l(r)$ $r:=v$
kärki on haluttu pseudo-perifeerinen kärki. $v$

Muistiinpanot

↑ George, Liu, 1984 , s. 65-66.
↑ George, Liu, 1984 , s. 68.
↑ George, Liu, 1984 , s. 70-72.

Kirjallisuus

E. Cuthill ja J. McKee. Harvaiden symmetristen matriisien kaistanleveyden vähentäminen Proc. 24. Nat. Conf. ACM , sivut 157-172, 1969.
George A., Liu J. Suurien harvaan positiivisten määrällisten järjestelmien tietokoneratkaisu. - M .: Mir, 1984. - 333 s.

Linkit

Boost C++ -kirjastojen Cuthill-McKee-algoritmin dokumentaatio .
Yksityiskohtainen selitys Cuthill-McKee-algoritmista .
Yksityiskohtainen selitys Cuthill-McKee-algoritmista (venäjäksi) (pääsemätön linkki) .
Cuthill-McKee-algoritmin toteutus Pythonissa (linkki ei saatavilla) .