Фидучиа-Маттейз алгоритмі - Fiduccia–Mattheyses algorithm - Wikipedia
 | Бұл мақала қажет болуы мүмкін қайта жазылған Уикипедияға сай болу сапа стандарттары. (Қаңтар 2015) |
Шешуге арналған классикалық тәсіл Гипограф екіге бөліну проблемасы - Чарльз Фидучиа мен Роберт Маттейзестің қайталанатын эвристикасы.[1] Бұл эвристикалық фм алгоритмі деп аталады.
Кіріспе
FM алгоритмі - бұл желілік бөлімдерді жақсартуға арналған сызықтық уақыт эвристикасы K-L эвристикалық:
- Таза шығындарды азайтуға бағытталған; қысқарту ұғымы гиперграфтарға дейін кеңейтілген.
- Тек қана бір шың бір кескін бойынша кесінді бойымен қозғалады.
- Тік өлшенген.
- «Теңгерімсіз» бөлімдерді басқара алады; баланс коэффициенті енгізіледі.
- Арнайы деректер құрылымы жұмыс уақытын жақсарту үшін кесінді бойынша жылжытылатын шыңдарды таңдау үшін қолданылады.
- Уақыттың күрделілігі O(P), қайда P терминалдардың жалпы саны #.
ФМ мысалы
F – M эвристикалық: белгілеу
Кіріс: шыңы (ұяшық) және гипереджи (тор) жиыны бар гиперграф
- n (i): # тордағы i ұяшықтар; мысалы, n (1) = 4
- s (i): i ұяшығының өлшемі
- p (i): i ұяшығының штифтері #; мысалы, p (1) = 4
- C: ұяшықтардың жалпы саны #; мысалы, C = 13
- N: торлардың жалпы саны #; мысалы, N = 4
- P: түйреуіштердің жалпы саны #; P = p (1) +… + p (C) = n (1) +… + n (N)
- Аудан қатынасы r, 0
Шығарылым: 2 бөлім
- Cutsetsize минимизацияланған
- | A | / (| A | + | B |). R
Сондай-ақ қараңыз
Әдебиеттер тізімі
- ^ Фидучия; Mattheyses (1982). «Желілік бөлімдерді жақсартудың сызықтық-уақыттық эвристикасы» (PDF). 19-шы дизайн автоматика конференциясы. Алынған 23 қазан 2013.