Tôi đã được nghe trộm bởi cùng một vấn đề trong một thời gian bây giờ. Các giải pháp là sự đồng thuận rõ ràng được đưa ra trong các bài viết trước đó: tìm trung bình (mx, của tôi) một cách độc lập và sau đó tìm điểm gần nhất trong N điểm nhất định và đó là nơi gặp gỡ. Để xem tại sao đây thực sự là giải pháp đầu tiên bạn nên xem xét khoảng cách.
d = sum (| xi-x |) + sum (| yi-y |) trên tất cả 1 < = i < = N,
đó là độc lập trong x và y. Do đó chúng ta có thể giải quyết trường hợp 1-D cho x và y. Tôi sẽ bỏ qua lời giải thích cho ^^ và do đó kết luận rằng (mx, my) là giải pháp tốt nhất nếu chúng tôi xem xét tất cả các điểm có thể.Các thách thức lớn hơn là chứng minh rằng chúng ta có thể di chuyển từ (mx, my) đến gần nhất (xi, yi) sao cho (xi, yi) là một trong những điểm đã cho, w/o thay đổi (tăng) khoảng cách. Bằng chứng đi:
Hãy xem xét rằng chúng tôi đã sắp xếp tọa độ x (vì lợi ích cho bằng chứng) và rằng X1<X2<...<Xn. Ngoài ra Xj<mx<X(j+1) nơi j = N/2, bây giờ, hãy di chuyển mx một bước sang trái, đó là mx' <- mx-1. Do đó d' = |X1-mx+1| + .. + |Xj-mx+1| + |X(j+1)-mx+1| + .. + |Xn-mx+1| Chúng tôi biết rằng mx-1 sẽ tăng N/2 giá trị (cho k> = j + 1 và giảm cho < = j) do đó hiệu ứng là như nhau. Do đó (mx-1, my) đưa ra cùng một giải pháp . Điều đó có nghĩa là có một không gian từ Xj<mx<X(j+1) và Yj<my<Y(j+1) nơi khoảng cách không thay đổi. Vì vậy, chúng ta có thể tìm thấy điểm gần nhất như vậy mà là câu trả lời.
Tôi đã bỏ qua trường hợp tinh tế của các nút lẻ/lẻ, nhưng tôi hy vọng toán học sẽ tự hoạt động khi bạn nhận ra bằng chứng cơ bản.
Đây là bài đăng đầu tiên của tôi, giúp tôi cải thiện kỹ năng viết của mình.
Đây là vấn đề giảm thiểu trên miền Số nguyên. Bằng chứng thường không nhỏ ... –