최대 평균 서브 세트 크기를 갖는 등거리 서브 세트에서 세트를 분리하는 방법은 무엇입니까?

Question

나는 그들 사이에 N 개의 물체와 N * N의 거리를 가지고있다. 이 집합을 부분 집합에 클러스터링하여 각 클러스터에 모든 개체가 동일한 거리를 갖고 모든 클러스터의 평균 (cluster_size)이 최대화되도록합니다.

나는 같은 알고리즘에 의해이 작업을 해결하기 위해 노력 :

1. 객체 사이의 모든 고유 한 거리를 열거 할 수 있습니다. 각각의 고유 한 거리 X 용

2. 객체 A와 B 사이의 거리를 정확하게 경우 A와 B 사이의 에지가 존재하는 노드들 및 인접 행렬 같은 객체 기반 그래프를 생성 할 X

3. 는에 최대 도당을 찾을 수 있습니다 이 그래프. 이 파벌의 크기가 현재 최대 값보다 큰 경우 - 객체

4. 반복

   의 집합에서 결과에 저장된 업데이트 최대 저장 파벌 결과로

5. 삭제 개체 개체의 집합이 비어 있지 때까지

더 효율적인 [approximate] 솔루션이 있습니까?

Answer 1

(평균 클러스터 사이즈) = 점의 총 개수/클러스터

이 극대화 할 수있는 유일한 방법의 수는 클러스터의 수를 최소화하는 것이다. 그것은 최적화 목표로 상당히 나쁜 선택 인 것 같습니다. 이 목적을 다시 생각해 볼 수 있습니다.

그 외에도 귀하의 알고리즘은 상당히 합리적이라고 생각합니다. 문제는 NP가 어렵 기 때문에 탐욕적인 근사를 사용하고 싶습니다.

나는 게으 르어 다시 계산하는 것이 좋습니다. 몇 가지 경계를 추가하십시오.

1. 모든 고유 한 거리에 대한 하위 그래프를 작성하십시오.

2. 크기에 따라 하위 그래프를 내림차순으로 정렬하십시오.

3. 이전 반복에서 캐시 된 값이 없으면 각 하위 그래프에서 가장 큰 클릭을 찾으십시오. 전체적으로 가장 큰 파벌을 기억하십시오. 현재 가장 큰 것이 나머지 부분 그래프보다 큰 경우 중지하십시오.

4. 출력 최상위 하위 그래프가 발견되었습니다.

5. 모든 그래프에서 포함 된 노드를 제거하고 발견 된 노드가 포함 된 최상의 클록을 잊어 버리십시오. 2로 돌아갑니다.