Gebruiker:Warsocket/Kernighan-Lin

Kernighan-Lin is een algoritme (methode) om een lokale zoekactie uit te voeren. Dit wordt gebruikt bij het graaf-bipartioneringsprobleem (zie Grafentheorie). Hierbij is het doel het de 2 kleuren van de knopen van de graaf zo aan te passen zodat er zo min mogelijk knopen van verschillende kleur met elkaar verbonden zijn. Het aantal knopen dat met elkaar verbonden is en een andere kleur bezit noemt met de knipgrootte.

Gebipartitioneerde graaf met knipgrootte = 2

Algoritme

Het algoritme begint met een gebalanceerde graaf (evenveel 'witte' en 'zwarte' knooppunten)

1. Probeer alle mogelijke wissels van de vrije knopen
2. Voer de wissel uit die de kleinste knipgroote oplevert
3. Fixeer de gewisselde knopen
4. Herhaal stap 1 t/m 3 totdat er geen vrije knopen meer zijn
5. ga nu terug naar de situatie waarbij de knipgrootte minimaal is
6. Herhaal stap 1 t/m 6 totdat deze geen verbetering meer opleveren
7. Nu is er een lokaal optimum gevonden

Pseudo code

For k1 in aantalKnopen: [tab]For k2 in aantalKnopen: [tab][tab]If k1 != k2