Wiki › Thuật toán › Hình học tính toán › Trung vị hình học (thuật toán Weiszfeld)

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.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 14 phút 5 lượt xem

Trung vị hình học (geometric median) của các điểm z1,…,zn trên mặt phẳng với trọng số dương w1,…,wn là điểm P làm nhỏ nhất tổng có trọng số các khoảng cách Euclid

f(P)=∑i=1nwi‖zi−P‖.

Đâ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 n≥5. 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 O(n), thường hội tụ sau vài chục đến vài trăm vòng.

Với n=3 điểm cùng trọng số và mọi góc của tam giác nhỏ hơn 120°, trung vị chính là điểm Fermat (nhìn ba cạnh dưới góc 120°); nếu có góc ≥120° thì là đỉnh của góc đó.

Ý tưởng / Trực giác

Hàm lồi. Mỗi ‖zi−P‖ là hàm lồi theo P, nên f lồi; nếu các điểm không cùng nằm trên một đường thẳng thì f 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 f giảm dần là đủ.

Điều kiện tối ưu. Khi P không trùng điểm nào, gradient là

∇f(P)=∑iwiP−zi‖zi−P‖.

Trực giác vật lý: mỗi điểm zi kéo P về phía nó bằng một sợi dây có lực không đổi wi (không phụ thuộc khoảng cách). P tối ưu khi tổng các lực bằng 0. Với ba điểm trọng số bằng nhau, ba vectơ đơn vị có tổng 0 đúng khi chúng lệch nhau 120°: đó là điểm Fermat.

Phép lặp Weiszfeld. Đặt di=‖zi−P‖. Giải ∇f=0 theo P như thể các di là hằng số:

Pmới=∑iwizi/di∑iwi/di.

Đây là trung bình có trọng số wi/di: điểm càng gần P càng có tiếng nói lớn. Có thể chứng minh (bằng bất đẳng thức a2b≥2a−b áp cho hàm thay thế bậc hai ∑wi‖zi−Q‖2/di, mà Pmới là cực tiểu) rằng f(Pmới)≤f(P), dấu bằng chỉ khi P đã 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 P trùng một điểm dữ liệu. Công thức chia cho di=0. Gọi w0 là tổng trọng số các điểm trùng P và R=∑di>0wi(zi−P)/di 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à

‖R‖≤w0:

điểm tại P "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 T) rồi chỉ đi một phần quãng đường: Pmới=(1−t)T+tP với t=w0/‖R‖.

Hội tụ chậm về một đỉnh. Nếu trung vị là một điểm dữ liệu zj (ví dụ zj có trọng số rất lớn), Weiszfeld tiến về zj rất chậm vì càng gần zj thì bước càng nhỏ. Cách chữa: ở mỗi vòng, nếu điểm dữ liệu gần P nhất thay đổi thì kiểm tra trực tiếp điều kiện ‖R‖≤w0 tại điểm đó (tốn thêm O(n), 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 A=(0,0), B=(4,0), C=(0,3), trọng số đều bằng 1. Bắt đầu từ trọng tâm (4/3,1):

Vòng k Pk dA dB dC f(Pk)
0 (1.3333,1.0000) 1.6667 2.8480 2.4037 6.91837
1 (1.0273,0.9129) 1.3743 3.1097 2.3262 6.81026
2 (0.8697,0.8719) 1.2315 3.2495 2.2989 6.77991
3 (0.7917,0.8393) 1.1538 3.3162 2.3012 6.77123
4 (0.7526,0.8134) 1.1081 3.3478 2.3125 6.76837
8 (0.7063,0.7648) 1.0410 3.3813 2.3441 6.76651
hội tụ (0.695789,0.751176) 6.766433

Ở vòng 0, điểm A gần nhất nên có trọng số 1/dA lớn nhất và kéo P về phía nó. f 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 ABC đều nhỏ hơn 120°): các góc APB^,BPC^,CPA^ đo được đều bằng 120° (sai số dưới 10−7 độ).

Đổi trọng số thành wA=5, wB=wC=1. Tại A: R=(1,0)+(0,1), ‖R‖=2≈1.414≤5=w0, nên A là trung vị, f(A)=4+3=7. 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ề A.

Cài đặt

Dữ liệu: n rồi n dòng x y w. In giá trị f nhỏ nhất và tọa độ trung vị.

C++
#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';
}
Python
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ỡ 1 lẫn cỡ 105. Trên máy thử, n=105 điểm ngẫu nhiên chạy khoảng 0,15 giây (C++); n=104 hội tụ sau khoảng 30 vòng.

Độ phức tạp

Thao tác Thời gian Bộ nhớ
Một vòng Weiszfeld O(n) O(1) thêm
Kiểm tra tối ưu tại một điểm dữ liệu O(n) O(1) thêm
Toàn bộ O(n·K), K là số vòng O(n)

Vì sao? Mỗi vòng chỉ cộng dồn ba tổng ∑wizi/di, ∑wi/di và tìm điểm gần nhất. Số vòng K 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 10−9), 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 ∑wizi∑wi 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 0 khi P 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 ‖R‖≤w0 (Vardi-Zhang), không phải cộng một epsilon tùy tiện vào di (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ỡ 10−6 tương đối (đã gặp khi stress test: f lệch 4·10−5 trên giá trị 23.78 với 4 điểm, trong đó hai điểm trùng nhau và là trung vị) dù đã chạy 104 vòng.
  • Ngưỡng tuyệt đối với tọa độ lớn: eps = 1e-12 cố định là quá nhỏ với tọa độ 105 (sai số làm tròn của double lớ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ết maxIter. 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 n lớn: tam phân theo x rồi theo y đúng (vì f lồi) nhưng tốn O(n·1002), chậm hơn Weiszfeld hàng trăm lần. Chỉ hợp khi n nhỏ hoặc để kiểm tra.
  • Áp cho bài nhiều cơ sở như bài một cơ sở: bài m-median (đặt m đ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: ∑wi(|xi−X|+|yi−Y|) 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ì f lồi, tìm kiếm tam phân lồng nhau theo x rồi y cũng cho đáp án; dùng làm brute force để kiểm tra Weiszfeld.
  • Nhiều cơ sở (m-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 m ă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ó.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0