2D 평면상의 점 목록을 사용하면 점 목록에서 모든 점까지의 총 합계가 평면에 N 점을 어떻게 배치 할 수 있습니까? 가장 가까운 배치 지점은 가능한 작았습니까? 환경은 신중하며 목록에는 [(0,0); (~ 200 : ~ 100)]N 지점을 점으로 최소화 점 목록까지의 거리
알고리즘의 최악의 경우의 성능은 다항식이어야하며 따라서 실시간으로 계산 범위가 작아야합니다. 모든 근사값도 환영합니다.
이 소리는 실제로 무엇을 K-Means clustering algorithm처럼 들립니다. 귀하의 경우, 포인트 목록은 입력이며, 포인트 수 N은 클러스터 수입니다.
안타깝게도 NP 하드입니다. 그러나 많은 연구가 진행되고 있으며 더 나은 방법을 찾으려는 많은 방법이 있습니다 (위키 페이지를 스크롤하여 찾으십시오).
또한 k- 수단이 학자들에 의해 많이 사용되기 때문에 더 나은 알고리즘이 있을지는 의문입니다. 나는 그들이 더 나은 알고리즘을 가지고 있다고 생각합니다.
그리고 다시, 저는 데이터 마이닝에서 가장 좋은 튜토리얼을 Andrew Moore's slides으로 제시했습니다. 비록 당신의 목적을 모르지만, 이것은 당신이 필요로하는 것에 아주 가깝습니다.
내가 필요로하는 것과 똑같은이 소리. 나는 그것을 조금 들여다 볼 것이다. –
가중치가 1 인 노드 목록의 Center of mass을 얻을 수 있습니다.
또는 거리에 대한 x^2의 분산.
나머지 노드와의 거리가 최소 인 질량 중심 영역에 N 노드를 배치 할 위치로 문제를 줄였습니다.
완벽한 세계에서 당신은 질량 중심에 단지 1 점을 넣을 수 있습니다. 그러나 같은 위치에 2 점을 놓을 수 없다고 가정하기 때문에 질량 중심 부근을 선택해야합니다.
이렇게하면 질량 중심 부근에서 최고 8 점을 선택하고 질량 중심을 다시 계산 한 다음 문제를 해결할 수 있습니다.
원래 세트의 각 포인트에 대해 가장 가까운 이웃 인 새 세트에서 한 포인트까지의 거리 만 계산한다는 말씀입니까? – mbeckish
나는 "가장 가까운 배치 지점"에 혼란 스럽다. 그러나 나는 당신에게 점수를주고 그들이 말한 지점에 최대한 가깝게 배치 할 것을 요구한다고 가정한다. 이게 네가 말하는거야? 어떤 경우에는 점 주위에 원의 모든 점을 넣을 수 있습니다. – djhaskin987
@mbeckish 맞습니다. –