Алгоритм Фидуччи – Маттезеса - Fiduccia–Mattheyses algorithm

Классический подход к решению Гиперграф Проблема разделения на части - итеративная эвристика Чарльза Фидуччи и Роберта Маттейсеса.[1] Эту эвристику обычно называют алгоритмом FM.

Вступление

Алгоритм FM - это эвристика линейного времени для улучшения сетевых разделов. K-L эвристика:

  • Нацелен на снижение чистых затрат; понятие сечения распространяется на гиперграфы.
  • Только одна вершина перемещается по разрезу за один ход.
  • Вершины взвешены.
  • Может обрабатывать «несбалансированные» перегородки; вводится коэффициент баланса.
  • Специальная структура данных используется для выбора вершин, которые нужно перемещать по разрезу, чтобы сократить время работы.
  • Сложность времени О(п), куда п общее количество терминалов.
Пример FM

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

Смотрите также

Рекомендации

  1. ^ Фидучча; Маттейсес (1982). «Эвристика линейного времени для улучшения сетевых разделов» (PDF). 19-я конференция по автоматизации проектирования. Получено 23 октября 2013.