Algoritmus Fiduccia – Mattheyses - Fiduccia–Mattheyses algorithm - Wikipedia

Tento článek možná bude muset být přepsáno vyhovět požadavkům Wikipedie standardy kvality. Můžeš pomoct. The diskusní stránka může obsahovat návrhy. (Ledna 2015)

Klasický přístup k řešení Hypergraf bipartitioning problem is an iterative heuristic by Charles Fiduccia and Robert Mattheyses.^[1] Tato heuristika se běžně nazývá algoritmus FM.

Úvod

Algoritmus FM je lineární časová heuristika pro zlepšení síťových oddílů. Nové funkce pro K-L heuristika:

• Usiluje o snížení čistých nákladů; pojem cutize je rozšířen na hypergrafy.
• Pouze jeden vrchol se pohybuje přes řez jediným pohybem.
• Vrcholy jsou váženy.
• Zvládne "nevyvážené" oddíly; je zaveden bilanční faktor.
• Speciální datová struktura se používá k výběru vrcholů, které se mají přesunout přes řez, aby se zlepšila doba provozu.
• Časová složitost Ó(P), kde P je celkový počet terminálů.

Příklad FM

F – M heuristika: notace

Vstup: Hypergraf se sadou vrcholů (buněk) a sadou hyperedge (sítí)

• n (i): # buněk v Net i; např. n (1) = 4
• s (i): velikost buňky i
• p (i): # kolíků buňky i; např. p (1) = 4
• C: celkový počet buněk; např. C = 13
• N: celkový počet sítí; např. N = 4
• P: celkový počet pinů; P = p (1) +… + p (C) = n (1) +… + n (N)
• Poměr plochy r, 0

Výstup: 2 oddíly

• Cutsetsize je minimalizován
• | A | / (| A | + | B |) ≈ r

Viz také

• Grafický oddíl
• Algoritmus Kernighan – Lin

Reference