홀드-카프 알고리즘

홀드-카프 알고리즘(Bellman-karp)이라고도 함Held–Karp 알고리즘은 역동적인 프로그래밍 알고리즘 1962년에 독립적으로 Bellman[1]과 헬드와 Karp[2]에 의해로 도시에 대한 집합 간의 입력은 거리 매트릭스를 방문 외판원 문제(TSP),를 해결하기 위해 제안된, 그리고 그 목표가 일단 정확히 말하자면 시동으로 돌아오기 전에 각 도시를 방문하는minimum-length 여행을 찾는 것이다.지점그것은 이 문제와 해밀턴 사이클 문제를 포함한 몇 가지 관련 문제들에 대한 정확한 해결책을 기하급수적으로 시간에 찾아낸다.

알고리즘 설명 및 동기 부여

$1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$이(가) 임의로 "시작" 도시로 지정된$$ $상태$로 1,${\displaystyle 2}$,${\displaystyle }$n ${\displaystyle$ 1,$2,\ldots ,n$ 도시에 번호를 매긴다(TSP에 대한 해결책이 사이클이기 때문에 시작 도시의 선택은 중요하지 않다).The Held–Karp algorithm begins by calculating, for each set of cities ${\displaystyle S\subseteq \{2,\ldots ,n\}}$ and every city ${\displaystyle e\neq 1}$ not contained in ${\displaystyle S}$, the shortest one-way path from ${\displaystyle 1}$ to ${\displaystyle e}$ that passes through e$[\displaystyle S}$의 매우 도시(다른 도시에서는 제외됨)Denote this distance ${\displaystyle g(S,e)}$, and write ${\displaystyle d(u,v)}$ for the length of the direct edge from ${\displaystyle u}$ to ${\displaystyle v}$. We'll compute values of ${\displaystyle g(S,e)}$ starting with the smallest sets ${\displaystyle S}$ and f가장 큰 것들과 함께 하는

$S{\displaystyle }$ ${\displaystyle S}$이(가) 둘 이하인 경우 $g{\displaystyle (S}$ ,${\displaystyle e}$ )$${\$displaystyle g(S,e)}$을(를) 계산하려면 하나 또는 두 개의 가능한 최단 경로를 확인해야 한다$$.For example, ${\displaystyle g(\emptyset ,e)}$ is simply ${\displaystyle d(1,e)}$, and ${\displaystyle g(\{2\},3)}$ is just the length of ${\displaystyle 1\rightarrow 2\rightarrow 3}$. Likewise, ${\displaystyle g(\{2,3\},4)}$ is the length of either${\displaystyle 1}$→ ${\displaystyle 2}$→ ${\displaystyle 3}$→ 4 $[\displaystyle 1\rightarrow 2\rightarrow 3}$ 또는$$ $1{\displaystyle \mathrm{}}$→ 3${\displaystyle }$→ 2${\displaystyle }$→$$ [\$displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$중 더 짧은 것이 특징이다.

$일단{\displaystyle }$ S ${\displaystyle S}$에 3개 이상의 도시가 포함되면 $S{\displaystyle }$ ${\displaystyle S}$을 통과하는 경로의 수는 빠르게 증가하지만$$, 그러한 경로의 몇 개만 검사하면 가장 짧은 도시를 찾을 수 있다.For instance, if ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4}$ is shorter than ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4}$, then ${\displaystyle 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5}$ must be shorter than ${\displayst$$yle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$, and the length of ${\displaystyle 1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5}$ is not a possible value of ${\displaystyle g(\{2,3,4\},5)}$. Similarly, if the shortest path from ${\displaystyle 1}$ through ${\displaystyle \{2,}$${\displaystyle \{2,3,4\}}$ to ${\displaystyle 5}$ is ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5}$, and the shortest path from ${\displaystyle 1}$ through ${\displaystyle \{2,3,4,5\}}$ to ${\displaystyle 6}$ ends with the edge ${\$$displaystyle 5\rightarrow 6}$, then the whole path from ${\displaystyle 1}$ to ${\displaystyle 6}$ must be ${\displaystyle 1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 6}$, and not any of the other five paths created by visiting ${\displaystyle \{2,3,4\}}$ in a dif격조 높은 질서

보다 일반적으로 $S{\displaystyle }$=${\displaystyle }${ ${\displaystyle {s\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, s ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ S$=\{s_{1},\ldots ,s_{k}\}}}}$이(가) k ${\displaystyle k}$ 도시의$$ 집합이라고 가정하자.For every integer ${\displaystyle 1\leq i\leq k}$, write ${\displaystyle S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}}$ for the set created by removing ${\displaystyle s_{i}}$ from ${\displa$$ystyle$ $S$$\}.$ 그런 $다음{\displaystyle \mathrm{}}$ 1$${\$displaystyle$ $S$$}$에서 S$${\$displaystyle$ S$}$까지 가는 최단 $경로$에 ${\displaystyle s_{}}$ i ${\$$displaystyle$ $s_{i$$}$가 두 번째에서 $마지막$인 도시인 경우$$ 이 경로에서 최종 가장 짧은 경로를 ${\displaystyle {제거}_{}}$해야 $한다$$.$$}}}$ ~ ${\displaystyle S_{}}$ $i{\displaystyle {}_{}}$ ${\$즉$$, $길이{\displaystyle \mathrm{}}$ $g{\displaystyle ({Si}_{}}$, s ${\displaystyle i_{}}$)${\displaystyle }$+ ${\displaystyle d(}$ ${\displaystyle s}$ , ${\displaystyle e_{}}$) ${\displaystyle g_${i$}$$에 대해$ 각각 가능한 2 ~ $마지막{\displaystyle }$ 도시의 ${\displaystyle i_{}}$ ${\$에 $대해{\displaystyle }$ 1 ${\$$displaystyle$ k}에서$$e {\$displaystystyle$ s}까지의$$최단 경로만 있을 수 있다$$$.$$)+d(s_{i},e)}$ 및$$$g{\displaystyle (S,}$ e${\displaystyle }$)${\displaystyle }$= ${\displaystyle \underset{}{min}}$ ${\displaystyle \underset{}{1\mathrm{}}}$ ${\displaystyle \underset{}{\le }}$ ${\displaystyle \underset{}{i}}$ ${\displaystyle \underset{}{\le }}$ ${\displaystyle \underset{}{}}$ g ${\displaystyle ({}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle s}$ i${\displaystyle {}_{}}$)${\displaystyle }$+ d${\displaystyle }$( s ${\displaystyle i_{}}$, ${\displaystyle e}$) = ${\displaysty g(S,e)=\min _{1\leq i,s_{i$}}$g(S_${i})+$d$$s_{i}e}.$

This stage of the algorithm finishes when ${\displaystyle g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)}$ is known for every integer ${\displaystyle 2\leq i\leq n}$, giving the shortest distance from city ${\displaystyle 1}$ to city ${\displaystyle i}$ that passes through every 다른 도시.훨씬 짧은 두 번째 단계는 이러한 거리를 가장자리 길이 $d{\displaystyle (i}$, ${\displaystyle 1}$) ${\displaystyle d(i,1)$에 추가하여$$ ${\displaystyle \mathrm{n}}$- 1 ${\displaystyle n-1}$의 가능한 최단 주기를 부여한 다음 가장 짧은 거리를 찾는다.

마지막으로 가장 짧은 경로 자체(${\displaystyle \mathrm{길이}}$뿐만 아니라$)$는 $S{\displaystyle }$${\displaystyle }$${\displaystyle 1}$에서$S$ ${\displaystyle S}$을$($를$)$ 통해 e {\$displaystyle e}$까지의 경로에 두 번째에서 마지막 $도시$의 라벨을$나란히{\displaystyle }$ 저장하여 공간 요구사항을 일정한 요인만 증가시킴으로써 재구성할 수 있다.

알고리즘 복잡성

Hold-Karp 알고리즘은 시간 $복잡성{\displaystyle \mathrm{}}$ ${\displaystyle (}$ (${\displaystyle {2n\mathrm{}}^{}}$2 $){\displaystyle \Theta (2^{n}n^{2})$를 가지는데$,$ 이는 흉물-강력 알고리즘의$$ 초경량 성능 $\theta {\displaystyle \mathrm{}}$(${\displaystyle n!)}$ ${\displaysty \Teta (n!)}$보다 상당히 나은 것이다.그러나 홀드-Karp는 함수 $g{\displaystyle (S}$, e )$${\$displaystyle$ $\Theta$$($$n2$^{$n$$\})$의 모든 계산 값을 보유하려면 $\theta {\displaystyle \mathrm{}(}$${\displaystyle \mathrm{n2}}$$^{n})$ 공간이$$ 필요한 반면, 과격력은 그래프 자체를 $저장$하려면 ${\displaystyle (({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaysty \Theta(n^{2})$ 공간만$$ 필요하다.

시간

Computing one value of ${\displaystyle g(S,e)}$ for a ${\displaystyle k}$-element subset ${\displaystyle S}$ of ${\displaystyle \{2,\ldots ,n\}}$ requires finding the shortest of ${\displaystyle k}$ possible paths, each found by adding a known value of ${\displaystyle g}$ and anedge length from the original graph; that is, it requires time proportional to ${\displaystyle k}$. There are ${\textstyle {\binom {n-1}{k}}}$ ${\displaystyle k}$-element subsets of ${\displaystyle \{2,\ldots ,n\}}$; and each subset gives ${\displaystyle n-k-1}$ possible values of ${\displaystyle e}$. Computing all values of ${\displaystyle g(S,e)}$ where ${\displaystyle S =k}$ thus requires time ${\textstyle k(n-k-1){\binom {n-1}{k}}=(n-1)(n-2){\binom {n-3}{k-1}}}$, for a total time across all subset sizes ${\textstyle (n-1)(n-2)\sum _{k=1}^{n-2}{\binom {n-3}{k-1}}=(n-1)(n-2)2^{n-3}=\$$Theta(n^{2}2^{n}})}$.알고리즘의 두 번째 ${\displaystyle \mathrm{단계}}$는 $n{\displaystyle }$- 1 ${\displaystyle n-1}$ 후보로부터$$ 완전한 주기를 찾는 $것$으로 ,${\displaystyle }$(${\displaystyle n}$) ${\displaystyle \Teta (n)}$시간이$$ 소요되며 점증상 성능에 영향을 주지 않는다.

공간

Storing all values of ${\displaystyle g(S,e)}$ for subsets of size ${\displaystyle k}$ requires keeping ${\textstyle (n-k-1){\binom {n-1}{k}}=(n-1){\binom {n-2}{k}}}$ values.A complete table of values of ${\displaystyle g(S,e)}$ thus requires space ${\textstyle \sum _{k=0}^{n-2}(n-1){\binom {n-2}{k}}=(n-1)2^{n}=\$$세타(n2^{n})}$.

사이클 자체가 아니라 최단 사이클의 길이만 필요한 경우, $크기{\displaystyle }$ k ${\displaystyle k}$의 S ${\displaystyle$ g}에 $대해$ g${\displaystyle }$(${\displaystyle S}$, e${\displaystyle }$) ${\displaystyle g}$을(를$)$ 계산하려면$$ $k{\displaystyle }$- ${\displaystyle 1}$의$$부분 집합에 대해$$ $g{\displaystyle }$ ${\$$displaystyle$ $g}$ 값만 필요하다는 점에 유의하여 공간 복잡성을 다소 개선할 수 있다.$playstyle k-1}$. Keeping only the ${\textstyle (n-1)\left[{\binom {n-2}{k-1}}+{\binom {n-2}{k}}\right]}$ values of ${\displaystyle g(S,e)}$ where ${\displaystyle S}$ has size either ${\displaystyle k-1}$ or ${\displaystyle k$$}}$은(는$)$ $k$= $\lfloor n\frac{}{}$ $\frac{2}{}$ $\rfloor$ ${\$ k$=\left\lfloor {\frac{n}{2}}\$$right$$\rfloor$ $}}$일 때 얻어진 알고리즘의 최대 공간 요구사항을 $reduces$(n 2n ${\displaystyle {}^{}}$로 줄인다$.$

예^[3]

거리 행렬:

${\displaystyle C={\begin{pmatrix}0&2&9&10\\1&0&6&4\\15&7&0&8\6&3&12&#end{pmatrix}}}}$

함수 설명:

• g(x, S) - 1, path min cost가 꼭지점 x에서 끝나기 때문에 S 세트의 정점을 정확히 한 번 통과
• c_xy - y에서 x로 끝나는 에지 비용
• p(x, S) - 세트 S에서 x까지의 두 번째에서 마지막 정점.끝에서 뒤로 TSP 경로를 구성하는 데 사용된다.

k = 0, null 집합:

∅ 설정:

g21(2, ∅) = c = 1 g(3, ∅) = c31 = 15 g(4, ∅) = c = 641

k = 1, 원소의 집합 고려:

{2} 설정:

g(3,{2}) = c32 + g(2, ∅ ) = c21 = 732 + 1 = 8 p(3,{2}) = 2 g(4,{2}) = 2 g(2, ∅ ) = c424221 = 3 + 1 = 4 p(4,{2}) = 2

{3} 설정:

g23(2,{3}) = c + g(3, ∅ ) = c = 623 + 1531 = 21 p(2,{3}) = 3 g(4,{3}) = 3 g(3, }) ) = c4343 = 12 + 1531 = 27 p(4,{3}) = 3

{4} 설정:

g24(2,{4}) = c + g(4, ∅ ) = c = 424 + 641 = 10 p(2,{4}) = 4 g(3,{4} = 4 g(3,{4}) = c34 + g41(4, ∅ ) = c34 = 8 + 6 = 14 p(3,{4}) = 4

k = 2, 다음 두 요소의 집합을 고려하십시오.

{2,3} 설정:

g(4,{2,3}) = 최소 {c42 + g(2,{3}), c43 + g(3,{2}}} = 최소 {3+21, 12+8}= 최소 {24, 20}= 20p(4,{2,3}) = 3

{2,4} 설정:

g(3,{2,4}) = 최소 {c32 + g(2,{4}), c34 + g(4,{2}}) = 최소 {7+10, 8+4} = 최소 {17, 12} = 12p(3,{2,4}) = 4

{3,4} 설정:

g(2,{3,4}) = 최소 {c23 + g(3,{4}), c24 + g(4,{3}}} = 최소 {6+14, 4+27}= 최소 {20, 31}= 20p(2,{3,4}) = 3

최적 둘러보기 길이:

f = g(1,{2,3,4}) = 최소 {c12 + g(2,{3,4}), c1314 + g(3,{2,4}), c + g(4,{2,3}) } = 최소 {2 + 20, 9 + 12, 10 + 20} = 최소 {22, 21, 30} = 21 = 21 = 21 = 21 = 21 = 21 = 21 = 21

노드 1의 이전 버전: p(1,{2,3,4}) = 3

노드 3의 이전 버전: p(3, {2,4}) = 4

노드 4의 이전 버전: p(4, {2}) = 2

노드 2의 이전 버전: p(2, {}) = 1

따라서 최적의 TSP 투어는 1 → 3 → 4 → 2 → 1로 주어진다.

가성음^[4]

function algorithm TSP (G, n) is for k := 2 to n do         g({k}, k) := d(1, k)     end for for s := 2 to n−1 do for all S ⊆ {2, ..., n},  S  = s do for all k ∈ S do                 g(S, k) := minm≠k,m∈S [g(S\{k}, m) + d(m, k)]             end for end for end for      opt := mink≠1 [g({2, 3, ..., n}, k) + d(k, 1)]     return (opt) end function

관련 알고리즘

TSP를 해결하기 위한 정확한 알고리즘

동적 프로그래밍 외에도 선형 프로그래밍과 분기 및 바운드는 TSP에 대한 정확한 솔루션에도 사용되는 설계 패턴이다.선형 프로그래밍은 절삭면 방법을 정수 프로그래밍에 적용하는데, 즉 모델의 두 제약조건에 의해 형성된 LP를 푼 다음, 불평등 제약조건을 추가하여 절삭면을 추구하여 점차 최적의 해법으로 수렴한다.절단면을 찾기 위해 이 방법을 적용할 때 경험에 의존하는 경우가 많아 일반적인 방법으로 사용하는 경우는 드물다.

나뭇가지와 바운드라는 용어는 리틀 등이 TSP에 발표한 논문에서 1963년에 처음 사용되었는데, 정확한 해결책을 위한 실질적인 적용 범위를 확대하기 위해 더 작은 검색 공간을 결합하고 하한을 설정하는 기법을 기술하였다.이 기술은 계산적으로 고려될 수 있는 도시의 수를 확대하는 데 유용하지만, 여전히 대규모 데이터 집합에서 분해된다.

제한적 경계를 적용해 검색 프로세스를 제어해 공간 상태 트리에서 최적의 솔루션 분기를 검색해 최대한 신속하게 최적의 솔루션을 찾을 수 있도록 했다.이 알고리즘의 핵심 요소는 제한적 경계선 선택이다.서로 다른 제한적 경계가 다른 분기 바인딩 알고리즘을 형성할 수 있다.

TSP 해결을 위한 대략적인 알고리즘

문제를 해결하기 위한 정밀 알고리즘의 적용이 매우 제한적이기 때문에 근사 알고리즘이나 휴리스틱 알고리즘을 사용하는 경우가 많다.알고리즘 결과는 C / C* ≤ ε으로 평가할 수 있다. C는 근사 알고리즘에서 생성된 총 이동 거리, C*는 최적 이동 거리, ε은 최악의 조건에서 최적 솔루션에 대한 근사 용액의 총 이동 거리 비율에 대한 상한이다.ε >1.0의 값.1.0에 가까울수록 알고리즘이 좋다.이러한 알고리즘에는 다음이 포함된다.보간 알고리즘, 가장 가까운 이웃 알고리즘, Clark & Wright 알고리즘, 더블 스패닝 트리 알고리즘, Christofides 알고리즘, Hybrid 알고리즘, 확률론 알고리즘(예: 시뮬레이션 어닐링)

참조