El algoritmo de Kernighan-Lin es un algoritmo heurístico para encontrar particiones de gráficos . El algoritmo tiene aplicaciones importantes en el diseño de circuitos y componentes digitales en VLSI . [1] [2]
Descripción
La entrada al algoritmo es un grafo no dirigido G = ( V , E ) con conjunto de vértices V , conjunto de aristas E , y (opcionalmente) pesos numéricos en los bordes en E . El objetivo del algoritmo es a la partición V en dos subconjuntos disjuntos A y B de igual (o casi igual) tamaño, de una manera que minimiza la suma T de los pesos del subconjunto de aristas que cruzada de A a B . Si el gráfico no está ponderado, entonces el objetivo es minimizar el número de bordes cruzados; esto equivale a asignar un peso a cada borde. El algoritmo mantiene y mejora una partición, en cada paso utilizando un algoritmo codicioso para emparejar los vértices de A con los vértices de B , de modo que mover los vértices emparejados de un lado de la partición al otro mejorará la partición. Después de hacer coincidir los vértices, se realiza entonces un subconjunto de los pares elegidos para tener el mejor efecto general sobre la calidad de la solución T . Dado un gráfico con n vértices, cada paso del algoritmo se ejecuta en el tiempo O ( n 2 log n ) .
Más detalladamente, para cada , dejar ser el costo interno de una , es decir, la suma de los costos de los bordes entre una y otros nodos en A , y dejarser el coste externo de una , es decir, la suma de los costos de los bordes entre una y nodos en B . Del mismo modo, defina, para cada . Además, deja
ser la diferencia entre los costos internos y externos del s . Si a y b se intercambian, entonces la reducción en el costo es
dónde es el costo del borde posible entre una y b .
El algoritmo intenta encontrar una serie óptima de operaciones de intercambio entre elementos de y que maximiza y luego ejecuta las operaciones, produciendo una partición de la gráfica de A y B . [1]
Pseudocódigo
Fuente: [2]
función Kernighan-Lin ( G (V, E) ) es determinar una partición inicial equilibrada de los nodos en conjuntos A y B hacer calcular los valores D para todo a en A y b en B deja que gv, av y bv sean listas vacías para n: = 1 a | V | / 2 hacer hallar a de A y b de B, tal que g = D [a] + D [b] - 2 × c (a, b) es máximo eliminar a y b de una consideración adicional en esta pasada agregue g a gv, a a av yb a bv actualizar los valores D para los elementos de A = A \ a y B = B \ b final para encuentra k que maximiza g_max, la suma de gv [1], ..., gv [k] si g_max> 0 entonces Intercambie av [1], av [2], ..., av [k] con bv [1], bv [2], ..., bv [k] hasta (g_max ≤ 0) volver G (V, E)
Ver también
Referencias
- ^ a b Kernighan, BW ; Lin, Shen (1970). "Un procedimiento heurístico eficiente para particionar gráficos". Revista técnica de Bell System . 49 : 291-307. doi : 10.1002 / j.1538-7305.1970.tb01770.x .
- ^ a b Ravikumar, C. P (1995). Métodos paralelos para el diseño de diseños VLSI . Grupo editorial de Greenwood. pag. 73. ISBN 978-0-89391-828-6.