Fiduccia-Mattheyses algoritmi - Fiduccia–Mattheyses algorithm - Wikipedia
 | Ushbu maqola bo'lishi kerak bo'lishi mumkin qayta yozilgan Vikipediyaga mos kelish sifat standartlari. (2015 yil yanvar) |
Hal qilish uchun klassik yondashuv Gipergraf ikkiga bo'linish muammosi - Charlz Fiduccia va Robert Mattheyses tomonidan takrorlanadigan evristik.[1] Ushbu evristik odatda FM algoritmi deb nomlanadi.
Kirish
FM algoritmi - bu tarmoq bo'limlarini takomillashtirish uchun chiziqli vaqt evristikasi K-L evristikasi:
- Sof kesilgan xarajatlarni kamaytirishga qaratilgan; qisqartirish tushunchasi gipergrafalarga qadar kengaytirilgan.
- Faqat bitta tepalik bitta harakat bilan kesma bo'ylab harakatlanadi.
- Vertices vaznga ega.
- "Balanssiz" bo'limlarni boshqarishi mumkin; balans koeffitsienti joriy etiladi.
- Ish vaqtini yaxshilash uchun kesma bo'ylab harakatlanadigan tepaliklarni tanlash uchun maxsus ma'lumotlar tuzilishi ishlatiladi.
- Vaqtning murakkabligi O(P), qaerda P terminallarning umumiy soni #.
FM namunasi
F-M evristik: yozuv
Kirish: tepasi (katakcha) to'plami va giperedge (to'ri) to'plami bo'lgan gipergraf
- n (i): Net i-dagi # katak; Masalan, n (1) = 4
- s (i): i katakchaning kattaligi
- p (i): # hujayra pinlari; masalan, p (1) = 4
- C: kataklarning umumiy soni #; masalan, C = 13
- N: jami # to'r; masalan, N = 4
- P: pinlarning jami #; P = p (1) +… + p (C) = n (1) +… + n (N)
- Maydon nisbati r, 0
Chiqish: 2 qism
- Cutsetsize minimallashtirilgan
- | A | / (| A | + | B |) ≈ r
Shuningdek qarang
Adabiyotlar
- ^ Fiduccia; Mattheyses (1982). "Tarmoq bo'limlarini yaxshilash uchun chiziqli vaqt evristikasi" (PDF). 19-dizayn avtomatlashtirish konferentsiyasi. Olingan 23 oktyabr 2013.