최근의 질문 은 Bellman 과 Held-Karp 와 독립적으로 인해 TSP에 대한 현재 고전적인 동적 프로그래밍 알고리즘에 대해 논의했습니다 . 알고리즘은 보편적 으로 시간 으로 실행되는 것으로보고됩니다 . 그러나 최근에 한 학생이 지적했듯이이 러닝 타임에는 불합리하게 강력한 계산 모델이 필요할 수 있습니다.O(2nn2)

$O(2^n{n}^2)$

$O(2^n n^2)$

다음은 알고리즘에 대한 간략한 설명입니다. 입력 값은 개의 꼭짓점이 있고 음이 아닌 길이 함수 를 갖는 유 방향 그래프 로 구성 됩니다. 임의의 정점 과 , 어떤 부분 집합 X 제외 것을 정점 들 및 t는 ,하자 L (들, X, t)가 최단 해밀턴 경로의 길이를 나타낸다 들 에 t 유도 서브 그래프에서 G [X \ 컵 \ {s, t \}] . Bellman-Held-Karp 알고리즘은 다음과 같은 되풀이를 기반으로합니다 (또는 경제학자 및 제어 이론가로서 “Bellman의 방정식”이라고 함).n ℓ : E → R + s t X s t L ( s , X , t ) s t G [ X ∪ { s , t } ]G=(V,E)

$G=(V,E)$

$G=(V,E)$n

$n$

$n$ℓ:E→R+

$\ell :E\to {\mathbb{R}}^{+}$

$\ell\colon E\to\mathbb{R}^+$s

$s$

$s$t

$t$

$t$X

$X$

$X$s

$s$

$s$t

$t$

$t$L(s,X,t)

$L(s,X,t)$

$L(s,X,t)$s

$s$

$s$t

$t$

$t$G[X∪{s,t}]

$G[X\cup \{s,t\}]$

$G[X\cup\{s,t\}]$

$$L(s,X,t) = \begin{cases} \ell(s,t) & \text{if $X = \varnothing_{\strut} $} \\ \min_{v\in X}~ \big(L(s, X\setminus\lbrace v\rbrace, v) + \ell(v,t)\big) & \text{otherwise} \end{cases}$$

정점 s

$s$

$s$ 경우 최적의 여행 세일즈맨 투어의 길이는 L(s,V∖{s},s)

$L(s,V\setminus \{s\},s)$

$L(s,V\setminus\{s\}, s)$ 입니다. 첫 번째 매개 변수 s

$s$

$s$ 는 모든 재귀 호출에서 일정 하기 때문에 Θ(2nn)

$\mathrm{\Theta }(2^{n}n)$

$\Theta(2^n n)$ 다른 하위 문제가 있으며 각 하위 문제는 최대 n

$n$

$n$ 다른 문제에 따라 달라집니다 . 따라서 동적 프로그래밍 알고리즘은 O(2nn2)

$O(2^n{n}^2)$

$O(2^n n^2)$ 시간에 실행됩니다.

아니면합니까?!

표준 정수 RAM 모델은 O(logn)

$O(\log n)$

$O(\log n)$ 비트를 사용하여 정수의 상수 시간 조작을 허용 하지만, 적어도 산술 및 논리 연산의 경우 더 큰 정수는 워드 크기의 청크로 나눠야합니다. (그렇지 않으면 이상한 일 이 발생할 수 있습니다.) 더 긴 메모리 주소에 대한 액세스도 마찬가지입니까? 알고리즘이 초 다항식 공간을 사용하는 경우 메모리 액세스에 일정한 시간 만 필요하다고 가정하는 것이 합리적입니까?

특히 벨만 – 보류 – 카프 알고리즘, 알고리즘은 서브셋의 설명 변환해야 X

$X$

$X$ 서브 세트의 설명에 X∖{v}

$X\setminus \{v\}$

$X\setminus\{v\}$ 각각에 대한 v

$v$

$v$ , 순서대로 액세스의 메모이 제이션 테이블. 서브 세트가 정수로 표현되는 경우, 이들 정수는 n

$n$

$n$ 비트를 요구 하므로 일정한 시간에 조작 될 수 없다; 정수로 나타내지 않으면 메모 테이블에 대한 인덱스로 직접 표현을 사용할 수 없습니다.

그래서 : 벨만 – 개최 – 카프 알고리즘의 실제 점근 실행 시간은?

---

---

답변