거리 매트릭스의 대략적인 추정

Question

나는 N 개의 오브젝트 집합을 가지고 있으며 NxN 거리 매트릭스를 계산하고 싶습니다. 때로는 내 N 개체 집합이 매우 커서 거리 비교의 하위 집합 만 계산하여 NxN 거리 행렬에 대한 근사값을 계산하고 싶습니다.

누구나 전체 거리 매트릭스에 대한 근사치를 계산하는 방향으로 나를 가리킬 수 있습니까? 나는 몇 가지 아이디어를 염두에두고 있지만 휠을 다시 발명하는 것을 피하고 싶습니다.

편집 : 알고리즘 유형의 예는 객체 A와 객체 B 사이에 매우 작은 거리가 있고 객체 B와 객체 C 사이에 매우 작은 거리가있는 경우 이점이 있습니다. 객체 A와 C 사이의 거리가 다소 짧습니다.

Answer 1

정직하게 말하자면 근사치가 얼마나 가깝고 하위 집합이 얼마나 큰지에 달려 있다고 생각합니다. 행렬이 어떻게 보이는지 전체적인 느낌을 원한다면 무작위 부분 집합 (최대 및 최소 노드 포함)에서 간단한 선형 보간법을 사용하여 매우 정확한 (tm) 결과를 얻을 수 있습니다.

는 여기 진짜 트릭은 휴리스틱 (선형, 차, 등 보간) 및 하위 집합의 크기를 알아내는 생각합니다. 또한 여러 부분 집합의 거리 행렬을 계산 한 다음 이러한 행렬을 몇 가지 방법 (선형, 구형 선형, 입방)으로 보간 할 수 있습니다.

초기 샘플에 따라, "오, 그게 내가 필요한 것에 충분하다"가 될 때까지는 경험적으로 시행 착오를 반복합니다.

Answer 2

"객체"가 네트워크에 있습니까? 개체가 네트워크에 있으면 this 또는 this을 사용하면 모든 쌍이 최단 경로가됩니다. 그렇지 않다면, 당신은 거의 모든 n x n 거리를 계산할 수 밖에 없다고 생각합니다.

Answer 3

우리가 일반적으로 그래프에서 보는 것과 유사하다 필요 솔루션, 당신은 거리를 찾는 All pair shortest path을 사용할 수 있습니다, 당신은 또한 johnson's algorithm