가장 가까운 가능한 길의 거리를 알면 여행 세일즈맨을 해결하십시오

Question

저는 TSP (Travelling Salesman Problem)을 해결하려고 노력하고 있지만 전통적인 방식은 아닙니다. 나는이 단계들을 따르고있다.

1) 먼저 나는 참/거짓 문제에 TSP를 변경합니다.

"이 문제의 정의는 다음과 같습니다."총 거리가 k보다 작거나 같은 모든 도시의 경로가 있습니까? " 이 알고리즘을 해결하기 위해 TSP_tf(k) 알고리즘이 있다고 가정 해 보겠습니다.

2) 그러면 I 최소 K 검색.

이것은 "가능한 가장 짧은 거리의 거리"를 검색합니다.

효율적인 알고리즘으로 이분법 검색을 수행 할 수 있습니다. k=1으로 시작하고 TSP_tf(k)으로 전화합니다. false를 반환하면 k에 2를 곱하고 true가 반환 될 때까지 TSP_tf을 계속 호출합니다. 이 경우 (k/2 - k] 간격으로 true를 반환하는 최소 k을 검색하고 이분법 검색을 사용하십시오.

최소 거리는 min_k입니다.

3)은 TSP의 최단 경로의 거리가 min_k입니다 알고 돌아.

여기 내 질문이옵니다. 어떻게 이것을 해결하는 효율적인 알고리즘이 될 것입니까? 능률적으로 나는 좋은 접근을 의미한다 : TSP가 NP 인 것을 명백 할 것이다.

Answer 1

나는 그것을 결국 해결할 수있었습니다.

TSP의 도시와 그 연결구를 나타내는 그래프 g이 있다고 가정 해 보겠습니다. 노드는 도시를 나타내고 가중치는 해당 도시와 도시 간의 거리가 해당 도시와 연결되어 있음을 나타냅니다.

거리가 주어진 경우 가장 짧은 경로를 얻으려면 가장자리를 하나씩 삭제하고 가장 짧은 경로에 속하는지 확인하십시오. 어떻게 알 수 있습니까?우리는 그래프에서 가장자리 e을 삭제하고 우리가 알려진 최단 거리 min_k와 TSP_tf를 호출 할 경우 두 가지 상황이 발생할 수 있습니다

• TSP_tf(min_k) == false합니다. 이것은 을 삭제하면 min_k 거리의 경로를 얻을 수 없습니다. e은 최단 경로의 일부입니다.

• TSP_tf(min_k) == true. e 연결이 없으면 동일한 최소 거리 min_k 거리를 얻을 수 있습니다. e은 최단 경로에 참여하지 않습니다.

우리는 그래프의 모든 모서리에 점진적으로 적용하는 경우, 우리는 정확한 최단 경로를 얻을 수 있습니다 (또는 더 나은 하나 이상의 해결책이 될 수 있기 때문에, 가장 짧은 경로 중 하나를 말했다).

// min_k is the distance of the shortest path of the TSP represented by the graph g. 
Graph TSP(Graph g, int min_k) 
    Graph shortestPath = g; 
    For (Edge e in g) 
     // Delete the edge e. 
     shortestPath -= e; 
     // e is part of the shortest path. 
     If (TSP_tf(shortestPath, min_k) == false) 
      shortestPath += e; 
     EndIf 
    EndFor 
    Return shortestPath; 
EndTSP 

우리가 알다시피, 그래프의 노드의 최대 수는 |V| 노드의 수를되고, 1/2 * |V| * |V-1|입니다. 각 노드에 대해 TSP_tf 호출이 수행되므로 TSP_tf에 대한 호출 수는 O(|V|^2) 인 효율적인 알고리즘입니다.

Answer 2

귀하의 TSP_tf은 일반적으로 의사 결정 문제 버전으로 알려져 있습니다. 해당 문제는 NP 완료입니다. 확인을 위해 https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computational_complexity을 참조하십시오. 그러므로 당신은 그것이 매우 다루기 쉽기를 희망해서는 안됩니다.

위키피디아의 기사에는 실용 상 TSP 문제를 해결하는 놀랍도록 효과적인 방법에 대한 많은 정보가 있습니다.