외판원 변형

Question

는 세일즈맨 문제, 또는 다음의 문제에 대한 다른 알고리즘 여행의 변형은인가. V는 G.

의 정점의 하위 집합입니다

V.

각각 두 정점 감사 사이에 최소한의 무게가 V 따라 간단한 폐쇄 회로 (및 G의 아마 다른 정점)를 찾는 방법

---------------------- 편집 ----------------------- -

이 문제에 대한 이름이나 게시 된 문서 또는 관련 연구 논문이 있습니까?

Answer 1

먼저, (만약 상태로서 G의 정점의 일부 임) V는 자체 가중 그래프 때문에 -는 예를 들어, G의 입력 G.

를 무시할 수 있도록 제 V의 가장자리 계산을 :

G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb) 

는 V의 입력을 간소화 할 수 있습니다 : 당신이 입력이 V의 정점 사이에 여러 경로가있을 때

이

Va -- 15 meter --> Vb 

재미가 시작 (다른 V의 정점에 사이 S)

G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb) 
G1 (Va) -- 7 meter --> G4 (no V) -- 7 meter --> G3 (Vb) 

나서 단순화 형태 (그 두 번째 행 소요)이다

Va -- 14 meter --> Vb 

사용 익스트라 알고리즘이 단순화 동안.

둘째, V에서 좋은 TSP 알고리즘을 적용합니다. 완벽한 알고리즘이므로 NP 완료입니다. 프로그래밍 언어에 따라 다양한 프레임 워크가 있습니다 (java, C/C++, ...).