Trung vị hình học (thuật toán Weiszfeld)
Tìm điểm làm nhỏ nhất tổng có trọng số khoảng cách Euclid tới một tập điểm (bài toán Fermat-Weber) bằng phép lặp Weiszfeld, kèm hiệu chỉnh Vardi-Zhang khi trung vị trùng một điểm dữ liệu.
Trung vị hình học (geometric median) của các điểm trên mặt phẳng với trọng số dương là điểm làm nhỏ nhất tổng có trọng số các khoảng cách Euclid
Đây là bài toán Weber (hay Fermat-Weber): đặt một kho, một trạm phát, một điểm hẹn sao cho tổng quãng đường (nhân trọng số) nhỏ nhất. Khác với trường hợp khoảng cách Manhattan (tách được theo từng trục, đáp án là trung vị của các hoành độ và của các tung độ) hay tổng bình phương khoảng cách (đáp án là trọng tâm), trung vị hình học không có công thức đóng khi . Thuật toán Weiszfeld là phép lặp điểm bất động đơn giản tìm nó với độ chính xác cao, mỗi vòng , thường hội tụ sau vài chục đến vài trăm vòng.
Với điểm cùng trọng số và mọi góc của tam giác nhỏ hơn , trung vị chính là điểm Fermat (nhìn ba cạnh dưới góc ); nếu có góc thì là đỉnh của góc đó.
Ý tưởng / Trực giác
Hàm lồi. Mỗi là hàm lồi theo , nên lồi; nếu các điểm không cùng nằm trên một đường thẳng thì lồi chặt và trung vị là duy nhất. Mọi cực tiểu địa phương đều là cực tiểu toàn cục, nên một phép lặp làm giảm dần là đủ.
Điều kiện tối ưu. Khi không trùng điểm nào, gradient là
Trực giác vật lý: mỗi điểm kéo về phía nó bằng một sợi dây có lực không đổi (không phụ thuộc khoảng cách). tối ưu khi tổng các lực bằng . Với ba điểm trọng số bằng nhau, ba vectơ đơn vị có tổng đúng khi chúng lệch nhau : đó là điểm Fermat.
Phép lặp Weiszfeld. Đặt . Giải theo như thể các là hằng số:
Đây là trung bình có trọng số : điểm càng gần càng có tiếng nói lớn. Có thể chứng minh (bằng bất đẳng thức áp cho hàm thay thế bậc hai , mà là cực tiểu) rằng , dấu bằng chỉ khi đã tối ưu. Phép lặp hội tụ tuyến tính khi trung vị không trùng điểm dữ liệu nào.
Khi trùng một điểm dữ liệu. Công thức chia cho . Gọi là tổng trọng số các điểm trùng và là tổng lực kéo của các điểm còn lại. Điều kiện tối ưu (dưới gradient) là
điểm tại "giữ" được dây kéo của tất cả các điểm khác. Nếu điều kiện sai, hiệu chỉnh Vardi-Zhang bỏ các điểm trùng khỏi bước Weiszfeld (được điểm ) rồi chỉ đi một phần quãng đường: với .
Hội tụ chậm về một đỉnh. Nếu trung vị là một điểm dữ liệu (ví dụ có trọng số rất lớn), Weiszfeld tiến về rất chậm vì càng gần thì bước càng nhỏ. Cách chữa: ở mỗi vòng, nếu điểm dữ liệu gần nhất thay đổi thì kiểm tra trực tiếp điều kiện tại điểm đó (tốn thêm , mỗi điểm chỉ kiểm tra một lần mỗi khi nó trở thành gần nhất).
Ví dụ chạy tay
Ba điểm , , , trọng số đều bằng . Bắt đầu từ trọng tâm :
| Vòng | |||||
|---|---|---|---|---|---|
| 0 | |||||
| 1 | |||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 8 | |||||
| hội tụ |
Ở vòng 0, điểm gần nhất nên có trọng số lớn nhất và kéo về phía nó. giảm đều qua mỗi vòng. Điểm cuối cùng là điểm Fermat của tam giác (mọi góc của tam giác đều nhỏ hơn ): các góc đo được đều bằng (sai số dưới độ).
Đổi trọng số thành , . Tại : , , nên là trung vị, . Code dưới đây phát hiện điều này ngay ở vòng đầu nhờ phép kiểm tra điểm gần nhất, thay vì lặp hàng nghìn vòng tiến dần về .
Cài đặt
Dữ liệu: rồi dòng x y w. In giá trị nhỏ nhất và tọa độ trung vị.
#include <bits/stdc++.h>
using namespace std;
struct Pt {
double x, y;
};
// Tổng có trọng số khoảng cách từ P tới các điểm
double cost(const vector<Pt>& z, const vector<double>& w, Pt P) {
double s = 0;
for (size_t i = 0; i < z.size(); i++) s += w[i] * hypot(z[i].x - P.x, z[i].y - P.y);
return s;
}
// Điểm dữ liệu c có phải trung vị không? Điều kiện: |sum w_i (z_i - c)/|z_i - c|| <= tổng trọng số tại c
bool isOptimalAt(const vector<Pt>& z, const vector<double>& w, Pt c, double eps) {
double rx = 0, ry = 0, w0 = 0;
for (size_t i = 0; i < z.size(); i++) {
double d = hypot(z[i].x - c.x, z[i].y - c.y);
if (d < eps) w0 += w[i];
else rx += w[i] * (z[i].x - c.x) / d, ry += w[i] * (z[i].y - c.y) / d;
}
return hypot(rx, ry) <= w0;
}
// Trung vị hình học có trọng số: lặp Weiszfeld + hiệu chỉnh Vardi-Zhang khi P trùng một điểm
Pt geometricMedian(const vector<Pt>& z, const vector<double>& w, int maxIter = 10000) {
int n = z.size();
double W = 0, scale = 1;
Pt P{0, 0};
for (int i = 0; i < n; i++) { // điểm bắt đầu: trọng tâm có trọng số
P.x += w[i] * z[i].x, P.y += w[i] * z[i].y, W += w[i];
scale = max({scale, fabs(z[i].x), fabs(z[i].y)});
}
P.x /= W, P.y /= W;
const double eps = 1e-12 * scale;
int lastChecked = -1;
for (int it = 0; it < maxIter; it++) {
double nx = 0, ny = 0, den = 0, w0 = 0; // w0 = tổng trọng số các điểm trùng P
int nearest = 0;
double best = 1e300;
for (int i = 0; i < n; i++) {
double d = hypot(z[i].x - P.x, z[i].y - P.y);
if (d < best) best = d, nearest = i;
if (d < eps) { w0 += w[i]; continue; }
nx += w[i] * z[i].x / d, ny += w[i] * z[i].y / d, den += w[i] / d;
}
// Weiszfeld hội tụ rất chậm khi đích là một điểm dữ liệu: thử điểm gần nhất (mỗi điểm một lần)
if (nearest != lastChecked) {
lastChecked = nearest;
if (isOptimalAt(z, w, z[nearest], eps)) return z[nearest];
}
if (den == 0) break; // mọi điểm trùng P
Pt T{nx / den, ny / den}; // bước Weiszfeld thuần
Pt Q = T;
if (w0 > 0) {
// R = tổng w_i (z_i - P) / d_i = den * (T - P): "lực kéo" của các điểm còn lại
double r = den * hypot(T.x - P.x, T.y - P.y);
if (r <= w0) break; // lực kéo không thắng trọng số tại P: P tối ưu
double t = w0 / r; // đi một phần đường từ P tới T
Q = {(1 - t) * T.x + t * P.x, (1 - t) * T.y + t * P.y};
}
double move = hypot(Q.x - P.x, Q.y - P.y);
P = Q;
if (move < eps) break;
}
return P;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Pt> z(n);
vector<double> w(n);
for (int i = 0; i < n; i++) cin >> z[i].x >> z[i].y >> w[i];
Pt P = geometricMedian(z, w);
cout << fixed << setprecision(9) << cost(z, w, P) << '\n' << P.x << ' ' << P.y << '\n';
}
import math
import sys
def cost(z, w, p):
"""Tổng có trọng số khoảng cách từ p tới các điểm."""
return sum(wi * math.hypot(x - p[0], y - p[1]) for (x, y), wi in zip(z, w))
def is_optimal_at(z, w, c, eps):
"""Điểm dữ liệu c là trung vị khi |sum w_i (z_i - c)/|z_i - c|| <= tổng trọng số tại c."""
rx = ry = w0 = 0.0
for (x, y), wi in zip(z, w):
d = math.hypot(x - c[0], y - c[1])
if d < eps:
w0 += wi
else:
rx += wi * (x - c[0]) / d
ry += wi * (y - c[1]) / d
return math.hypot(rx, ry) <= w0
def geometric_median(z, w, max_iter=10000):
"""Trung vị hình học có trọng số: Weiszfeld + hiệu chỉnh Vardi-Zhang."""
W = sum(w)
px = sum(wi * x for (x, _), wi in zip(z, w)) / W # bắt đầu từ trọng tâm có trọng số
py = sum(wi * y for (_, y), wi in zip(z, w)) / W
scale = max([1.0] + [max(abs(x), abs(y)) for x, y in z])
eps = 1e-12 * scale
last_checked = -1
for _ in range(max_iter):
nx = ny = den = w0 = 0.0 # w0 = tổng trọng số các điểm trùng P
nearest, best = 0, float("inf")
for i, ((x, y), wi) in enumerate(zip(z, w)):
d = math.hypot(x - px, y - py)
if d < best:
best, nearest = d, i
if d < eps:
w0 += wi
continue
nx += wi * x / d
ny += wi * y / d
den += wi / d
# Weiszfeld hội tụ rất chậm khi đích là một điểm dữ liệu: thử điểm gần nhất (mỗi điểm một lần)
if nearest != last_checked:
last_checked = nearest
if is_optimal_at(z, w, z[nearest], eps):
return z[nearest]
if den == 0: # mọi điểm trùng P
break
tx, ty = nx / den, ny / den # bước Weiszfeld thuần
qx, qy = tx, ty
if w0 > 0:
# R = den * (T - P): "lực kéo" của các điểm còn lại
r = den * math.hypot(tx - px, ty - py)
if r <= w0: # lực kéo không thắng trọng số tại P: P tối ưu
break
t = w0 / r # đi một phần đường từ P tới T
qx, qy = (1 - t) * tx + t * px, (1 - t) * ty + t * py
move = math.hypot(qx - px, qy - py)
px, py = qx, qy
if move < eps:
break
return px, py
def main():
data = sys.stdin.read().split()
n = int(data[0])
z = [(float(data[1 + 3 * i]), float(data[2 + 3 * i])) for i in range(n)]
w = [float(data[3 + 3 * i]) for i in range(n)]
p = geometric_median(z, w)
print("%.9f\n%.9f %.9f" % (cost(z, w, p), p[0], p[1]))
main()
Ngưỡng dừng eps tỉ lệ với độ lớn tọa độ (scale), nên code dùng được cho cả tọa độ cỡ lẫn cỡ . Trên máy thử, điểm ngẫu nhiên chạy khoảng giây (C++); hội tụ sau khoảng vòng.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Một vòng Weiszfeld | thêm | |
| Kiểm tra tối ưu tại một điểm dữ liệu | thêm | |
| Toàn bộ | , là số vòng |
Vì sao? Mỗi vòng chỉ cộng dồn ba tổng , và tìm điểm gần nhất. Số vòng phụ thuộc vào hình dạng dữ liệu: hội tụ tuyến tính khi trung vị nằm xa các điểm dữ liệu (thường vài chục vòng cho ), và có thể rất chậm khi trung vị nằm sát (nhưng không trùng) một điểm dữ liệu; đặt giới hạn maxIter để không bao giờ chạy quá lâu.
⚠️ Lỗi thường gặp
- Nhầm trung vị với trọng tâm: trọng tâm cực tiểu tổng bình phương khoảng cách, không phải tổng khoảng cách. Một điểm ở rất xa kéo trọng tâm đi theo, nhưng gần như không ảnh hưởng trung vị.
- Chia cho khi trùng một điểm: bắt đầu từ một điểm dữ liệu, hoặc lặp tới đúng một điểm dữ liệu, làm
d = 0. Phải bỏ các điểm trùng khỏi tổng và dùng điều kiện (Vardi-Zhang), không phải cộng một epsilon tùy tiện vào (làm lệch đáp án khi trọng số lớn). - Dừng sớm vì bước nhỏ: bước nhỏ không có nghĩa là đã tới đích. Khi trung vị là một điểm dữ liệu, Weiszfeld đi những bước rất nhỏ mà vẫn còn cách đích xa; nếu thiếu phép kiểm tra điểm gần nhất, đáp án có thể lệch cỡ tương đối (đã gặp khi stress test: lệch trên giá trị với điểm, trong đó hai điểm trùng nhau và là trung vị) dù đã chạy vòng.
- Ngưỡng tuyệt đối với tọa độ lớn:
eps = 1e-12cố định là quá nhỏ với tọa độ (sai số làm tròn củadoublelớn hơn thế), bước lặp có thể dao động mãi ở mức sai số làm tròn và vòng lặp chỉ dừng khi hếtmaxIter. Dùng ngưỡng tương đối theo độ lớn tọa độ. - Dùng tìm kiếm tam phân lồng nhau cho lớn: tam phân theo rồi theo đúng (vì lồi) nhưng tốn , chậm hơn Weiszfeld hàng trăm lần. Chỉ hợp khi nhỏ hoặc để kiểm tra.
- Áp cho bài nhiều cơ sở như bài một cơ sở: bài -median (đặt điểm, mỗi điểm dữ liệu đi tới điểm gần nhất) không còn lồi; Weiszfeld chỉ giải được bước "đặt lại một cơ sở khi đã biết nhóm của nó", cần thêm tìm kiếm cục bộ.
Biến thể / Mở rộng
- Khoảng cách Manhattan: tách được theo hai trục, đáp án là trung vị có trọng số của các hoành độ và của các tung độ; xem khoảng cách Manhattan.
- Tìm kiếm tam phân hai chiều: vì lồi, tìm kiếm tam phân lồng nhau theo rồi cũng cho đáp án; dùng làm brute force để kiểm tra Weiszfeld.
- Nhiều cơ sở (-median): xen kẽ "gán mỗi điểm vào cơ sở gần nhất" và "đặt lại mỗi cơ sở ở trung vị nhóm của nó" (giống k-means nhưng dùng trung vị), kết hợp bước đổi chỗ để thoát cực tiểu địa phương.
- Cây Steiner Euclid: điểm Fermat là trường hợp một điểm rẽ nhánh của cây Steiner; với nhiều điểm rẽ nhánh thì cần dựng hình học (Melzak) chứ không phải trung vị.
- Xem thêm các kỹ thuật nền tảng ở Hình học.
Bài tập luyện
- Ăng-ten chuyển tiếp không gian con hành tinh (icpc26mbk): (Very Hard) Đặt ăng-ten để tổng khoảng cách có trọng số tới ăng-ten gần nhất gần tối ưu: tìm kiếm cục bộ, trong đó mỗi ăng-ten được đặt lại ở trung vị hình học (Weiszfeld có hiệu chỉnh Vardi-Zhang) của nhóm trạm của nó.
Bình luận