케르니간-린 알고리즘

Kernighan-Lin 알고리즘은 그래프의 파티션을 찾기 위한 경험적 알고리즘이다.알고리즘은 VLSI의 전자 설계 자동화에 있어 디지털 회로와 구성 요소의 레이아웃에 중요한 실용적 응용이 있다.^[1][2]

설명

알고리즘에 대한 입력은 E의 가장자리에 정점 집합 V, 에지 집합 E 및 (선택적으로) 숫자 가중치가 있는 비방향 그래프 G = (V, E)이다.알고리즘의 목표는 A에서 B로 교차하는 가장자리 부분 집합의 가중치의 합계 T를 최소화하는 방법으로 V를 동일(또는 거의 동일한) 크기의 두 개의 분리 하위 집합 A와 B로 분할하는 것이다.그래프가 가중치가 없는 경우 그 대신 교차 가장자리 수를 최소화하는 것이 목표다. 이는 각 가장자리에 가중치를 하나씩 할당하는 것과 같다.알고리즘은 A의 정점을 B의 정점과 짝을 이루는 욕심 많은 알고리즘을 사용하여 각 패스에서 파티션을 유지하고 개선하여, 쌍으로 된 정점을 파티션의 한 쪽에서 다른 쪽으로 이동하면 파티션이 개선된다.정점을 일치시킨 후, 솔루션 품질 T에 가장 전체적인 영향을 미치기 위해 선택한 쌍의 부분집합을 수행한다.정점이 n개인 그래프를 보면 알고리즘의 각 패스는 시간 O(n² log n)로 실행된다.

In more detail, for each ${\displaystyle a\in A}$, let ${\displaystyle I_{a}}$ be the internal cost of a, that is, the sum of the costs of edges between a and other nodes in A, and let ${\displaystyle E_{a}}$ be the external cost of a, that is, the sum of the costs of edges between a and nodes in B.마찬가지로$,$ 각 ${\displaystyle b}$에 대해$$ $I{\displaystyle {}_{}}$ ${\displaystyle b_{}}$ ${\$ $E{\displaystyle {}_{}}$ ${\displaystyle b_{}}$ ${\$$displaystyle E_{b$$}$를 정의하십시오$.$ $또한$,

${\displaystyle D_{s}=E_{s}-I_{s}}}$

s의 외부 비용과 내부 비용의 차이다.a와 b를 상호 교환할 경우, 비용 절감은 다음과 같다.

${\displaystyle T_{old}-T_{new}=D_{a}+D_{b}-2c_{a,b}}}$

$여기$서 ${\displaystyle {c,}_{}}$ ${\displaystyle b_{}}$ ${\$는 a와 b 사이의 가능한 에지 비용이다$$.

알고리즘은 ${\displaystyle {To}_{}}$ l ${\displaystyle d_{}}$ -${\displaystyle {}_{}{}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle e_{}}$ ${\displaystyle w_{}}$ ${\$을(를$)$ 최대화한 $다음$$$ 연산을 실행하여 그래프의 파티션을 A와 B에 생성한다$.$^[1]

가성음

출처:^[2]

function Kernighan-Lin(G(V, E)) is     determine a balanced initial partition of the nodes into sets A and B          do         compute D values for all a in A and b in B         let gv, av, and bv be empty lists         for n := 1 to  V  / 2 do             find a from A and b from B, such that g = D[a] + D[b] − 2×c(a, b) is maximal             regv에 av고, bg를 추가하고 b더 이상 고려되지 않다에 대한 bv를 업데이트하 D값에 대한 요소의 A=한\와 같이고 B)B)b에 끝날 것을 발견 k은 극대화 g_max, 이 합계의 gv[1],..., gv[k]만약g_max>0다음 거래소 av[1], av[2],..., av[k]과 bv[1], bv[2]합니다..,bv[k] ~ (g_max ≤ 0) 반환 G(V, E)

참고 항목

• 피두치아-마테이스 알고리즘

참조