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

O(2nn2)

다음은 알고리즘에 대한 간략한 설명입니다. 입력 값은 개의 꼭짓점이 있고 음이 아닌 길이 함수 를 갖는 유 방향 그래프 로 구성 됩니다. 임의의 정점 과 , 어떤 부분 집합 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)

n

n

ℓ:E→R+

ℓ:E→R+

s

s

t

t

X

X

s

s

t

t

L(s,X,t)

L(s,X,t)

s

s

t

t

G[X∪{s,t}]

G[X∪{s,t}]

정점 s

s

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

L(s,V∖{s},s)

입니다. 첫 번째 매개 변수 s

s

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

Θ(2nn)

다른 하위 문제가 있으며 각 하위 문제는 최대 n

n

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

O(2nn2)

시간에 실행됩니다.

아니면합니까?!

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

O(log⁡n)

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

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

X

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

X∖{v}

각각에 대한 v

v

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

n

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

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

---

---

답변