WikiDer > Kutill-McKee algoritmi

Kutill-Makki matritsasini buyurtma qilish

Xuddi shu matritsaning RCM buyurtmasi

Yilda raqamli chiziqli algebra, Kutill-McKee algoritmi (SM), Elizabeth Kutill va Jeyms uchun nomlangan^[1] Makki,^[2] bu algoritm buzmoq siyrak matritsa bu bor nosimmetrik siyraklik shakli tarmoqli matritsasi kichik bilan shakl tarmoqli kengligi. The teskari Kutill-McKee algoritmi (RCM) Alan Jorj tufayli bir xil algoritm mavjud, ammo natijada indeks raqamlari teskari.^[3] Amalda bu odatda kamroq natijalarga olib keladi to'ldirish Gauss eliminatsiyasi qo'llanilganda CM buyurtmasiga qaraganda.^[4]

Cuthill McKee algoritmi standartning bir variantidir kenglik bo'yicha birinchi qidiruvgrafik algoritmlarida ishlatiladigan algoritm. U periferik tugundan boshlanadi va keyin paydo bo'ladi darajalar ${ displaystyle R_ {i}}$ uchun ${ displaystyle i = 1,2, ..}$ barcha tugunlar tugamaguncha. To'plam ${ displaystyle R_ {i + 1}}$ to'plamdan yaratilgan ${ displaystyle R_ {i}}$barcha tugunlarga ulashgan barcha tepaliklarni ro'yxatlash orqali ${ displaystyle R_ {i}}$. Ushbu tugunlar avvalgilariga va darajasiga qarab tartiblangan.

Algoritm

Nosimmetrik berilgan ${ displaystyle n times n}$ matritsa biz matritsani qo'shni matritsa a grafik. Keyinchalik Cuthill-McKee algoritmi - ning qayta nomlanishi tepaliklar qo'shni matritsaning o'tkazuvchanligini kamaytirish uchun grafikaning.

Algoritm buyurtma beradi n- juftlik ${ displaystyle R}$ tepaliklarning yangi tartibi bo'lgan tepaliklar.

Avval biz a ni tanlaymiz periferik vertex (eng pasti bilan tepalik daraja) ${ displaystyle x}$ va sozlang ${ displaystyle R: = ( {x })}$.

Keyin uchun ${ displaystyle i = 1,2, dots}$ biz quyidagi bosqichlarni takrorlaymiz ${ displaystyle | R |$

• Qo'shni to'plamni tuzing ${ displaystyle A_ {i}}$ ning ${ displaystyle R_ {i}}$ (bilan ${ displaystyle R_ {i}}$ The men- ning tarkibiy qismi ${ displaystyle R}$) va allaqachon mavjud bo'lgan tepaliklarni chiqarib tashlang ${ displaystyle R}$

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

• Saralash ${ displaystyle A_ {i}}$ minimal salafiy tomonidan ko'tarilish (R da eng qadimgi mavqega ega bo'lgan allaqachon tashrif buyurgan qo'shni) va tirbandlik sifatida ko'tarilish tepalik darajasi.^[5]
• Qo'shish ${ displaystyle A_ {i}}$ Natija to'plamiga ${ displaystyle R}$.

Boshqacha qilib aytganda, tepaliklarni ma'lum bir narsaga qarab raqamlang darajadagi tuzilish (tomonidan hisoblab chiqilgan kenglik bo'yicha birinchi qidiruv) bu erda har bir darajadagi tepaliklar oldingilarining raqamlarini pastdan balandgacha tartibida tashrif buyuriladi. Oldingilar bir xil bo'lgan joyda, tepaliklar daraja bo'yicha ajralib turadi (yana pastdan balandgacha tartiblangan).

Shuningdek qarang

• Grafik o'tkazuvchanligi
• Matritsa siyrak

Adabiyotlar

• Cuthill-McKee hujjatlari uchun C ++ kutubxonalarini kuchaytirish.
• Kutil-Makki algoritmining batafsil tavsifi.
• simrcm MATLAB tomonidan RCMni amalga oshirish.
• teskari_cuthill_mckee RCM muntazamligi SciPy yozilgan Cython.