3
D 차원 메트릭 공간에 N 개의 점 집합이 있습니다. 하위 집합의 두 점 사이의 가장 작은 거리가 가장 큰 방식으로 K를 선택하고 싶습니다.Maxmin 거리감에서 가장 좋은 서브 샘플
예를 들어, 3 차원 유클리드 공간에서 N = 4 및 K = 3 인 경우, 해는 가장 긴 단변을 갖는 정사면체의면이됩니다.
달성 할 수있는 고전적인 방법이 있습니까? 그것은 다항식 시간으로 정확히 풀 수 있습니까?
나는 할 수있는 한 많이 봤지만이 문제를 부르는 법을 아직 알지 못했습니다.
내 경우 N = 50, K = 10 및 D = 300입니다.
명확한 설명 :
무력 접근 방식은 N 중에서 K 포인트의 모든 조합을 시도하고 모든 부분 집합에 가장 가까운 쌍을 결정하는 것입니다. 해결책은 가장 긴 쌍을 산출하는 부분 집합에 의해 주어집니다.
O (K^2) 과정을 반복하여 N!/K! (N-K)! 타임스.
흠, 10^2 50!/10! 40! = 1027227817000
점 사이의 거리를 가진 그래프를 만든 다음 Kruskal 알고리즘의 수정 된 버전을 실행하여 최대 스패닝 트리를 구현하는 것 같습니다. – higuaro
최대 스패닝 트리는 노드간에 긴 링크가있는 V 자형이 될 수 있지만 두 개의 노드가 매우 가까운 링크로 결합되지 않았습니다. 나는 이것에 대한 명백한 언덕 오르기와 욕심 많은 알고리즘을 생각할 수있다. (데이터를 조사하고 지금까지 가지고있는 점 중 하나를 사용하여 새로운 점을 바꾸는 것이 반복적으로 개선되는지를 반복적으로 볼 수는 있지만) 그들은 특정 최적화를하지 않을 것이다. – mcdowella
나는 N 포인트에 최대 스패닝 트리를 구축했습니다. 내 K 하위 샘플을 얻기 위해 트리를 잘라내려면 어떻게해야합니까? 스패닝 트리를 어떻게하면 솔루션에 더 가까이 가게 할 수 있습니까? –