TSP 용 클러스터링 알고리즘

Question

약 10,000 개의 도시로 구성된 매우 큰 TSP를 해결하려고합니다. 필자의 업무를 병렬화하기 위해이 도시를 클러스터로 나누고 각 클러스터에 대해 TSP를 해결하려고합니다.

나는 내 도시를 클러스터로 분리 할 수있는 방법을 원한다. (클러스터의 각 도시 사이의 근접성/근접성).

효과적인 순서를 아는 사람이 있습니까?

Answer 1

솔루션이 (최적으로 기억한다면 적어도 유클리드 메트릭에서는) 최적 솔루션보다 최대 2 배 최악이라는 간단한 근사 알고리즘이 있습니다. 알고리즘은 다음과 같습니다. 최소 스패닝 트리를 가져옵니다. 나무 가장자리를 사용하여 여행하십시오.

나는 스스로를 발명하는 대신에 더 좋은 근사 알고리즘을 연구하려고한다.

는, 당신이 그것을 수행하려는 경우, 당신이 찾고있는 단지 도구 몇 가지 밀도 기반 클러스터링 알고리즘이 있습니다

Answer 2

(같은 기사에서) K-means과 다른 알고리즘을 거기, 클러스터로 구분합니다 어쨌든 점들을 클러스터로 분리하는 것.

DBSCAN은 다른 것들로부터 파생 된 주요한 것입니다. OPTICS는 클러스터링 자체를 생성하지 않는 DBSCAN의 확장이지만 클러스터를 추출하기 위해 검사 할 수있는 점의 플롯을 만듭니다 (알고리즘의 또 다른 부분은 자동으로 클러스터를 추출합니다). DBSCAN은 더 간단하고 OPTICS는 더 많습니다. 융통성 있는. 이 두 가지 모두 R-tree와 같은 적절한 인덱싱 구조를 사용하면 더 효율적입니다. ELKI, scikit 및 WEKA와 같은 툴킷에는 구현이 있습니다.

은 매우 바쁜 세일즈맨이다