해밀턴 경로 파인더 구현 테스트

Question

나는 유향 그래프에서 최적의 해밀턴 경로를 찾는 알고리즘을 구현 중이다. 합리적으로 잘 작동하는 알고리즘을 구현했지만 일부 경우에는 미묘한 버그 나 다른 문제가 있는지 확실하지 않습니다. 따라서 해결책이 알려진 여러 네트워크가 필요합니다. 구현이 해결해야하는지 확인해야합니다.

위키 피 디아는 해밀턴 경로가 무향 그래프에 적합한 용어 일 뿐이므로 "해밀턴 경로"는 지정된 네트워크에서 모든 노드를 한 번 정확하게 한 번 방문하는 경로를 의미한다고 가정합니다.

모든 연결 (또는 "가장자리")에 양의 정수 값 (또는 길이)이 있다고 가정 할 수 있습니다. 어떤 노드도 그 자신에 연결되어 있지 않다고 가정 할 수 있으며, 어떤 두 노드 사이에 각 방향으로 하나의 가장자리 만있을 수 있습니다.

나는 전체 길이가 가장 긴 경로에 관심이 있기 때문에 "최적"은 가장 길다는 것을 의미합니다. 단, 가장 짧은 총 길이 (기존 TSP 에서처럼)를 원하는 경우에는 거의 차이가 없습니다. 나는 또한 욕심 많은 알고리즘을 사용하고있다.

TSP가 해결 된 감독 네트워크는 어디에서 어떻게 얻을 수 있습니까? 실제 솔루션과 욕심 많은 (또는 다른 발견 적) 솔루션을 사용할 수 있다면 더 좋을 것입니다. 네트워크는 유익한 테스트를 위해 충분히 커야하지만 솔루션을 수동으로 확인하기에 충분히 작아야합니다 (솔루션이 처음에는 알려지지 않은 경우). 그들은 "쉬운"네트워크와 "문제가있는"네트워크를 모두 망라할만큼 위상 적으로 다양해야합니다.

다른 사람이 찾고있는 경우; 내가 가지고있는 최선의 네트워크는 다음과 같습니다.

A B C D E 
A 0 1 2 0 1 
B 1 0 0 0 1 
C 0 3 0 1 2 
D 4 0 0 0 0 
E 1 0 0 2 0 

이 인접 목록은 행의 출처이며 열은 대상입니다. 숫자는 각 가장자리의 길이이고, 0은 "가장자리 없음"을 나타냅니다. 예를 들어,도 4 (A)에 D 의 가장자리의 길이는 4 인 것을 나타내고, D 에 (세로 0)에서 아무런 관련이 없다.

이 네트워크의 최대 길이 경로는 E-> D-> A-> C-> B입니다. 전체 길이는 2 + 3 + 3 + 3 = 11입니다. 나는 욕심 많은 알고리즘이이 경우에 가장 좋은 해결책을 찾을 수 있다고 믿으며 그것이 최선의 해결책이라는 것을 분명히 알 수 있습니다.

Answer 1

해밀턴 경로에서 위키 항목을 읽었을 때 해밀턴 경로를 찾는 것이 NP 하드임을 알아야합니다 (정확히 말하면 해결하려는 것은 TSP이지만 그다지 변하지 않습니다). 그 하나의 사실은 욕심 많은 알고리즘이 문제에 대한 최적의 솔루션을 제공하지 않는다는 것을 암시합니다.

당신의 욕심이 알고리즘은 값/길이를 내림차순으로 정렬 모서리

테이크, 그것은

(a)가 생성

하지 않는

가, 경로 - 인 - 건설에 테두리를 추가처럼 작동하는 경우 사이클

(b) 경로 인 - 건설 = 3 ℃에서의 노드를 생성

최적의 경로 인 반면,

A B C D E F 
A 0 5 4 0 0 0 
B 5 0 5 0 4 0 
C 4 5 0 1 0 0 
D 0 0 1 0 5 4 
E 0 4 0 5 0 5 
F 0 0 0 4 5 0 

욕심 알고리즘 (21)의 총 길이 ABCDEF 경로를 찾습니다 그렇지 않으면

여기에 나는 탐욕이 실패하게 위치를 생각할 수있는 최소한의 카운터 예제 건너 뛰기 총 길이가 22 인 ACBEDF (동일한 길이의 더 많은 것이 있습니다).

알고리즘이 다르게 작동하는 경우이 예제에서는 제대로 작동하지만, 욕심이 많으면 반대 사례가 계속있을 수 있습니다. 그럴 경우에 코드를 게시하고 관심이 있습니다.