Участник:Midmedian/Алгоритм Федуччи-Маттеуса
Автор описания: И.А.Бабкин
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Федуччи-Маттеуса (FM-алгоритм)[1] является эвристикой для оптимального разделения гиперграфа на два непересекающихся блока (подграфа) с минимальным количеством разрезанных сетей (гиперрёбер) за линейной время.
Математическое описание алгоритма
Пусть дан гиперграф [math]\displaystyle{ P=(C,N) }[/math], где [math]\displaystyle{ C }[/math] - это пронумерованный набор ячеек (вершин), соединённых пронумерованным набором сетей [math]\displaystyle{ N }[/math]. Гарантируется, что гиперграф состоит как минимум из двух ячеек и что каждая из ячеек содержится хотя бы в одной из сетей.
Количество ячеек в [math]\displaystyle{ i }[/math]-ой сети обозначим как [math]\displaystyle{ n(i) }[/math], а размер [math]\displaystyle{ j }[/math]-ой ячейки (количество сетей, в которые входит ячейка) за [math]\displaystyle{ s(j) }[/math].
Размер блока [math]\displaystyle{ B }[/math] определим, как
- [math]\displaystyle{ |B|=\sum\limits_{i=1}^{|N|} n(i)=\sum\limits_{i=1}^{|C|} s(i) }[/math].
Задача заключается в разделении [math]\displaystyle{ P }[/math] на непересекающиеся блоки [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] размерами [math]\displaystyle{ |A| }[/math] и [math]\displaystyle{ |B| }[/math] соответственно так, чтобы выполнялось условие
- [math]\displaystyle{ \frac{|A|}{|A|+|B|} \cong r }[/math],
где [math]\displaystyle{ r }[/math] - коэффициент разделения ([math]\displaystyle{ 0 \lt r \lt 1 }[/math]).
Прирост [math]\displaystyle{ i }[/math]-ой ячейки, находящейся в некотором блоке [math]\displaystyle{ B }[/math], определим, как
- [math]\displaystyle{ \Delta g(i)=FS(i)-TE(i) }[/math][2],
где [math]\displaystyle{ FS(i) }[/math] - количество разрезанных сетей, связанных только с [math]\displaystyle{ i }[/math]-ой ячейкой (и никакой другой из блока [math]\displaystyle{ B }[/math]), а [math]\displaystyle{ TE(i) }[/math] - количество неразрезанных сетей, связанных с [math]\displaystyle{ i }[/math]-ой ячейкой.