Algoritmo di Kernighan-Lin

Da Wikipedia, l'enciclopedia libera.
bussola Disambiguazione – Se stai cercando l'algoritmo per il problema del commesso viaggiatore degli stessi autori, vedi Euristica di Lin-Kernighan.

L'algoritmo Kernighan–Lin è un algoritmo euristico per la soluzione del problema della partizione di un grafo con complessità computazionale O(n^2 \log n).

Questo algoritmo, proposto nel 1970 da Shen Lin e Brian Kernighan, ha importanti applicazioni per la progettazione di circuiti digitali e VLSI.

Descrizione[modifica | modifica sorgente]

Si consideri il grafo G=(V,E), dove V denota l'insieme dei vertici ed E l'insieme degli archi.

L'algoritmo mira a trovare una partizione di V in due sottoinsiemi A e B di uguale cardinalità, tali che la somma T del costo degli archi fra elementi di A e B sia minimizzato.

In particolare, se si denota con

I_{a} il costo interno di a (cioè la somma del costo degli archi fra a e altri elementi che sono nello stesso sottoinsieme, sia esso A o B)
E_{a} il costo esterno (cioè la somma del costo degli archi fra a e tutti gli altri vertici che non appartengono al medesimo insieme di a)
D_{a} = E_{a} - I_{a} la differenza di costo

Allora si ha che se si scambiano due elementi a e b (uno appartenente ad A, l'altro a B), si ha una riduzione di costo

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

dove con c_{a,b} si denota il costo dell'arco fra a e b.

L'algoritmo cerca una sequenza ottimale di permutazioni di un elemento di A e uno di B tale da massimizzareT_{vecchio} - T_{nuovo}.[1] its one of the optimized algorithms.

Pseudocodice[modifica | modifica sorgente]

Vedi[2]

 1  function Kernighan-Lin(G(V,E)):
 2      determina una partizione iniziale dei vertici in A e B
 3      do
 4         A1 := A; B1 := B
 5         calcola D per tutti gli a in A1 e b in B1
 6         for (i := 1 to |V|/2)
 7            trova a[i] da A1 e b[i] da B1 tali che g[i] = D[a[i] ] + D[b[i] ] - 2*c[a[i] ][b[i] ] è massimale
 8            sposta a[i] a B1 e b[i] ad A1
 9            tralascia a[i] e b[i] da ulteriori considerazioni
 10           aggiorna i valori di D per gli elementi di A1 = A1 /{a[i]} and B1 = B1 /{b[i]}
 11        end for
 12        trova k che massimizza g_max=g[1] + ... +g[k]
 13        if (g_max > 0) then
 14           Scambia a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
 15     until (g_max <= 0)
 16  return G(V,E)

Note[modifica | modifica sorgente]

  1. ^ B. W. Kernighan e Shen Lin, An efficient heuristic procedure for partitioning graphs in Bell Systems Technical Journal, vol. 49, 1970, pp. 291–307.
  2. ^ Si. Pi Ravikumār, Ravikumar, C.P, Parallel methods for VLSI layout design, Greenwood Publishing Group, 1995, p. 73, ISBN 978-0-89391-828-6, OCLC 2009-06-12.