Algorytm Fiduccia-Mattheysesa
Klasycznym podejściem do rozwiązania problemu dwupartycjonowania hipergrafu jest iteracyjna heurystyka autorstwa Charlesa Fiduccii i Roberta Mattheysesa. Ta heurystyka jest powszechnie nazywana algorytmem FM.
Wstęp
Algorytm FM to liniowa heurystyka czasu służąca do ulepszania partycji sieciowych. Nowe funkcje heurystyki KL :
- Ma na celu zmniejszenie kosztów cięć netto; koncepcja cutsize została rozszerzona na hipergrafy.
- Tylko jeden wierzchołek jest przesuwany w poprzek cięcia w jednym ruchu.
- Wierzchołki są ważone.
- Może obsłużyć „niezbalansowane” partycje; wprowadzony zostaje współczynnik równowagi.
- Do wybierania wierzchołków, które mają zostać przesunięte w poprzek cięcia, używana jest specjalna struktura danych, aby skrócić czas działania.
- Złożoność czasowa O ( P ), gdzie P to całkowita liczba terminali.
Przykład FMa
Heurystyka F – M: notacja
Wejście: Hipergraf ze zbiorem wierzchołków (komórek) i zbiorem hiperkrawędzi (sieć).
- n(i): liczba komórek w sieci i; np. n(1) = 4
- s(i): rozmiar komórki i
- p(i): liczba pinów komórki i; np. p(1) = 4
- C: całkowita liczba komórek; np. C = 13
- N: całkowita liczba sieci; np. N = 4
- P: całkowita liczba pinów; P = p(1) + … + p(C) = n(1) + … + n(N)
- Stosunek powierzchni r, 0< r<1
Wyjście: 2 partycje
- Rozmiar zestawu cięć jest zminimalizowany
- |A|/(|A|+|B|) ≈ r