Algoritmo di Kernighan-Lin

Da Wikipedia, l'enciclopedia libera.
Nota disambigua.svg 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 .

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 wikitesto]

Si consideri il grafo , dove denota l'insieme dei vertici ed l'insieme degli archi.

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

In particolare, se si denota con

il costo interno di (cioè la somma del costo degli archi fra e altri elementi che sono nello stesso sottoinsieme, sia esso o )
il costo esterno (cioè la somma del costo degli archi fra e tutti gli altri vertici che non appartengono al medesimo insieme di )
la differenza di costo

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

dove con si denota il costo dell'arco fra e .

L'algoritmo cerca una sequenza ottimale di permutazioni di un elemento di e uno di tale da massimizzare.[1] its one of the optimized algorithms.

Pseudocodice[modifica | modifica wikitesto]

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 wikitesto]

  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.