이 질문은 실제로 one과 같은 문구를 나타냅니다. 당신은 N 노드와 K과 완벽한 무향 그래프를 부여"금지 된"가장자리를 사용하지 않는 해밀턴 사이클의 수는 어떻게 찾습니까?
"금지"가장자리 다음 code jam problem는 다음과 같습니다. N = 300 <, K = 15 < 는 K "금지"에지들 중 하나를 사용하지 않는 그래프 해밀 토니안 사이클 수를 찾는다.
O(2^N*N^2)의 간단한 DP 접근법은 그러한 경우에 작동하지 않습니다. N. solutions의 우승상은 O(2^K)입니다. 아무도이 문제를 해결하는 방법을 알고 있습니까?
금지 된 가장자리의 각 하위 집합 S에 대해 얼마나 많은 해밀턴 사이클이 있는지, S의 모든 에지를 사용하는지 알아 보겠습니다.이 하위 작업을 해결하면 inclusion-exclusion formula으로 문제를 해결할 수 있습니다.
이제 하위 작업을 어떻게 해결할 수 있습니까? S의 모든 모서리를 그려 봅시다. degree가 2보다 큰 버텍스가 존재한다면 분명히 사이클을 완료 할 수없고 대답은 0입니다. 그렇지 않으면 그래프가 연결된 구성 요소로 나뉩니다. 각 구성 요소는 하나의 정점, 사이클 또는 단순 경로입니다.
주기가 있으면 모든 꼭지점을 통과해야합니다. 그렇지 않으면 해밀턴 순환을 완료 할 수 없습니다. 이 경우, 응답이 2 인 (싸이클 2 개 방향으로 이송 될 수있다.) 그렇지 않으면, 응답은 C 경로 및 K 단독 정점이 때, 나머지 경우는 0
이다. 해밀턴 사이클을 완료하려면 각 경로의 방향 (2^ 방법)을 선택하고 구성 요소의 순서를 선택해야합니다. c + k 구성 요소가 있으므로 (c + k)로 다시 정렬 할 수 있습니다. 방법. 그러나 우리는 순환에 관심이 있습니다. 그래서 우리는 순환 이동에 의해 서로 차례가되는 순서를 구별하지 않습니다. (So (1,2,3), (2,3,1)과 (3,1,2)는 동일합니다.) 대답은 이동 횟수 (c + k)로 나누어야 함을 의미합니다. 따라서 서브 타스크에 대한 답은 2^c (c + k-1)입니다!.
이 아이디어는 bmerry의 솔루션 (매우 깨끗한 코드, btw)에서 구현됩니다.
해밀 토니안 사이클 문제 세일즈맨 문제 주행 특수한 경우 (그들이 그렇지 인접 무한대 인 경우 한정된 상수 두 도시 사이의 거리를 설정하여 수득한다.)
이러한 NP 완료 문제는 간단한 단어에 어떤 그들에 대한 빠른 해결책이 없다는 것을 의미합니다.
해밀턴 경로를 찾기위한 사소한 발견 적 알고리즘은 경로 abc ...을 만들고 더 이상 가능하지 않을 때까지 확장하는 것입니다. z의 모든 이웃이 이미 경로에 있기 때문에 abc ... xyz 경로를 더 이상 확장 할 수 없으면 하나의 단계로 돌아가서 yz의 가장자리를 제거하고 y의 다른 이웃으로 경로를 확장합니다. 선택 사항이 해밀턴 경로를 생성하지 않으면, 한 걸음 더 뒤로 물러나고, 가장자리 xy를 제거하고, x의 다른 이웃으로 경로를 확장하는 등의 작업을 수행합니다.이 알고리즘은 분명히 해밀턴 경로 (있는 경우)를 찾지 만 지수 시간에 실행됩니다. 대한
더 Cormen
어떤 의미에서 TSP는 해밀 토니안주기 문제와 동일하지 않습니다. TSP는 최적화 문제이며 대부분의 경우 전체 그래프라고 가정합니다. 즉, 모든 정점에서 다른 정점으로 이동할 수 있습니다. Hamiltionian Cycle 문제는 결정 문제이며 일반적으로 완료되지 않은 그래프에 있습니다. – starflyer
에 의해 "Algos 소개"의 NP 완전 문제 장을 왜 bmerry의 솔루션의 코드의 끝에 2분의 9,901에 의해 곱셈이 확인? "(x * w/2) mod w"는 무엇을 제공합니까? –