여러 도시를 방문하는 TSP의 변형

StackOverflow https://stackoverflow.com/questions/1458048

  •  12-09-2019
  •  | 
  •  

문제

나는 여러 방문으로 TSP에 대한 지점과 바운드 솔루션에 대해 논의하려고합니다.

편집하다:

Jitse가 지적한대로 관련이 없기 때문에 의심을 제거했습니다. 이제 질문이 더 분명합니다.

도움이 되었습니까?

해결책

각 노드 A와 B 쌍에 대해 A에서 B까지 가장 짧은 경로를 나타내는 가장자리를 추가하여 그래프를 확대합니다. Floyd-Warshall 알고리즘 TSP 알고리즘보다 훨씬 빠른 O (n^3) 에서이 작업을 수행 할 수 있습니다. 이 작업을 마치면 표준 TSP 브랜치 및 바운드 기술을 사용하십시오. 이 지역 정보가 있습니다 애플 게이트의 책, 지점에 대해 논의하고 TSP에 대한 바운드 Wikipedia tsp 항목.

다른 팁

나는 그의 제안을 구현하기 쉬운 가능한 감독을 다루기 때문에 Martin Hock의 답변에 대한 의견으로 이것을 제출하고 싶습니다.

분기 및 바운드 알고리즘은 Floyd-Warshall 알고리즘의 출력을 고려할 때 최소 비용 경로를 재구성하기위한 알고리즘과 결합해야합니다. 분기 및 바인딩 알고리즘은 외부 루프이며 방문되지 않은 노드를 선택합니다. 그런 다음 최소 비용 경로 재구성 알고리즘을 사용하여 실제로 사이클에 가장자리와 노드를 추가합니다. 노드는 분기 및 바인딩 부분뿐만 아니라 최소 비용 경로 재구성 알고리즘에 의해 방문한대로 표시되어야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top