Bài toán của thớt là tổng các khoảng cách (Bài toán k trơn)gọi điểm tốt nhất đấy có tọa độ (X, Y)
vậy thì mình cần phải tối ưu hóa hàm số sau
minimize ∑((X - x_i)^2 + (Y -y_i)^2)
khai triển thành
minimize 5*X^2 + 5*Y^2 -2*X*∑x_i - 2*Y*∑y_i +∑x_i^2 + ∑y_i^2
đặt f(X,Y) = 5*X^2 + 5*Y^2 -2*X*∑x_i - 2*Y*∑y_i +∑x_i^2 + ∑y_i^2
f'(X) = 10*X - 2*∑x_i
f'(Y) = 10*Y - 2*∑y_i
hàm f(X,Y) sẽ đạt cực đại/tiểu tại f'(X) = 0 và f'(Y) = 0
=> X = 2*∑x_i/10 = 1/5 * ∑x_i
Y = 2*∑y_i/10 = 1/5 * ∑y_i
Chứng mình lằng ngoằng nhưng điểm tốt nhất là điểm trung bình giá trị của các điểm kia : ))
cái này là minimize khoảng cách Euclidean mà thím,Bài toán của thớt là tổng các khoảng cách (Bài toán k trơn)
Cái bạn đang giải là tổng bình phương các khoảng cách rồi (bài toán trơn.)
// bài toán này k có nghiệm closed-form nha.
Khoảng cách Ơ clít từ (X,Y) tới (x_i,y_i) là ((X - x_i)^2 + (Y -y_i)^2)^(1/2). Bác thiếu cái lũy thừa 1/2cái này là minimize khoảng cách Euclidean mà thím,
nếu mà minimize thì có thể rút gọn cái 1/2 đấyKhoảng cách Ơ clít từ (X,Y) tới (x_i,y_i) là ((X - x_i)^2 + (Y -y_i)^2)^(1/2). Bác thiếu cái lũy thừa 1/2
Thành có nhóm bạn gồm n người ở n điểm khác nhau trong thành phố. Nhóm bạn này muốn hẹn gặp mặt nhau tại 1 điểm bất kỳ. Nhưng vấn đề là chọn điểm nào để tốt cho tất cả ?vận tốc j thím ?
K đúng nhé. Cực tiểu tổng khoảng cách và tổng bình phương kc là 2 bài toán không tương đương. Phản ví dụ có thể lấy trong TH 1 chiều với n=3 chẳng hạn. Nghiệm của bài toán tổng bình phương kc là trung bình cộng các điểm cho trước trong khi nghiệm của bài toán tổng kc là trung vị của các điểm cho trước.nếu mà minimize thì có thể rút gọn cái 1/2 đấy
n
Thành có nhóm bạn gồm n người ở n điểm khác nhau trong thành phố. Nhóm bạn này muốn hẹn gặp mặt nhau tại 1 điểm bất kỳ. Nhưng vấn đề là chọn điểm nào để tốt cho tất cả ?
Đâu có đề cập đến việc vận tốc di chuyển bằng nhau đâu thím
các giá trị khoảng cách này luôn lớn hơn 0 nên tương đương nhau.K đúng nhé. Cực tiểu tổng khoảng cách và tổng bình phương kc là 2 bài toán không tương đương. Phản ví dụ có thể lấy trong TH 1 chiều với n=3 chẳng hạn. Nghiệm của bài toán tổng bình phương kc là trung bình cộng các điểm cho trước trong khi nghiệm của bài toán tổng kc là trung vị của các điểm cho trước.
đề bài không giả sử vận tốc bằng nhau thì không được lược bỏ đâu thím
Mình nói tới đó thôi . Trong TH 1 chiều nó đã k tương đương roài. Đây là bài toán tìm trung vị hình học và k có nghiệm closed-form. Bye bác.các giá trị khoảng cách này luôn lớn hơn 0 nên tương đương nhau
vận tốc từ điểm thứ n tới điểm trung tâm chắc gì đã giống nhau đâu thím
đề bài không giả sử vận tốc bằng nhau thì không được lược bỏ đâu thím
Trong paper này họ propose một thuật toán chạy trong thời gian gần như là tuyến tính để giải bài toán của chủ thớt lày
- Cohen, Michael; Lee, Yin Tat; Miller, Gary; Pachocki, Jakub; Sidford, Aaron (2016). "Geometric median in nearly linear time" (PDF). Proc. 48th Symposium on Theory of Computing (STOC 2016). Association for Computing Machinery. arXiv:1606.05225. doi:10.1145/2897518.2897647.
thế bài toán đơn giản quá rồi còn gìĐây là bài toán, ví dụ chỉ là thực tế cho thú vị thôi, các yếu tố như tốc độ, sức mạnh, thời tiết ... là như nhau nha Bác.