Tìm điểm giao nhau gần nhất trong kế hoạch

Question

Tôi đã được hỏi câu hỏi sau đây trong cuộc phỏng vấn gần đây:

Giả sử bạn có, theo lưới trên hệ tọa độ Descartes (Quadrant I).

o - x - x - x - o 
| | | | | 
x - x - x - o - x 
| | | | | 
x - o - o - x - x 

where, o => person at intersection and x => no person at intersection 

class Point { 
int x; 
int y; 
boolean hasPerson; 
} 


Point findNearestPointWhereAllPeopleCanMeet(Point[] people) { 

} 

Thực hiện thói quen khi có danh sách vị trí người (điểm), tìm vị trí (điểm) gần điểm nhất định cho tất cả điểm đã cho.

Bạn giải quyết vấn đề này như thế nào?

1) Cách tiếp cận là cây k-d, nhưng bạn có biết bất kỳ giải pháp nào khác không?

Answer 1

Nếu sự cố kêu gọi giảm thiểu số Manhattan distance (nghĩa là, mọi người chỉ đi song song với trục), thì vấn đề sau đó khá tầm thường. Đầu tiên, chọn tọa độ x và tọa độ y là các vấn đề độc lập.

Sau đó, đối với mỗi tọa độ, chỉ cần tìm giá trị trung bình của vị trí của những người dọc theo trục đó. Đối với nhiều cấu hình của mọi người, có thể có nhiều hơn một điểm để giảm thiểu tổng khoảng cách đi bộ của tất cả mọi người. (Chỉ cần xem xét 2 người cách nhau hơn 2 khối trong x và ở cùng toạ độ y; bất kỳ giao lộ nào ở giữa sẽ yêu cầu cùng một tổng số đi bộ của hai người.)

Nếu vấn đề yêu cầu giảm thiểu khoảng cách Euclide, thì mục tiêu là tìm trung bình L1 2 biến. Đây là một vấn đề tiêu chuẩn, nhưng nó là xa tầm thường. (Ví dụ: xem here) Có một câu trả lời duy nhất. Cho rằng đây là một câu hỏi phỏng vấn, tôi nghi ngờ rằng điều này không áp dụng.

Answer 2

Trước khi đi nghiên cứu cây kd đây là một vài suy nghĩ mà đến tâm trí của tôi:

1. Lặp mọi điểm của ma trận, đồ thị của bạn, hoặc bất cứ điều gì nó là
2. Gán cho mỗi điểm (x, y) một giá trị biểu thị MAX_distance từ Điểm đến bất kỳ người nào. (Xem một ví dụ rõ bên dưới)
3. Đi bất kỳ điểm nào có MAX_DISTANCE thấp nhất

V.D. Point Given (0,0):

• Đối với (1,0) khoảng cách là: 1
• Đối với (2,0) khoảng cách là: 2
• Đối với (0,2) khoảng cách là: 2
• đối với (3,1) khoảng cách là: 4
• đối với (4,2) khoảng cách là: 6

các MAX_DISTANCE cho (0,0) là 6. Given của bạn nhập MAX_distance thấp nhất phải là 3 và có nhiều điểm với giá trị đó như (2,1) f hoặc ví dụ.

Nên có cách để làm cho thuật toán này hiệu quả hơn .. Có thể với cây kd: p hoặc với các chỉnh sửa khác như kiểm tra tổng số người, vị trí tương đối/khoảng cách, giá trị MAX_distance ở bất kỳ lần lặp nào, v.v.

Answer 3

Điều này có thể sẽ cung cấp cho bạn nhiều câu hỏi gần đúng hơn câu trả lời đúng. Nhưng có lẽ bạn có thể thử một số loại phân nhóm (xem xử lý ảnh y tế)

gì nếu bạn dự án tất cả các điểm trên trục Y:

3* 
4* 
3* 

Sau đó, dự án trên trục X:

2* 2* 2* 2* 2* 

Chú thích: 3 * có nghĩa là 3 người tại tọa độ này trên trục

Bây giờ, hãy tìm trung bình cũng sử dụng trọng số (weight @location = bao nhiêu người ở lần thứ tại vị trí trên trục)

Nếu bạn tìm thấy trung vị cho cả hai trục thì bạn có thể lấy điểm cuộc họp là (trung bình, trung bình).

Bạn có thể nhận được điểm gần nhất chính xác nếu khi bạn tính trung bình trên một trục, bạn cũng phải đảm bảo giảm thiểu khoảng cách bằng cách tính trung bình của trục kia. Trường hợp sau này khó hơn.