나는 traveling salesman problem에 대한 파이썬에서 memetic 알고리즘을 만들었습니다. 그러나 내가 만난 모든 테스트 데이터 (도시 간 거리 목록)에는 최상의 솔루션에 대한 정보가 없으므로 글로벌 최적 알고리즘에 얼마나 근접하는지 알 수 없습니다.널리 알려진 글로벌 최적의 여행 판매원 사례
아무도 내가 알고있는 최고의 솔루션으로 일부 tsp 테스트 데이터 (가급적이면 매트릭스 형태로되어 있지만, 어떤 것도 좋음)를 어디에서 찾을 수 있는지 알고 있습니까?
Google은 무엇을 했습니까?
http://www.tsp.gatech.edu/data/index.html
해당 페이지 16가 최적의 솔루션을 가지고있는 여러 테스트 케이스를 제공한다.
네,하지만 웬일인지 가장 명백한 것은 아닙니다. 감사합니다. . – checker
+1. 아주 좋은 사이트. –
이것은 실제로 지금 Google에서 첫 번째 결과입니다. :) –
아마도 자신 만의 테스트 데이터를 생성 할 수 있습니까?
이것은 포괄적 인 테스트는 아니지만 도움이 될 것입니다. 참고 : 아래는 해밀턴의 경로에 대한 것이며, 사이클을 찾고 있다면 비슷한 것이 가능할 것입니다. 당신은 다음과 같은 작업을 수행 할 수
는 :
는 n 개의 노드가있는 무향 그래프 G를 주어 말한다.
이제 G의 가장자리의 무게를 1로 설정하고 G가 아닌 가장자리를 추가하여 임의의 무게가 1보다 큰 가중 그래프 G '를 만듭니다. 즉 G'는 모든 가장자리에 할당 된 가중치.
이제 G '에서 유효한 TSP 알고리즘을 실행하고 크기 n-1의 경로를 생성하면 G는 해밀턴 경로를 갖습니다. 그렇지 않으면 G는 해밀턴 경로를 갖지 않습니다. (: Hypercube은 해밀턴 경로를 가지고 예컨대 용) 및 TSP 알고리즘에 대한 테스트 데이터를 생성
그래서 지금 당신은 당신이 해밀턴 경로가없는 /이 그 알고 그래프를 사용할 수 있습니다. http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
을 당신이 힘든 시간 해밀턴 경로없이와/그래프에 데이터를 찾는데 어려움이되지 않습니다 가정 :
이 페이지는 해밀턴 경로를 그래프를 생성에 유용 할 수있는 몇 가지 충분 조건을 가지고있다.
희망이 있습니다. 행운을 빕니다!
TSPLIB는 다양한 소스 및 다양한 유형의 TSP (및 관련 문제)에 대한 샘플 인스턴스의 라이브러리입니다.
항상 분명히 O (1)이다 이베이에이 판매하고. :-P http://xkcd.com/399/ –