[Có thưởng] Thử thách Toán học dành cho Vozer.

Trọng tâm của đa giác n-1 cạnh với các cạnh là đường nối giữa 2 người 1 với nhau
 
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 : ))
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 mà phải dev thuật toán.
 
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.
cái này là minimize khoảng cách Euclidean mà thím,
 
n
vận tốc j thím ?
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
 
nếu mà minimize thì có thể rút gọn cái 1/2 đấy
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

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
1631168629979.png
 
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.
các giá trị khoảng cách này luôn lớn hơn 0 nên tương đương nhau.
Và bài này không yêu cầu tìm nghiệm để phương trình bằng 0, mà tìm nghiệm để phương trình đạt cực tiểu/đại.
 
Bài toán tìm trọng tâm thôi mà
Với 2 điểm: trung điểm của đoạn
Với 3 điểm: trọng tâm của 2 điểm trước nối với điểm thêm vào rồi chọn điểm ở 2/3 đoạn ấy
Với 4 điểm: trọng tâm của 3 điểm trước nối với điểm thêm vào rồi chọn điểm ở 3/4 đoạn ấy
...
Với n điểm: trọng tâm của n-1 điểm trước nối với điểm thêm vào rồi chọn điểm ở (n-1)/n đoạn ấy

//sr mọi người, không phải trọng tâm nhé :D
 
Last edited:
các giá trị khoảng cách này luôn lớn hơn 0 nên tương đương nhau
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.
 
Back
Top