Классический подход к решению проблемы разделения гиперграфа - итеративная эвристика Чарльза Фидуччи и Роберта Маттейсеса. [1] Эту эвристику обычно называют алгоритмом FM.
Вступление
Алгоритм FM - это эвристика линейного времени для улучшения сетевых разделов. Новые возможности эвристики KL :
- Нацелен на снижение чистых затрат; понятие сечения распространяется на гиперграфы.
- Только одна вершина перемещается по разрезу за один ход.
- Вершины взвешены.
- Может обрабатывать «несбалансированные» перегородки; вводится коэффициент баланса.
- Специальная структура данных используется для выбора вершин, которые нужно перемещать по разрезу, чтобы сократить время работы.
- Временная сложность 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 раздела
- Размер разреза сведен к минимуму
- | A | / (| A | + | B |) ≈ r
Смотрите также
Рекомендации
- ^ Фидучча; Маттейсес (1982). «Эвристика линейного времени для улучшения сетевых разделов» (PDF) . 19-я конференция по автоматизации проектирования . Проверено 23 октября 2013 года .