클러스터링 구현을위한 아이디어

Question

클러스터링 알고리즘을 구현 중입니다. 원본 복사본을 보관할 객체는 vector of Node이고 다른 객체는 vector of Cluster입니다. 각 Cluster object에는 포함 된 모든 노드에 vector of pointers이 있습니다.

매 반복마다 두 개의 클러스터가 결합 비용에 따라 결합되어야합니다.

지금은 priority queue을 사용하여 두 비용 집계 비용과 두 클러스터에 대한 포인터를 포함하는 구조체를 보유하고 있습니다. 모든 반복에서 최소 비용으로 항목을 팝하고 참조 된 클러스터에 참여합니다. 큐를 사용하고 싶습니다. 왜냐하면 최소한의 비용을 찾기 위해 모든 오브젝트에 반복적 인 데이터가 많이 발생하기 때문에 실용적이지 않습니다.

한 클러스터에서 다른 클러스터로 데이터를 복사 한 다음 클러스터 중 하나를 제거하여 병합을 구현했습니다. 문제는 내 대기열에 이제 제거 된 클러스터를 참조하는 항목이 많이 포함되어 있다는 것입니다.

어떻게 구현하겠습니까? 어쩌면 클러스터에 가입하는 좀 더 영리한 방법이 있을까요? 구현을위한 제네럴 아이디어를 찾고 있습니다.

Answer 1

다음과 같은 생각이 있습니다. bool _isRemoved 필드를 Cluster 클래스에 추가합니다. 제거 된 모든 클러스터에 대해 true으로 설정합니다. 대기열에서 무언가를 꺼내면 _isRemoved이 true으로 설정된 두 클러스터 중 하나가 있는지 먼저 확인합니다. 그렇다면 큐에서 다음 쌍을 팝하고 처리를 계속해야합니다.

저는 C++ 전문가는 아니지만 다음 문제는 제거되어 참조 된 클러스터가 여전히 메모리를 차지한다는 것입니다. 큐에 클러스터에 대한 포인터를 저장하는 대신이 문제점을 피하려면 클러스터의 식별자를 저장할 수 있습니다. 식별자는지도 (사전)를 사용하여 클러스터에 빠르게 매핑 될 수 있습니다.