헝가리 알고리즘

헝가리 방법은 다항 시간 내에 할당 문제를 해결하는 결합 최적화 알고리즘으로, 나중에 예상되는 원시-이중 방법을 의미한다.해롤드 쿤이 1955년에 개발하여 출판한 것인데, 그는 이 알고리즘이 크게 두 헝가리 수학자의 초기 저작에 기초했기 때문에 "헝가리식 방법"이라는 이름을 붙였다.데네스 케니그와 ^[1][2]제니 에거바리

제임스 뮌크레스는 1957년에 이 알고리즘을 검토했고 그것이 (강력하게) 다항식이라는 것을 관찰했다.^[3]그 이후로 알고리즘은 쿤-멍크레스 알고리즘 또는 뮌크레스 할당 알고리즘으로도 알려져 왔다.원래의 알고리즘의 시간 복잡성은 $O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {4\mathrm{}}^{}}$) ${\displaystyle O(n^{4$ 그러나 Edmonds와 Karp, 독립적으로 Tomiza는 $O{\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$) ${\displaystyle O(n^{3})$ 실행 시간을$$ 달성하도록 수정할 수 있다는 것을 알아차렸다.^[4][5][how?]가장 많이^{[citation needed]} 사용되는 $O{\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})$ 변종$$ 중 하나는 Jonker-Volgenant 알고리즘이다.^[6]Ford와 Fulkerson은 이 방법을 Ford-Fulkerson 알고리즘의 형태로 일반적인 최대 흐름 문제까지 확장했다.2006년에 칼 구스타프 자코비가 19세기에 과제 문제를 해결했다는 사실이 밝혀졌고, 그 해결책은 1890년에 라틴어로 사후에 출판되었다.^[7]

문제

예

이 간단한 예에는 세 명의 노동자가 있다: 폴, 데이브, 그리고 크리스.그 중 하나는 화장실 청소를 해야 하고, 다른 하나는 바닥을 쓸고, 세 번째는 창문을 닦아야 하지만, 그들은 각각의 다양한 작업에 대해 서로 다른 보수를 요구한다.문제는 일자리를 할당하는 가장 저렴한 방법을 찾는 것이다.그 문제는 노동자들이 그 일을 하는 데 드는 비용의 행렬로 나타낼 수 있다.예를 들면 다음과 같다.

	클린 욕실	스위프 플로어	창 세척
폴.	$2	$3	$3
데이브	$3	$2	$3
크리스	$3	$3	$2

위의 표에 적용했을 때 헝가리식 방법은 최소한의 비용을 줄 것이다: 이것은 6달러인데, 폴이 화장실을 청소하고, 데이브가 바닥을 쓸고, 크리스가 창문을 닦게 함으로써 달성한 것이다.

행렬식

매트릭스 공식에서, 우리는 n×n 매트릭스가 음이 아닌 매트릭스가 주어지는데, 여기서 i번째 행과 j번째 열의 요소는 i번째 작업자에게 j번째 작업을 할당하는 비용을 나타낸다.우리는 각각의 일을 한 사람에게 할당하고, 각 노동자에게 한 가지 일을 할당하여 총 할당 비용이 최소가 되도록 하는, 노동자에게 할당되는 일의 할당을 찾아야 한다.

이는 비용 행렬 C의 행과 열을 허용하여 행렬의 추적을 최소화하는 것으로 표현할 수 있다.

${\displaystyle \min _{L,R}{\rm {Tr}(LCR)}$

여기서 L과 R은 순열 행렬이다.

최대 비용을 산출하는 과제를 찾는 것이 목표라면 비용 매트릭스 C를 부정함으로써 문제를 해결할 수 있다.

초당적 그래프 제형식

알고리즘은 우리가 초당적 그래프를 사용하여 문제를 공식화하면 설명하기가 더 쉽다.우리는 완전한 초당적 그래프 $G{\displaystyle }$= ${\displaystyle (S}$ ${\displaystyle ,}$ ${\displaystyle T}$; E$){\displaystyle$ G$=(S,T;E)$를 가지고 있고, n worker 꼭지점 (S)과 n job 꼭지점 (T)이$$ 있고, 각 가장자리에는 음이 아닌 $비용{\displaystyle }$ c$,j)$가 있다$.$ 우리는 최소 총비용과 완벽하게 일치하는 것을 찾기를 원한다.

초당적 그래프 측면에서 알고리즘

Let us call a function ${\displaystyle y:(S\cup T)\to \mathbb {R} }$ a potential if ${\displaystyle y(i)+y(j)\leq c(i,j)}$ for each ${\displaystyle i\in S,j\in T}$. The value of potential y is the sum of the potential over all vertices: ${\displaystyle \sum _{v\in S\cup T}y(v)}$$\displaystyle \sum _{v\in S\cup T}y(v$

각각의 완벽한 매칭의 비용은 적어도 각각의 잠재력의 값이다: 매칭의 총 비용은 모든 에지의 비용의 합이다. 각 에지의 비용은 적어도 엔드포인트의 잠재력의 합이다. 매칭이 완벽하기 때문에, 각 꼭지점은 정확히 하나의 에지의 끝점이다. 따라서 총 비용은 적어도 잠재력의 합이다.

헝가리 방법은 완벽한 매칭과 매칭 비용이 잠재적 가치와 같을 수 있는 가능성을 찾아낸다.이는 둘 다 최적이라는 것을 증명한다.실제로 헝가리 방법은 타이트한 가장자리의 완벽한 일치를 찾아낸다: ${\displaystyle \mathrm{엣지}}$ i $j{\displaystyle }$ ${\displaystyle ij}$이(${\displaystyle 가)}$ y${\displaystyle }$(${\displaystyle }$i${\displaystyle }$)${\displaystyle }$+ ${\displaystyle y}$( ) = ${\displaystyle c,}$ ${\displaystyle j}$) ${\displaysty y(i)+y(j)=c(i,$$j$$)\}\}.$ ${\displaystyle G_{}}$ y$${\$displaysty$에 의한 타이트한 가장자리의 하위 그래프를 $표시$한다.$G{\displaystyle {}_{}}$ ${\displaystyle y_{}}$ ${\$있는 경우)의 완벽한 매칭 비용은 y의 값과 같다.

알고리즘 동안 우리는 $잠재적$인 ${\displaystyle y_{}}$와 G y ${\$${\displaystyle \stackrel{}{G_{}}}$ y${\displaystyle \stackrel{}{{}_{}}}$→ ${\$의 방향을 유지하며, 이 값은 T에서 S로 향하는 가장자리가 일치하는 M을 형성하는 특성을 갖는다.초기에는 어디에서나 y가 0이고, 모든 가장자리는 S에서 T로 방향을 잡는다(그래서 M은 비어 있다).각 단계에서 값이 증가하도록 y를 수정하거나 더 많은 가장자리와의 일치를 얻기 위해 방향을 수정한다.우리는 M의 모든 가장자리가 팽팽하다는 불변성을 유지한다.M이 완벽한 짝이라면 우리는 끝장이다.

In a general step, let ${\displaystyle R_{S}\subseteq S}$ and ${\displaystyle R_{T}\subseteq T}$ be the vertices not covered by M (so ${\displaystyle R_{S}}$ consists of the vertices in S with no incoming edge and ${\displaystyle R_{$$T}}$은(는) 송신 에지가 없는 T의 정점으로 구성된다$$.${\displaystyle \stackrel{}{Z_{}}}$를 $G{\displaystyle \stackrel{}{{}_{}}}$ y →${\$displaystyle ${G_{y}}}}$에 도달 가능한 꼭지점 집합으로, 꽉 끼는 가장자리만 따라가는 방향 ${\displaystyle {경로}_{}}$를 통해$$ R S ${\$이것은 너비 우선 검색으로 계산할 수 있다.

If ${\displaystyle R_{T}\cap Z}$ is nonempty, then reverse the orientation of a directed path in ${\displaystyle {\overrightarrow {G_{y}}}}$ from ${\displaystyle R_{S}}$ to ${\displaystyle R_{T}}$. Thus the size of the corresponding matching increases by 1.

$R{\displaystyle {}_{}}$ ${\displaystyle T_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle Z}$ ${\displaystyle R_{T}\cap Z}$이(가) 비어 있는 경우

${\displaystyle \Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}.}$

Δ is well defined because at least one such edge ${\displaystyle ij}$ must exist whenever the matching is not yet of maximum possible size (see the following section); it is positive because there are no tight edges between ${\displaystyle Z\cap S}$ and ${\displaystyle T\setminus Z}$. Increase y by Δ on the vertice$Z{\displaystyle }$ ${\displaystyle \cap }$ ${\displaystyle S}$ ${\displaystyle$ Z$\cap S}$의 s와 ${\displaystyle Z}$ ${\displaystyle \cap }$ T ${\displaystyle Z\cap T}$의 정점에서 y Δ만큼 y를 감소시킨다$.$ 결과 y는 여전히 잠재성이며, 그래프 ${\displaystyle G_{}}$ y ${\$는 변경되지만$$ 여전히 M을 포함하고 있다(다음 하위 섹션 참조).우리는 새로운 가장자리 방향을 S에서 T로 맞춘다.Δ의 정의에 의해 R ${\displaystyle S_{}}$ ${\$에서 도달할 수 있는 정점의 설정 Z가 증가한다$$(긴축 에지 수가 반드시 증가하는 것은 아님).

우리는 M이 완벽한 매칭이 될 때까지 이러한 단계를 반복하며, 이 경우 최소 비용 할당을 제공한다.이 버전의 방법의 실행 시간은 $O{\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ 4${\displaystyle {}^{}}$) ${\displaystyle O(n^{4$ : M은 n번 증강되며, M이 변하지 않는 단계에서는 (Z가 매번 증가하기 때문에) 최대 n번의 잠재적 변화가 있다.잠재적인 변화에 충분한 시간은 $O{\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\displaystyle O(n^{2})}$ 입니다$.$

알고리즘이 진행 중이라는 증거

일치가 가능한 최대 크기가 아닌 한 알고리즘은 항상 진행 가능하다는 것을 보여주어야 한다. 즉, 일치된 에지의 수를 늘리거나 적어도 하나의 에지를 조일 수 있다.최소한 다음 중 하나가 모든 단계에서 유지됨을 보여 주는 것으로 충분하다.

• M은 가능한 최대 크기 입니다.
• ${\displaystyle G_{}}$ ${\displaystyle y_{}}$ ${\$에는 증강 경로가 포함되어 있다$$.
• G에는 느슨한 꼬리가 있는 경로: ${\displaystyle R_{}}$ $S{\displaystyle {}_{}}$ ${\$의 일부 꼭지점에서 $T{\displaystyle }$ ${\displaystyle \setminus }$ Z ${\displaystyle T\setminus$}의 꼭지점까지의$$ 경로로$$, 좁은 가장자리 숫자(아마도 0)와 느슨한 가장자리 하나로 구성된다.따라서 느슨한 꼬리가 있는 경로의 느슨한 가장자리는 Δ가 잘 정의되어 있음을 $보장하는$Z${\displaystyle z}$ S$${\$displaystyle Z\cap$ S$}$에서 온다.

만약 M이 가능한 최대 크기라면, 우리는 당연히 끝장이다.그렇지 않으면, Berge의 보조정리기에 의해, 기초 그래프 G에 M에 관한 증강경로 P가 존재해야 한다.However, this path may not exist in ${\displaystyle G_{y}}$: Although every even-numbered edge in P is tight by the definition of M, odd-numbered edges may be loose and thus absent from ${\displaystyle G_{y}}$. One endpoint of P is in ${\displaystyle R_{S}}$, the other in ${\displaystyle R_{$$T}$; w.l.o.g.${\displaystyle {가}_{}}$ R S$${\$displaystyle R_{S}$에서 시작된다고 가정해 봅시다$.$ P의 모든 가장자리가 꽉 끼면 ${\displaystyle {Gy}_{}}$ ${\$에서 증강 경로로 남아 있고, 우리는$$ 끝마쳤다.그렇지 않으면 ${\displaystyle u}$ v ${\displaystyle uv}$을(를) P의 첫 번째 느슨한 가장자리가 되게$$ 한다.$만약{\displaystyle }$ v ${\displaystyle \notin }$ ${\displaystyle Z}$ ${\displaystyle v\notin Z}$이(가) 있다면 우리는 느슨한 꼬리가 있는 경로를 찾았고 우리는 끝이다.Otherwise, v is reachable from some other path Q of tight edges from a vertex in ${\displaystyle R_{S}}$. Let ${\displaystyle P_{v}}$ be the subpath of P beginning at v and continuing to the end, and let ${\displaystyle P'}$ be the path formed by travelling along Q until a vertex on ${\displayst$$yle P_{v}}$ is reached, and then continuing to the end of ${\displaystyle P_{v}}$. Observe that ${\displaystyle P'}$ is an augmenting path in G with at least one fewer loose edge than P. P can be replaced with ${\displaystyle P'}$ and this reasoning process iterated (formally, using induction on the number of느슨한 가장자리)는 G ${\displaystyle y_{}}$ ${\$의 증축 경로 또는$$ G의 느슨한 꼬리가 발견될 때까지입니다.

전위 y를 조정하면 M이 변경되지 않는다는 증거

Y를 조정한 후에도 M의 모든 에지가 남아 있다는 것을 보여주기 위해, M의 임의 에지에 대해 두 끝점 모두 또는 둘 다 Z에 있지 않음을 보여주는 것으로 충분하다.이를 위해 $v{\displaystyle }$ ${\displaystyle u}$ ${\displaystylevu}$을(를) T에서 S까지의 M 에지로 설정하십시오$$.만약 v가 Z에 있다면 M의 모든 가장자리는 단단하기 때문에 너도 마찬가지일 것이라는 것을 쉽게 알 수 있다.Now suppose, toward contradiction, that ${\displaystyle u\in Z}$ but ${\displaystyle v\notin Z}$. u itself cannot be in ${\displaystyle R_{S}}$ because it is the endpoint of a matched edge, so there must be some directed path of tight edges from a vertex in ${\displaystyle R_{S}}$ to u.이 경로는 반드시 v를 피해야 하며, 이는 Z에 없는 가정이기 때문에 이 경로에서 u 바로 앞에 있는 정점 $v{\displaystyle {}^{}}$ ${\displaystyle \prime }$ ∈ ∈ ∈$$T {\$displaystyle v'\in$ T$\}.$${\displaystyle {}^{}}$v ${\displaystyle u}$u {\$displaystyle v$'$}$은 T에서 S까지 빡빡빡한 에지이므로$$ M에 있다.그러나 M에는 정점 u를 공유하는 두 개의 가장자리가 들어 있어 M이 일치한다는 사실과 모순된다.따라서 M의 모든 에지는 양쪽 끝점을 가지거나 Z에 끝점을 가지지 않는다.

당신이 잠재력을 가지고 있다는 증거

조정된 후에도 y가 잠재력을 유지한다는 것을 보여주기 위해, 비용 이상으로 증가된 총 잠재력을 가진 가장자리가 없다는 것을 보여주기에 충분하다.이는 앞 단락에 의해 M의 가장자리에 대해 이미 확립되었으므로 S에서 T까지의 임의의 가장자리 UV를 고려한다.If ${\displaystyle y(u)}$ is increased by Δ, then either ${\displaystyle v\in Z\cap T}$, in which case ${\displaystyle y(v)}$ is decreased by Δ, leaving the total potential of the edge unchanged, or ${\displaystyle v\in T\setminus Z}$, in which case the definition of Δ guarantees that $$${\displaystyle$$\Delta \leq c(u,v)}.$ 따라서 y는 잠재력으로 남아 있다$.$

행렬 해석

이 글은 독자들에게 혼란스럽거나 불명확할 수 있다.특히 이것은 예에 따라 알고리즘을 수행하지만, 행렬에 대한 실제 알고리즘은 이전에는 논의된 적이 없으며, 실제 알고리즘의 세부사항을 제공하지 않으며, 또한 최소 커버를 "그리기"하는 등의 모호한 접근법에 의존한다. 기사에 대해 명확하게 설명할 수 있도록 도와주십시오. 토크 페이지에서 이에 대한 논의가 있을 수 있다.(2019년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

n명의 작업자와 작업, 그리고 각 작업자를 작업에 할당하는 비용이 포함된 n×n 매트릭스를 주어진다면, 할당을 최소화하는 비용을 찾아라.

먼저 문제는 아래와 같이 행렬의 형태로 기재되어 있다.

a1	a2	a3	a4
b1	b2	b3	b4
c1	c2	c3	c4
d1	d2	d3	d4

여기서 a, b, c, d는 작업 1, 2, 3, 4를 수행해야 하는 근로자다. a1, a2, a3, a4는 작업자 "a"가 각각 1, 2, 3, 4를 할 때 발생하는 벌칙을 나타낸다.다른 기호들도 마찬가지다.매트릭스는 사각형이기 때문에 각 작업자는 하나의 작업만 수행할 수 있다.

1단계

그런 다음 매트릭스에서 행 연산을 수행한다.이를 위해 모든 a_i(i는 1-4에 속함) 중에서 가장 낮은 것을 취하여 그 행의 각 원소에서 뺀다.이렇게 하면 해당 행에서 최소 1개의 0이 발생할 것이다(이 행에서 가장 낮은 두 개의 동일한 원소가 있을 때 다중 0이 발생한다).이 절차는 모든 행에 반복된다.우리는 이제 적어도 한 줄에 0을 가진 행렬을 가지고 있다.

노동자가 n명이고 과제가 n명이기 때문에, 연속이나 열의 각 항목에 고정 숫자를 추가하거나 빼면 그 금액만큼 할당 비용이 변경될 뿐이지만, 오래된 가중치에 따른 최소 비용 배정은 새로운 가중치에 따른 최소 비용 할당으로 남을 것이다.

이제 우리는 각 에이전트가 한 가지 일만 하고 각각의 경우에 부과되는 벌칙은 0이 되도록 에이전트에게 업무를 할당하려고 한다.모든 체중은 음수가 아니기 때문에, 배정은 최소 비용이 될 것이다.이것은 아래에 설명되어 있다.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
c1'	0	c3'	c4'
d1'	d2'	0	d4'

0으로 표시된 0은 할당된 작업이다.

2단계

때때로 이 단계의 매트릭스는 아래 매트릭스의 경우와 같이 할당에 사용할 수 없다는 것이 밝혀질 수 있다.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

위의 경우, 어떠한 임무도 부여할 수 없다.작업 1은 에이전트 a와 c 둘 다에 의해 효율적으로 수행된다는 점에 유의하십시오.둘 다 같은 임무를 부여받을 수 없다.또한 아무도 3번 작업을 효율적으로 수행하지 않는다는 점에 유의하십시오.이를 극복하기 위해 모든 컬럼(즉, 각 컬럼의 최소 요소를 해당 컬럼의 모든 요소에서 빼는 것)에 대해 위의 절차를 반복한 후 할당이 가능한지 확인한다.

대부분의 상황에서 이것은 결과를 주겠지만, 만약 그것이 여전히 가능하지 않다면 우리는 계속 나아갈 필요가 있다.

3단계

행렬의 모든 0은 가능한 한 적은 행 및/또는 열을 표시하여 덮어야 한다.이를 위한 한 가지 방법은 다음과 같다.

첫째, 가능한 많은 작업을 할당한다.

• 1열은 0이 1개여서 배정된다.3열의 0은 같은 열에 있기 때문에 교차된다.
• 2열은 0이 1개여서 배정된다.
• 3열의 유일한 0번이 교차되어 아무것도 배정되지 않았다.
• 4열에는 0이 교차되지 않은 두 개가 있다.둘 중 하나를 배정할 수 있고, 그 다음 나머지 0은 교차된다.

또는 3열의 0을 할당하여 1열의 0을 대신 교차시킬 수 있다.

0'	a2'	a3'	a4'
b1'	b2'	b3'	0'
0	c2'	c3'	c4'
d1'	0'	0	d4'

이제 도면 부분까지.

• 할당이 없는 모든 행(3행)을 표시하십시오.
• 새로 표시된 행(열 1)에 모든 열에 0을 표시하십시오.
• 새로 표시된 열(1행)에 할당이 있는 모든 행을 표시하십시오.
• 새 행이나 열이 표시되지 않을 때까지 이전 2개의 글머리 기호에서 설명한 단계를 반복하십시오.

×
0'	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0	c2'	c3'	c4'	×
d1'	0'	0	d4'

이제 표시된 모든 열과 표시되지 않은 행에 선을 그으십시오.

×
0'	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0	c2'	c3'	c4'	×
d1'	0'	0	d4'

앞서 언급한 상세한 설명은 0을 모두 커버할 수 있는 최소 선 수를 그리는 한 가지 방법일 뿐이다.다른 방법들도 효과가 있다.

4단계

남은 요소에서 가장 낮은 값을 찾으십시오.표시되지 않은 모든 요소에서 이 요소를 빼서 두 개의 선으로 덮인 모든 요소에 추가하십시오.

이는 교차되지 않은 모든 행에서 숫자를 빼고 교차된 모든 열에 동일한 숫자를 추가하는 것과 같다.이러한 작업은 최적의 할당을 변경하지 않는다.

할당 가능할 때까지 3-4단계를 반복한다. 이는 0을 모두 커버하는 데 사용되는 최소 라인 수가 최소(인원 수, 할당 수)와 같을 때, 더미 변수(대개 최대 비용)가 할당 수보다 클 때 채우는 데 사용된다고 가정한다.

Kőnig의 정리로부터 최소 선 수(최소 정점 커버^[9])는 n(최대 일치의^[10] 크기)가 된다.^[8]따라서 n개의 라인이 필요할 때 매트릭스에서 0만 보면 최소 비용 할당이 가능하다.

참고 문헌 목록

• R.E. Burkard, M. Dell'Amico, S. Martello:할당 문제(재인쇄).2012년 필라델피아 SIAM. ISBN978-1-61197-222-1
• M. Fischetti, "Lezioni di Ricerca Operativa", Edizioni Libreria Progetto Padova, Italia, 1995.
• R. Ahuja, T. Magnanti, J. Orlin, "네트워크 흐름", 프렌티스 홀, 1993.
• S. 마르텔로 "제노 에거바리: 헝가리 알고리즘의 기원부터 위성 통신까지"2010년 중앙 유럽 학술지 운영 연구 18, 47–58,

참조

외부 링크

• Bruff, Derek, The Assignment Problem and Hergan Method (매트릭스 형식주의)
• Mordecai J. Golin, Butterpartite Matching and Hergan Method (빅그래프 형식주의), 코스 노트, 홍콩 과학기술 대학
• Brilliant 웹 사이트의 헝가리 최대 일치 알고리즘(두 형식 모두).
• R. A. Pilgright, Munkres의 할당 알고리즘. 직사각형 행렬, 코스 노트, Murray State University에서 수정.
• Mike Dawes, The Optimal Assignment Problem, Course notes, Western Ontario University of Western Otherio.
• 쿤의 헝가리 방식 – 헝가리의 안드라스 프랑크, 에거바리 연구 그룹, 파즈만 P. 세터너리 1/C, H1117, 헝가리 부다페스트.
• 강의:운영 연구의 기초 - 과제 문제 - 헝가리 알고리즘, 교수IIT 마드라스 경영학과 G. 스리니바산.
• 확장:과제 민감도 분석(O(n^4) 시간 복잡성), 류, 쉘.
• 온라인으로 모든 할당 문제를 해결하여 헝가리 알고리즘에 대한 단계별 설명을 제공하십시오.

구현

이러한 모든 것이 $O{\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})}$시간의$$ 복잡성을 만족하지는 않는다는 점에 유의하십시오.일부는 오류를 포함하거나, $더{\displaystyle }$ 느린 O${\displaystyle ({}^{}}$ ${\displaystyle {4\mathrm{}}^{}}$) ${\displaystyle O(n^{4})$ 알고리즘을$$ 구현하거나, 다른 비효율성을 가질 수 있다.최악의 경우, 위키피디아에서 연결된 코드 예는 나중에 취약성 코드를 포함하도록 수정될 수 있다.무명 저자의 그러한 코드 사례를 이용할 때 검증과 벤치마킹이 필요하다.

• 줄리아 실행
• C 구현 클레임 $O{\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})}$ 시간$$ 복잡성
• Java 구현 클레임 $O{\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3}})$ 시간$$ 복잡성
• Matlab 구현 시 $O{\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})}$ 시간$$ 복잡성(공용 도메인)
• 파이썬 구현
• 단위 테스트를 통한 Ruby 구현
• C# 구현 클레임 $O{\displaystyle }$( ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})}$ 시간$$ 복잡성
• 단위 테스트를 사용한 D 구현($O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})$를 클레임하는 Java 버전의 포트$)$ )
• 온라인 대화형 구현
• 직렬 및 병렬 구현.
• 매트랩과 C
• 펄 구현
• C++ 구현
• $C{\displaystyle }$++ 구현 클레임 O${\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3})}$ 시간$$ 복잡성(BSD 스타일 오픈 소스 라이센스)
• MATLAB 구현
• C 구현
• 단위 테스트를 통한 JavaScript 구현($O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\displaystyle O(n^{3}})$ 시간$$ 복잡성을 주장하는 Java 버전의 포트)
• R 단서 패키지가 구현을 제안함, 해결_LSAP
• GitHub에서 Node.js 구현
• Scipy 패키지로 Python 구현