여행 세일즈맨 - 근사 온라인 소프트웨어?

Question

여행 판매원 문제에 대한 평범한 솔루션을 생성하는 솔루션을 알고 계신 분도 계실 것입니다. 31 명의 목적지를 방문하는 3 명의 사람들이 있습니다 ... 어떻게 접근해야할지 모르겠습니다. 모든

감사합니다 -

맥심

Answer 1

나는 당신이 (출발점이 지정되지 않은 경우) 시작하는 임의의 지점을 선택하여 욕심 접근 방법을 시도 할 수 다음 각 단계에 당신이 여행 가정 현재 지점과 가장 가까운 지점. 점 사이의 거리를 일정 시간으로 계산할 수 있다고 가정하면 O (n^2) 시간에 경로를 찾을 수 있습니다.

(나는 이런 종류의 일을 잠시에서 작성하지 않은, 그래서 나는이 충분히 명확 바랍니다) 다음 의사 코드가 도움이 될 것입니다, 명확히하기 위해

Name: GreedyPath(C, p) 
Input: C - a non-empty collection of points to visit 
     p - a starting point in C 
Output: S - a sequence of points covering C 
Algorithm: 
    Remove p from C 
    If C is empty 
    Return the sequence containing only p 
    Else 
    Let p1 be the closest point to p in C 
    Let S = GreedyPath(C, p1) 
    Append p to the start of S 
    Return S 

은 분명히 일부를 소비하는 시간이를 찾는 매번 p에 가장 근접한 지점이지만, n 점에 대해서 이것은 (내가 잘못하지 않는 한) n(n-1)/2 거리 계산 만 필요합니다.

Answer 2

Nearest Neighbor, Christofides 및 Lin–Kernighan과 같은 몇 가지 옵션이 있습니다.

이러한 경우 실패하면 전문가의 code을 언제든지 사용할 수 있습니다 (학술 연구자에게는 무료).