Algoritmus Kernighan – Lin - Kernighan–Lin algorithm

The Algoritmus Kernighan – Lin je heuristický algoritmus pro hledání oddílů grafů Algoritmus má důležité aplikace v uspořádání digitálních obvodů a komponent v VLSI.^[1]^[2]

Popis

Vstup do algoritmu je neorientovaný graf $G = (PROTI, E)$ se sadou vrcholů $PROTI$ , sada hran $E$ , a (volitelně) číselné váhy na okrajích v $E$ . Cílem algoritmu je rozdělení $PROTI$ do dvou disjunktních podmnožin $A$ a $B$ stejné (nebo téměř stejné) velikosti způsobem, který minimalizuje součet $T$ vah podmnožiny hran, které procházejí od $A$ na $B$ . Pokud je graf nevážený, pak je místo toho cílem minimalizovat počet křížení hran; to je ekvivalent přiřazení váhy jedné každé hraně. Algoritmus udržuje a vylepšuje oddíl v každém průchodu pomocí a chamtivý algoritmus spárovat vrcholy $A$ s vrcholy $B$ , takže přesun spárovaných vrcholů z jedné strany oddílu na druhou zlepší oddíl. Po přizpůsobení vrcholů pak provede podmnožinu zvolených párů, aby měl nejlepší celkový účinek na kvalitu řešení $T$ .Daný graf s $n$ vrcholy, každý průchod algoritmu běží v čase $Ó (n 2 log n)$ .

Podrobněji pro každého ${ displaystyle a v A}$ , nechť ${ displaystyle I_ {a}}$ být interní náklady z A, tj. součet nákladů na hrany mezi A a další uzly v Aa nechte ${ displaystyle E_ {a}}$ být externí náklady z A, tj. součet nákladů na hrany mezi A a uzly v B. Podobně definujte ${ displaystyle I_ {b}}$ , ${ displaystyle E_ {b}}$ pro každého ${ displaystyle b v B}$ . Kromě toho

{ displaystyle D_ {s} = E_ {s} -I_ {s}}

být rozdíl mezi externími a interními náklady s. Li A a b jsou zaměňovány, pak je snížení nákladů

{ displaystyle T_ {old} -T_ {new} = D_ {a} + D_ {b} -2c_ {a, b}}

kde ${ displaystyle c_ {a, b}}$ je cena možné hrany mezi A a b.

Algoritmus se pokouší najít optimální řadu operací výměny mezi prvky ${ displaystyle A}$ a ${ displaystyle B}$ který maximalizuje ${ displaystyle T_ {starý} -T_ {nový}}$ a poté provede operace a vytvoří část grafu do A a B.^[1]

Pseudo kód

Zdroj:^[2]

funkce Kernighan-Lin (G (V, E)) je    určete vyvážené počáteční rozdělení uzlů do množin A a B. dělat        vypočítat hodnoty D pro všechna a v A a b v B, ať jsou gv, av a bv prázdné seznamy pro n: = 1 na | V | / 2 dělat            najděte a z A ab z B, takže g = D [a] + D [b] - 2 × c (a, b) je maximální odebrat a a b z dalšího uvažování v tomto průchodu přidat g do gv, a to av a b až bv aktualizují hodnoty D pro prvky A = A  a a B = B  b konec pro        najděte k, které maximalizuje g_max, součet gv [1], ..., gv [k] -li g_max> 0 pak            Vyměňte av [1], av [2], ..., av [k] s bv [1], bv [2], ..., bv [k] do (g_max ≤ 0)    návrat G (V, E)

Viz také

Algoritmus Fiduccia – Mattheyses

Reference

^ ^A ^b Kernighan, B. W.; Lin, Shen (1970). Msgstr "Efektivní heuristický postup pro dělení grafů". Technický deník Bell System. 49: 291–307. doi:10.1002 / j.1538-7305.1970.tb01770.x.
^ ^A ^b Ravikumar, C. P (1995). Paralelní metody pro návrh rozvržení VLSI. Greenwood Publishing Group. str. 73. ISBN 978-0-89391-828-6.

[kl-1] A ^b Kernighan, B. W.; Lin, Shen (1970). Msgstr "Efektivní heuristický postup pro dělení grafů". Technický deník Bell System. 49: 291–307. doi:10.1002 / j.1538-7305.1970.tb01770.x.

[ravikumar-2] A ^b Ravikumar, C. P (1995). Paralelní metody pro návrh rozvržení VLSI. Greenwood Publishing Group. str. 73. ISBN 978-0-89391-828-6.

[1]

[2]