tìm điểm gần nhất với các điểm khác

Question

Cho điểm N (theo 2D) với toạ độ x và y. Bạn phải tìm điểm P (trong N điểm đã cho) sao cho tổng khoảng cách từ điểm khác (N-1) đến điểm P là nhỏ nhất.

cho ví dụ. N điểm cho p1 (x1, y1), p2 (x2, y2) ...... pN (xN, yN). chúng tôi đã tìm thấy điểm P trong p1, p2 .... PN có tổng khoảng cách từ tất cả các điểm khác là tối thiểu.

Tôi đã sử dụng phương pháp tiếp cận vũ lực, nhưng tôi cần một cách tiếp cận tốt hơn. Tôi cũng đã cố gắng bằng cách tìm trung bình, có nghĩa là vv nhưng nó không hoạt động cho tất cả các trường hợp.

sau đó tôi đưa ra ý tưởng rằng tôi sẽ coi X là một đỉnh của đa giác và tìm thấy trọng tâm của đa giác này, và sau đó tôi sẽ chọn một điểm từ Y gần nhất với trọng tâm. Nhưng tôi không chắc liệu centroid có giảm thiểu tổng khoảng cách của nó đến các đỉnh của đa giác hay không, vì vậy tôi không chắc liệu đây có phải là một cách tốt hay không? Có bất kỳ thuật toán nào để giải quyết vấn đề này không?

Answer 1

Nếu điểm của bạn được phân phối độc đáo và nếu có quá nhiều lực bạo lực (tính tổng khoảng cách từ mỗi điểm đến mọi điểm khác) thì không hấp dẫn như sau có thể cho bạn câu trả lời đủ tốt. Bởi 'phân phối độc đáo', tôi có nghĩa là (xấp xỉ) đồng nhất hoặc (xấp xỉ) một cách ngẫu nhiên và không có cụm được đánh dấu ở nhiều vị trí.

Tạo lưới thống nhất k*k, trong đó k là một số nguyên lẻ, trên toàn bộ không gian của bạn. Nếu điểm của bạn được phân phối độc đáo, cái mà bạn đang tìm kiếm (có lẽ) trong ô trung tâm của lưới này. Đối với tất cả các ô khác trong lưới đếm số điểm trong mỗi ô và ước tính vị trí trung bình của các điểm trong mỗi ô (hoặc sử dụng trung tâm ô hoặc tính trung bình (x,y) cho các điểm trong ô).

Đối với mỗi điểm trong ô trung tâm, tính toán khoảng cách tới mọi điểm khác trong ô trung tâm và khoảng cách trung bình trọng số cho các điểm trong các ô khác. Tất nhiên, điều này sẽ là khoảng cách từ điểm đến vị trí 'trung bình' của các điểm trong các ô khác, được cân bằng bởi số điểm trong các ô khác.

Bạn sẽ phải điều chỉnh độ chính xác tăng của giá trị cao hơn cho k so với tải tính toán gia tăng và tìm ra điều gì phù hợp nhất với điểm của bạn. Nếu sự phân bố các điểm trên các ô không đồng đều thì phương pháp này có thể không phù hợp.

Cách tiếp cận này được sử dụng khá rộng rãi trong các mô phỏng quy mô lớn, nơi các điểm có các đặc tính, chẳng hạn như trọng lực và điện tích, hoạt động trong khoảng cách. Cho dù nó phù hợp với nhu cầu của bạn, tôi không biết.

Answer 2

Tôi không chắc chắn nếu tôi hiểu câu hỏi của bạn nhưng khi bạn tính toán cây bao trùm tối thiểu, tổng số từ bất kỳ điểm nào đến bất kỳ điểm nào khác từ cây là tối thiểu.

Answer 3

Điểm trong việc xem xét được gọi là hình học trung bình

Các trọng tâm hoặc trung tâm khối lượng, định nghĩa tương tự với trung bình hình học như giảm thiểu tổng các bình phương của khoảng cách cho mỗi mẫu, có thể được tìm thấy bởi một công thức đơn giản - tọa độ của nó là trung bình của tọa độ của mẫu nhưng không có công thức nào được biết cho trung bình hình học, và nó đã được chứng minh rằng không có công thức rõ ràng hoặc thuật toán chính xác chỉ liên quan đến phép tính số học và rễ thứ k .