Algoritmul Kernighan-Lin

Algoritmul Kernighan-Lin este un algoritm euristic pentru soluționarea problemei partiționării unui grafic cu complexitate de calcul $O(n^{2}\log n)$ ${\ displaystyle O (n ^ {2} \ log n)}$ ${\ displaystyle O (n ^ {2} \ log n)}$ .

Acest algoritm, propus în 1970 de Shen Lin și Brian Kernighan , are aplicații importante pentru proiectarea circuitelor digitale și VLSI .

Descriere

Luați în considerare graficul $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ , unde este $V.$ ${\ displaystyle V}$ $V.$ denotă mulțimea vârfurilor și $ȘI$ ${\ displaystyle E}$ $ȘI$ setul de arcade .

Algoritmul își propune să găsească o partiție a $V.$ ${\ displaystyle V}$ $V.$ în două subseturi $LA$ ${\ displaystyle A}$ $LA$ Și $B.$ ${\ displaystyle B}$ $B.$ de cardinalitate egală, astfel încât suma $T.$ ${\ displaystyle T}$ $T.$ a costului arcurilor dintre elementele de $LA$ ${\ displaystyle A}$ $LA$ Și $B.$ ${\ displaystyle B}$ $B.$ să fie minimizate.

În special, dacă este notat cu

I_{a}

{\ displaystyle I_ {a}}

{\ displaystyle I_ {a}}

costul intern al

la

{\ displaystyle a}

la

(adică suma costului arcurilor între

la

{\ displaystyle a}

la

și alte elemente care se află în același subset, fie el

LA

{\ displaystyle A}

LA

sau

B.

{\ displaystyle B}

B.

)

E_{a}

{\ displaystyle E_ {a}}

{\ displaystyle E_ {a}}

costul extern (adică suma costului arcurilor între

la

{\ displaystyle a}

la

și toate celelalte vârfuri care nu aparțin aceluiași set de

la

{\ displaystyle a}

la

)

D_{a}=E_{a}-I_{a}

{\ displaystyle D_ {a} = E_ {a} -I_ {a}}

{\ displaystyle D_ {a} = E_ {a} -I_ {a}}

diferența de cost

Atunci avem asta dacă se schimbă două elemente $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ (unul aparținând $LA$ ${\ displaystyle A}$ $LA$ , cealaltă a $B.$ ${\ displaystyle B}$ $B.$ ), există o reducere a costurilor

T_{vecchio}-T_{nuovo}=D_{a}+D_{b}-2c_{a,b}

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

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

unde cu $c_{a,b}$ ${\ displaystyle c_ {a, b}}$ ${\ displaystyle c_ {a, b}}$ costul arcului este notat între $la$ ${\ displaystyle a}$ $la$ Și $b$ ${\ displaystyle b}$ $b$ .

Algoritmul caută o succesiune optimă de permutații ale unui element de $LA$ ${\ displaystyle A}$ $LA$ este unul din $B.$ ${\ displaystyle B}$ $B.$ precum pentru a maximiza $T_{vecchio}-T_{nuovo}$ ${\ displaystyle T_ {old} -T_ {new}}$ ${\ displaystyle T_ {old} -T_ {new}}$ . ^[1] este unul dintre algoritmii optimizați.

Pseudo cod

Vezi ^[2]

 1 funcție Kernighan-Lin ( G (V, E) ):
 2 determină o partiție inițială a vârfurilor în A și B
 3 fac
 4 A1: = A; B1: = B
 5 calculează D pentru toate a din A1 și b din B1
 6 pentru (i: = 1 până la | V | / 2)
 7 găsește un [i] din A1 și b [i] din B1 astfel încât g [i] = D [a [i]] + D [b [i]] - 2 * c [a [i]] [b [ i]] este maxim
 8 deplasează a [i] la B1 și b [i] la A1
 9 omite a [i] și b [i] din alte considerații
 10 actualizează valorile lui D pentru elementele A1 = A1 / {a [i]} și B1 = B1 / {b [i]}
 11 sfârșit pentru
 12 găsește k care maximizează g_max = g [1] + ... + g [k]
 13 if (g_max> 0) atunci
 14 Schimbă a [1], a [2], ..., a [k] cu b [1], b [2], ..., b [k]
 15 până la (g_max <= 0)
 16 retur G (V, E)

Notă

^ BW Kernighan și Shen Lin , O procedură euristică eficientă pentru partiționarea graficelor , în Bell Systems Technical Journal , vol. 49, 1970, pp. 291-307.
^ Da. Pi Ravikumār, Ravikumar, CP, Metode paralele pentru proiectarea aspectului VLSI , Greenwood Publishing Group, 1995, p. 73, ISBN 978-0-89391-828-6 ,OCLC 2009-06-12 .

[kl-1] BW Kernighan și Shen Lin , O procedură euristică eficientă pentru partiționarea graficelor , în Bell Systems Technical Journal , vol. 49, 1970, pp. 291-307.

[ravikumar-2] Da. Pi Ravikumār, Ravikumar, CP, Metode paralele pentru proiectarea aspectului VLSI , Greenwood Publishing Group, 1995, p. 73, ISBN 978-0-89391-828-6 ,OCLC 2009-06-12 .

[1]

[2]