vignette|Comptage bipartitionné avec taille de coupe = 2 L'algorithme de Kernighan–Lin est une heuristique pour réaliser un partitionnement de graphe. L'algorithme est notamment utilisé pour l'agencement des circuits intégrés et des composants pour l'intégration à très grande échelle (VLSI). Description
L'algorithme prend en entrée un graphe non-orienté , défini par l'ensemble de nœuds , l'ensemble de liens et potentiellement les coûts des liens de . L'objectif est de réaliser une partition de l'ensemble en deux ensembles disjoints et de tailles proches ou égales, de manière à minimiser la somme des poids du sous-ensemble de liens allant de à . Si le graphe est non-pondéré, l'algorithme cherche à minimiser le nombre de liens allant de à , ce qui est équivalent à assigner un poids unitaire à tous les liens.
L'algorithme tient à jour une partition et l'améliore à chaque itération en utilisant une méthode gloutonne. Le principe est d'apparier des nœuds de à des nœuds de , de manière qu'intervertir les ensembles auxquels appartiennent les nœuds appariés améliore la qualité du partitionnement. Après association des nœuds, l'algorithme réalise un sous-ensemble des paires choisies pour obtenir la valeur minimum de . Pour un graphe à nœuds, chaque itération de l'algorithme est réalisée en .
Plus précisément, pour tout , on appelle le coût interne de , c'est-à-dire la somme des coûts des liens entre et les autres nœuds de et le coût externe de , c'est-à-dire la somme des coûts des liens entre et les nœuds de . On définit de manière analogue et pour tout . On pose
la différence entre les coûts externes et internes de . Si et sont intervertis, alors la réduction de coût est:
où est le coût d'un potentiel lien entre et .
L'algorithme cherche à trouver une suite optimale d'interversions entre éléments de et de qui maximise puis met à jour le partitionnement du graphe en et en réalisant effectivement ces opérations.
Pseudocode
Source
fonction Kernighan-Lin(G(V, E)) déterminer une partition initiale des nœuds équilibrée entre les ensembles A et B
faire calculer les valeurs D pour tout a dans A et tout b dans B soient L_g, L_a, et L_b des listes vides pour n := 1 à |V| faire trouver a dans A et b dans B tels que g = D[a] + D[b] − 2×c(a, b) est maximum on ne considère plus a et b dans la suite de cette itération ajouter g à L_g, a à L_a et b à L_b mettre à jour les valeurs D pour les éléments de A = A \ a et B = B \ b fin pour trouver k qui maximise g_max, la somme des L_g, ..., L_g[k] si g_max > 0 alors Mettre L_a, L_a, ..., L_a[k] dans B et L_b, L_b, ..., L_b[k] dans A jusqu'à (g_max ≤ 0)
renvoyer A,B
Références
Catégorie:Algorithmique Catégorie:Optimisation combinatoire