Wiki › Thuật toán › Thuật toán ngẫu nhiên (Randomized Algorithms)

Thuật toán ngẫu nhiên (Randomized Algorithms)

Sinh số ngẫu nhiên đúng cách, Las Vegas và Monte Carlo, xor/sum hashing, băm chống hack, Freivalds, lấy mẫu ngẫu nhiên, trộn ngẫu nhiên (đường tròn bao nhỏ nhất) và mô phỏng tôi luyện.

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

Thuật toán ngẫu nhiên (randomized algorithm) là thuật toán được phép "tung đồng xu" trong lúc chạy: chọn chốt ngẫu nhiên, trộn input, gán trọng số ngẫu nhiên, lấy mẫu ngẫu nhiên. Đổi lại một xác suất sai (hoặc thời gian chạy dao động) nhỏ tới mức bỏ qua được, ta thường được thuật toán ngắn hơn và nhanh hơn hẳn lời giải tất định. Ví dụ: kiểm tra đoạn con a[l..r] có phải hoán vị của 1..(r−l+1) hay không trong O(1) mỗi truy vấn sau O(n) tiền xử lý, kiểm tra A·B=C cho ma trận n×n trong O(n2) thay vì O(n3), hay tìm đường tròn nhỏ nhất bao n điểm trong O(n) kỳ vọng.

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

Vì sao ngẫu nhiên lại giúp được?

Lời giải tất định có một điểm yếu: người ra đề biết trước nó sẽ làm gì, nên có thể dựng test xấu nhất. Quicksort chọn chốt là phần tử đầu tiên chạy O(n2) trên mảng đã sắp xếp; hash với cơ số cố định bị dựng sẵn hai xâu đụng độ; unordered_map mặc định bị dựng sẵn dãy khóa rơi cùng một ô.

Khi thuật toán dùng số ngẫu nhiên được sinh lúc chạy, test phải được viết ra trước khi đồng xu được tung. Không test nào "xấu" với mọi kết quả tung, nên phân tích chỉ cần chứng minh: với mọi input, xác suất (lấy theo đồng xu) gặp chuyện xấu là nhỏ. Đó là toàn bộ triết lý của phần này.

Las Vegas và Monte Carlo
Las Vegas Monte Carlo
Kết quả Luôn đúng Có thể sai với xác suất nhỏ
Thời gian Ngẫu nhiên, ta phân tích kỳ vọng Cố định (bị chặn trước)
Ví dụ Quicksort chốt ngẫu nhiên, treap, đường tròn bao nhỏ nhất, tìm phần tử đa số có kiểm tra lại Hash xâu, xor hashing, Freivalds, Miller-Rabin

Hai loại đổi được cho nhau:

  • Monte Carlo thành Las Vegas khi kiểm tra được đáp án rẻ: cứ thử ngẫu nhiên, đáp án nào qua bước kiểm tra thì chắc chắn đúng; lặp đến khi gặp.
  • Las Vegas thành Monte Carlo: chạy tối đa một ngân sách thời gian, hết thì dừng và chấp nhận có thể chưa tìm thấy.
Khuếch đại xác suất (amplification)

Giả sử một lần chạy Monte Carlo có sai một phía: nếu đáp án là "khác" thì lần chạy báo "bằng" với xác suất ≤p (ví dụ p=12 với Freivalds). Chạy k lần độc lập, chỉ kết luận "bằng" khi cả k lần đều báo "bằng":

Pr[sai]≤pk.

Với p=12 và k=30, xác suất sai ≤2−30≈10−9: nhỏ hơn xác suất máy chấm bị lỗi phần cứng. Khi phải trả lời q câu hỏi, dùng chặn hợp (union bound): xác suất có ít nhất một câu sai ≤q·pk.

Sinh số ngẫu nhiên đúng cách

C++: dùng mt19937, đừng dùng rand()
C++
#include <bits/stdc++.h>
using namespace std;

// One global generator, seeded once from the clock.
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// Uniform integer in [lo, hi] (both inclusive).
int rand_int(int lo, int hi) {
    return uniform_int_distribution<int>(lo, hi)(rng);
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    shuffle(a.begin(), a.end(), rng);       // random permutation
    for (int x : a) printf("%d ", x);
    printf("\n%d\n", rand_int(1, 6));         // roll a die
}
Python
import random

a = [1, 2, 3, 4, 5]
random.shuffle(a)             # random permutation, in place
print(a)
print(random.randint(1, 6))   # integer in [1, 6], both ends inclusive
print(random.getrandbits(64)) # random 64-bit integer, good for hashing
print(random.choice(a))       # random element
  • mt19937 sinh số 32 bit, mt19937_64 sinh số 64 bit (dùng cho hash). Gọi rng() trả về một số ngẫu nhiên đều trên toàn bộ miền.
  • uniform_int_distribution<int>(lo, hi) cho số đều trong [lo,hi], không bị lệch như rng() % n.
  • shuffle(first, last, rng) trộn đều. Hàm cũ random_shuffle đã bị xóa khỏi C++17.
  • Hạt giống (seed) lấy từ chrono::steady_clock, đổi theo từng nano giây, nên mỗi lần chạy khác nhau.

Vì sao không dùng rand():

  • Trên Windows (MinGW, MSVC) RAND_MAX = 32767, nên rand() % 100000 không bao giờ ra số ≥32768. Code chạy đúng trên Linux nhưng sai trên máy khác.
  • rand() % n bị lệch: khi RAND_MAX + 1 không chia hết cho n, các số nhỏ xuất hiện nhiều hơn.
  • srand(time(0)) đổi seed theo giây, và chất lượng bộ sinh rand() kém (bộ sinh đồng dư tuyến tính, bit thấp có chu kỳ ngắn).
Python: random là đủ

Module random của Python cũng dùng Mersenne Twister và tự lấy seed từ hệ điều hành khi được import, nên không cần gọi random.seed(). Đừng gọi random.seed(0) hay bất kỳ seed cố định nào trong bài nộp.

Bài toán mẫu: đoạn con có phải hoán vị không? (xor hashing)

Đề. Cho mảng a1..an với 1≤ai≤n và q truy vấn (l,r). Với mỗi truy vấn, cho biết đoạn a[l..r] có phải là một hoán vị của 1,2,…,k với k=r−l+1 không. Giới hạn n,q≤2·105.

Cách tất định cần segment tree (kiểm tra max bằng k và không có phần tử lặp), khá dài. Cách ngẫu nhiên chỉ cần mảng tiền tố.

Ý tưởng

Gán cho mỗi giá trị v∈[1,n] một dấu vân tay zv là số ngẫu nhiên 64 bit. Định nghĩa "dấu vân tay" của một đoạn là xor các z của các phần tử trong đoạn:

F(l,r)=zal⊕zal+1⊕⋯⊕zar=Pr⊕Pl−1,

với Pi=Pi−1⊕zai là xor tiền tố. Dấu vân tay của tập chuẩn {1..k} là Hk=z1⊕⋯⊕zk. Trả lời "YES" khi và chỉ khi F(l,r)=Hk.

Vì sao đúng (với xác suất cao).

  • Nếu đoạn là hoán vị của 1..k thì hai vế là xor của cùng một tập số, nên luôn bằng nhau. Không bao giờ báo sai "NO".
  • Nếu đoạn không là hoán vị: xor triệt tiêu các giá trị xuất hiện số chẵn lần, nên F(l,r) là xor của tập S gồm các giá trị xuất hiện lẻ lần. Vì đoạn có đúng k phần tử, S={1..k} chỉ xảy ra khi mỗi giá trị 1..k xuất hiện đúng một lần, tức là đoạn là hoán vị. Vậy S≠{1..k}, và F⊕Hk là xor của tập khác rỗng S△{1..k} các số ngẫu nhiên độc lập. Xor của các số đều và độc lập là một số đều trên 264 giá trị, nên nó bằng 0 với xác suất đúng 2−64.

Với q truy vấn, xác suất có ít nhất một câu sai ≤q·2−64≈10−14.

Ví dụ chạy tay

Mảng a=[2,1,3,1,2]. Để dễ nhìn, ta dùng dấu vân tay 4 bit (bài thật dùng 64 bit): z1=5=01012, z2=3=00112, z3=9=10012.

array
2 1 3 1 2
step Mảng a (chỉ số từ 1)
step Truy vấn (1, 3): đoạn [2, 1, 3], k = 3
highlight green 1..3
step Truy vấn (2, 4): đoạn [1, 3, 1], k = 3
clear
highlight red 2..4
step Truy vấn (4, 5): đoạn [1, 2], k = 2
clear
highlight green 4..5

Bảng xor tiền tố Pi và dấu vân tay tập chuẩn Hk:

i 0 1 2 3 4 5
ai 2 1 3 1 2
zai 0011 0101 1001 0101 0011
Pi 0000 0011 0110 1111 1010 1001

H1=0101,H2=0101⊕0011=0110,H3=0110⊕1001=1111.

Trả lời các truy vấn:

Truy vấn Đoạn Pr⊕Pl−1 Hk Kết luận
(1,3) [2,1,3] 1111⊕0000=1111 H3=1111 YES
(2,4) [1,3,1] 1010⊕0011=1001 H3=1111 NO
(4,5) [1,2] 1001⊕1111=0110 H2=0110 YES
(3,3) [3] 1111⊕0110=1001 H1=0101 NO
(2,2) [1] 0110⊕0011=0101 H1=0101 YES

Ở truy vấn (2,4), hai số 1 triệt tiêu nhau, chỉ còn z3=1001; nó khác H3 nên kết luận đúng là NO. Với 4 bit, xác suất đụng độ là 116 mỗi truy vấn, quá lớn; với 64 bit nó là 2−64.

Cài đặt

Input: dòng đầu n,q; dòng hai a1..an; q dòng sau mỗi dòng l,r. Output: YES hoặc NO cho từng truy vấn.

C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    // Seed from the clock: each run gets different random numbers,
    // so nobody can prepare a test against our hash in advance.
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

    int n, q;
    scanf("%d %d", &n, &q);
    vector<unsigned long long> z(n + 1), H(n + 1, 0), P(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        z[v] = rng();               // random 64-bit "fingerprint" of value v
        H[v] = H[v - 1] ^ z[v];     // H[k] = fingerprint of the set {1..k}
    }
    for (int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);            // 1 <= a <= n
        P[i] = P[i - 1] ^ z[a];     // prefix xor of fingerprints
    }
    while (q--) {
        int l, r;
        scanf("%d %d", &l, &r);
        // xor of a[l..r] fingerprints, compared with the set {1..len}
        bool ok = (P[r] ^ P[l - 1]) == H[r - l + 1];
        puts(ok ? "YES" : "NO");
    }
}
Python
import sys
import random


def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    # random is seeded from the OS (time / urandom) on import: no fixed seed
    z = [0] + [random.getrandbits(64) for _ in range(n)]
    H = [0] * (n + 1)
    for v in range(1, n + 1):
        H[v] = H[v - 1] ^ z[v]           # fingerprint of the set {1..v}
    P = [0] * (n + 1)
    for i in range(1, n + 1):
        P[i] = P[i - 1] ^ z[int(data[1 + i])]  # prefix xor of fingerprints
    out = []
    pos = 2 + n
    for _ in range(q):
        l, r = int(data[pos]), int(data[pos + 1])
        pos += 2
        out.append("YES" if P[r] ^ P[l - 1] == H[r - l + 1] else "NO")
    print("\n".join(out))


main()

Với input của ví dụ trên (5 5, 2 1 3 1 2, rồi 5 truy vấn), cả hai chương trình in YES NO YES NO YES (mỗi từ một dòng), và đã được đối chiếu với lời giải vét cạn trên vài trăm test ngẫu nhiên.

Độ phức tạp: O(n+q) thời gian, O(n) bộ nhớ (ba mảng z,H,P). Xác suất sai ≤q·2−64.

Các kỹ thuật ngẫu nhiên kinh điển

1. Trộn ngẫu nhiên để phá thứ tự xấu: đường tròn bao nhỏ nhất

Nhiều thuật toán gia tăng (incremental: thêm lần lượt từng phần tử, cập nhật đáp án) có trường hợp xấu O(n2) hoặc tệ hơn, nhưng chỉ khi các phần tử đến theo thứ tự xấu. Trộn input trước khi chạy biến thứ tự thành ngẫu nhiên, và phân tích kỳ vọng cho kết quả tốt với mọi input. Ví dụ quen thuộc: quicksort với chốt ngẫu nhiên, dựng cây nhị phân tìm kiếm bằng cách chèn theo thứ tự ngẫu nhiên, và thuật toán Welzl tìm đường tròn nhỏ nhất chứa n điểm dưới đây.

Duyệt điểm theo thứ tự đã trộn và giữ đường tròn C bao các điểm đã xét. Khi điểm pi nằm ngoài C, đường tròn mới chắc chắn đi qua pi, nên ta dựng lại bằng hai vòng lặp con với pi (rồi pj) được cố định trên biên.

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct P { double x, y; };
struct Circle { P c; double r; };
const double EPS = 1e-9;

double dist(P a, P b) { return hypot(a.x - b.x, a.y - b.y); }
bool inside(const Circle& C, P p) { return dist(C.c, p) <= C.r + EPS; }

Circle from2(P a, P b) {
    P m = {(a.x + b.x) / 2, (a.y + b.y) / 2};
    return {m, dist(a, m)};
}
Circle from3(P a, P b, P c) {             // circumcircle
    double bx = b.x - a.x, by = b.y - a.y, cx = c.x - a.x, cy = c.y - a.y;
    double d = 2 * (bx * cy - by * cx);
    if (fabs(d) < EPS) {                  // collinear: use the farthest pair
        Circle best = from2(a, b);
        for (Circle t : {from2(a, c), from2(b, c)}) if (t.r > best.r) best = t;
        return best;
    }
    double ux = (cy * (bx * bx + by * by) - by * (cx * cx + cy * cy)) / d;
    double uy = (bx * (cx * cx + cy * cy) - cx * (bx * bx + by * by)) / d;
    P o = {a.x + ux, a.y + uy};
    return {o, dist(o, a)};
}

// Smallest enclosing circle, expected O(n) after a random shuffle.
Circle min_circle(vector<P> p) {
    shuffle(p.begin(), p.end(), rng);     // kills adversarial input order
    int n = p.size();
    Circle C = {p[0], 0};
    for (int i = 1; i < n; i++) {
        if (inside(C, p[i])) continue;    // usually true: cheap step
        C = {p[i], 0};                    // p[i] must lie on the boundary
        for (int j = 0; j < i; j++) {
            if (inside(C, p[j])) continue;
            C = from2(p[i], p[j]);        // p[i], p[j] on the boundary
            for (int k = 0; k < j; k++)
                if (!inside(C, p[k])) C = from3(p[i], p[j], p[k]);
        }
    }
    return C;
}

Với 5 điểm (0,0),(0,1),(1,0),(1,1),(0.5,0.5), hàm trả về tâm (0.5,0.5), bán kính 0.7071; với (0,0),(4,0),(2,1) trả về tâm (2,0), bán kính 2 (cài đặt đã được đối chiếu với vét cạn mọi cặp và bộ ba điểm).

Vì sao kỳ vọng O(n) (phân tích lùi). Đường tròn bao nhỏ nhất của i điểm đầu được xác định bởi nhiều nhất 3 điểm trên biên. Vì thứ tự là ngẫu nhiên, điểm pi là một điểm đều trong i điểm đầu, nên xác suất nó là một trong ≤3 điểm xác định biên (tức là nằm ngoài đường tròn của i−1 điểm trước) là ≤3i. Khi đó vòng lặp con tốn O(i) kỳ vọng (cùng lập luận áp dụng cho vòng j). Tổng kỳ vọng:

∑i=1n(O(1)+3i·O(i))=O(n).

Nếu không trộn, người ra đề có thể sắp điểm sao cho mỗi điểm mới đều nằm ngoài, và thuật toán chạy O(n3). Ý tưởng "trộn rồi gia tăng" cũng cho thuật toán tìm cặp điểm gần nhất trong O(n) kỳ vọng bằng lưới ô vuông.

2. Lấy mẫu ngẫu nhiên: phần tử đa số và "ít nhất một nửa"

Nếu một tính chất đúng với ít nhất một nửa số phần tử, thì một phần tử chọn ngẫu nhiên có tính chất đó với xác suất ≥12. Chọn 30 lần, xác suất trượt cả 30 lần ≤2−30.

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// Returns an element occurring > n/2 times, or -1 if (probably) none.
// Each try picks a random index; if a majority exists, a try hits it
// with probability > 1/2, so 30 tries all miss with probability < 2^-30.
int find_majority(const vector<int>& a, int tries = 30) {
    int n = a.size();
    for (int t = 0; t < tries; t++) {
        int cand = a[uniform_int_distribution<int>(0, n - 1)(rng)];
        int c = count(a.begin(), a.end(), cand);   // O(n) check
        if (2 * c > n) return cand;                // verified: answer is surely right
    }
    return -1;   // Monte Carlo: wrong with probability < 2^-30
}

Với [3,1,3,3,2,3,3] hàm trả về 3; với [1,2,3,1,2,3] trả về −1. Riêng bài phần tử đa số có lời giải tất định O(n) (thuật toán bỏ phiếu Boyer-Moore), nhưng kỹ thuật lấy mẫu tổng quát hơn nhiều, vì nó áp dụng được cho mọi tính chất kiểm tra được:

  • Ước chung lớn nhất của ít nhất một nửa dãy (bài kinh điển "Ghd"): đáp án g chia hết ít nhất n2 số, nên một số ngẫu nhiên ax là bội của g với xác suất ≥12. Thử khoảng 10 số ngẫu nhiên, với mỗi số duyệt các ước của nó và đếm bội. Không có lời giải tất định đơn giản.
  • Đường thẳng đi qua nhiều điểm nhất khi biết đáp án chứa ≥nk điểm: chọn ngẫu nhiên hai điểm, xác suất cả hai nằm trên đường đáp án ≈1k2, thử O(k2) lần.
  • Truy vấn đoạn "có phần tử xuất hiện >len2 lần không": lấy ngẫu nhiên vài vị trí trong đoạn, đếm số lần xuất hiện bằng tìm kiếm nhị phân trên danh sách vị trí của giá trị đó, O(klogn) mỗi truy vấn.
3. Băm chống hack: hash ngẫu nhiên cho bảng băm và xâu

Bảng băm. Hàm băm mặc định của unordered_map<long long, ...> trong GCC là hàm đồng nhất h(x)=x, chia lấy dư cho số ô (một số nguyên tố trong danh sách cố định). Người ra đề có thể sinh 105 khóa là bội của số nguyên tố đó, tất cả rơi vào một ô, và mỗi thao tác thành O(n). Cách chữa là dùng hàm trộn bit splitmix64 kèm một offset ngẫu nhiên chọn lúc chạy (xem thêm trang Bảng băm):

struct SplitMixHash {
    // splitmix64: mixes all 64 bits, so nearby keys spread out
    static unsigned long long splitmix64(unsigned long long x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(unsigned long long x) const {
        // random offset chosen once per run: the hacker cannot know it
        static const unsigned long long SEED =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};

unordered_map<long long, int, SplitMixHash> cnt;

Trong Python, hash(x) == x với số nguyên nhỏ nên dict/set các số nguyên cũng có thể bị dựng test xấu. Mẹo đơn giản: chọn R = random.getrandbits(62) một lần rồi dùng khóa x ^ R thay cho x.

Hash xâu. Hash đa thức H(s)=∑siBL−1−imodM có cận đụng độ L−1M cho mỗi cặp xâu chỉ khi cơ số B được chọn ngẫu nhiên lúc chạy. Cơ số cố định như 31 hay 131 thì đề có thể chứa sẵn cặp xâu đụng độ. Chi tiết, cách chọn modulo và nghịch lý ngày sinh ở trang Hash xâu.

4. Kiểm tra tích ma trận: thuật toán Freivalds

Cho ba ma trận n×n là A,B,C, kiểm tra A·B=C. Nhân thật tốn O(n3). Freivalds chọn vector ngẫu nhiên x∈{0,1}n và so sánh A(Bx) với Cx: ba phép nhân ma trận với vector, mỗi phép O(n2).

Vì sao xác suất sai ≤12. Đặt D=AB−C. Nếu AB≠C thì D có một ô dij≠0. Cố định mọi xk với k≠j; phần tử thứ i của Dx là dijxj+c với c không phụ thuộc xj. Trong hai giá trị xj=0 và xj=1, nhiều nhất một giá trị làm biểu thức bằng 0. Vậy Pr[Dx=0]≤12. Lặp 20 lần cho xác suất sai ≤2−20.

typedef long long ll;
const ll MOD = 1000000007;

// y = M * x  (mod MOD), O(n^2)
vector<ll> mul_vec(const vector<vector<ll>>& M, const vector<ll>& x) {
    int n = M.size();
    vector<ll> y(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) y[i] = (y[i] + M[i][j] * x[j]) % MOD;
    return y;
}

// Checks A * B == C with error probability <= (1/2)^rounds.
bool freivalds(const vector<vector<ll>>& A, const vector<vector<ll>>& B,
               const vector<vector<ll>>& C, int rounds = 20) {
    int n = A.size();
    for (int it = 0; it < rounds; it++) {
        vector<ll> x(n);
        for (auto& v : x) v = rng() & 1;            // random 0/1 vector
        // compare A(Bx) with Cx: three O(n^2) products instead of O(n^3)
        if (mul_vec(A, mul_vec(B, x)) != mul_vec(C, x)) return false;
    }
    return true;
}

Với A=(1234), B=(5678), hàm trả về đúng với C=(19224350) và sai với C có ô cuối là 51. Đây là thuật toán Monte Carlo sai một phía: khi trả về false thì chắc chắn AB≠C.

5. Gán trọng số ngẫu nhiên: sum hashing và xor hashing

Bài mẫu ở trên là một trường hợp của kỹ thuật rất mạnh: thay mỗi đối tượng bằng một số ngẫu nhiên lớn, rồi biến câu hỏi "hai tập/đa tập có bằng nhau không" thành "hai tổng có bằng nhau không". Tổng (hoặc xor) tính được bằng tiền tố, Fenwick, segment tree, nên các cấu trúc dữ liệu quen thuộc trả lời được câu hỏi về tập hợp.

Muốn so sánh Dùng Lý do
Hai tập (không lặp) xor hoặc tổng Cả hai đều được
Hai đa tập (có lặp, so cả số lần) tổng mod 264 xor triệt tiêu phần tử lặp chẵn lần
Chỉ quan tâm tính chẵn lẻ số lần xuất hiện xor Đúng thứ xor tính

Một số dạng điển hình:

  • Hai đỉnh có cùng tập kề không: gán zv ngẫu nhiên, đặt S(v)=∑u∈N(v)zu. Hai đỉnh có cùng tập kề khi và chỉ khi (với xác suất cao) S bằng nhau, nên chỉ cần sắp xếp n số thay vì so n2 cặp danh sách.
  • Hai ô có bị bao bởi cùng tập hình chữ nhật không: mỗi hình chữ nhật một trọng số ngẫu nhiên, cộng vào mọi ô bên trong (Fenwick 2D, cộng hình chữ nhật, hỏi điểm). Hai ô cùng vùng khi tổng bằng nhau.
  • Đoạn chứa trọn mọi lần xuất hiện của mỗi giá trị nó chứa: với mỗi giá trị, gán trọng số ngẫu nhiên cho các lần xuất hiện sao cho xor của tất cả bằng 0 (lần cuối nhận xor các lần trước). Đoạn [L,R] thỏa mãn khi và chỉ khi xor đoạn bằng 0, tức PR=PL−1.
6. Các thuật toán ngẫu nhiên khác trên wiki
  • Kiểm tra nguyên tố Miller-Rabin là Monte Carlo sai một phía: mỗi cơ số ngẫu nhiên phát hiện hợp số với xác suất ≥34. Pollard-Rho phân tích thừa số với thời gian kỳ vọng O(n1/4) nhờ nghịch lý ngày sinh. Xem Miller-Rabin và Pollard-Rho.
  • Treap gán mỗi nút một độ ưu tiên ngẫu nhiên; cây khi đó có dạng như BST dựng từ thứ tự chèn ngẫu nhiên, độ sâu kỳ vọng O(logn). Xem Treap.
7. Mô phỏng tôi luyện (simulated annealing): heuristic, không phải thuật toán đúng

Khi bài là tối ưu hóa khó (hoặc bài chấm điểm theo độ tốt của đáp án), mô phỏng tôi luyện là một heuristic ngẫu nhiên hay dùng: từ trạng thái hiện tại, thử một bước đi ngẫu nhiên nhỏ; nhận ngay nếu tốt hơn, nhận cả bước tệ hơn một lượng Δ với xác suất e−Δ/T. "Nhiệt độ" T giảm dần: lúc đầu đi lung tung để thoát cực tiểu địa phương, về sau gần như chỉ đi xuống.

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double rnd01() { return uniform_real_distribution<double>(0, 1)(rng); }

// Toy problem: find (x, y) minimizing the sum of distances to given points.
vector<pair<double, double>> pts = {{0, 0}, {10, 0}, {0, 10}, {10, 10}};
double cost(double x, double y) {
    double s = 0;
    for (auto [px, py] : pts) s += hypot(x - px, y - py);
    return s;
}

int main() {
    double x = 0, y = 0, cur = cost(x, y), best = cur;
    for (double T = 10; T > 1e-6; T *= 0.999) {        // temperature cools down
        double nx = x + (rnd01() * 2 - 1) * T;          // neighbour: small random move
        double ny = y + (rnd01() * 2 - 1) * T;
        double nc = cost(nx, ny);
        // always accept a better state; accept a worse one with prob e^{-delta/T}
        if (nc < cur || rnd01() < exp((cur - nc) / T)) {
            x = nx, y = ny, cur = nc;
            best = min(best, cur);
        }
    }
    printf("%.4f\n", best);   // optimum is 4 * 5*sqrt(2) = 28.2843 at (5, 5)
}

Chạy thử cho kết quả khoảng 28.284 đến 28.285, xấp xỉ tối ưu 202≈28.2843 nhưng không chính xác tuyệt đối và không có bảo đảm nào. Với bài này có thuật toán đúng là Weiszfeld. Chỉ dùng annealing khi không tìm được lời giải chính xác, hoặc để vét điểm subtask.

Độ phức tạp

Với thuật toán ngẫu nhiên ta nói về thời gian kỳ vọng (Las Vegas) hoặc xác suất sai (Monte Carlo). Kỳ vọng được lấy theo các đồng xu của thuật toán, không phải theo input, nên nó đúng cho mọi input kể cả test xấu nhất.

Kỹ thuật Thời gian Bộ nhớ Xác suất sai
Xor hashing đoạn là hoán vị O(n+q) O(n) ≤q·2−64
Đường tròn bao nhỏ nhất (Welzl) O(n) kỳ vọng O(n) 0 (Las Vegas)
Phần tử đa số, k lần thử O(kn) O(1) thêm ≤2−k
Freivalds, k vòng O(kn2) O(n) thêm ≤2−k
Bảng băm ngẫu nhiên O(1) kỳ vọng mỗi thao tác O(n) 0 (chỉ ảnh hưởng tốc độ)

Lý giải ngắn:

  • Xor hashing: mỗi phần tử đóng góp một phép xor vào mảng tiền tố, mỗi truy vấn hai lần tra mảng và một phép so sánh. Xác suất sai mỗi truy vấn là 2−64 (xor các số đều độc lập là đều), cộng dồn theo chặn hợp.
  • Welzl: điểm thứ i gây "dựng lại" với xác suất ≤3i, mỗi lần dựng lại tốn O(i) kỳ vọng, tổng ∑3i·i=O(n).
  • Lấy mẫu và Freivalds: mỗi lần thử độc lập thất bại với xác suất ≤12, nên k lần đều thất bại với xác suất ≤2−k; mỗi lần thử tốn một lượt kiểm tra O(n) hoặc O(n2).
  • Bảng băm: với hàm băm ngẫu nhiên, số khóa kỳ vọng trong một ô là nsố ô=O(1).

⚠️ Lỗi thường gặp

  • Seed cố định bị dựng test. mt19937 rng; (không truyền seed) luôn dùng seed mặc định 5489, mt19937 rng(42) hay srand(0) cũng vậy: mọi lần chạy ra cùng một dãy số. Ai có code của bạn (hệ thống hack, người ra đề chuẩn bị test anti-hash cho các seed phổ biến) đều dựng được test làm thuật toán sai hoặc chậm. Luôn seed bằng chrono::steady_clock::now().time_since_epoch().count(). Riêng Python, random tự seed từ hệ điều hành, chỉ cần đừng gọi random.seed(hằng_số).
  • Dùng rand(). Triệu chứng: đúng trên Linux, sai hoặc TLE trên Windows vì RAND_MAX = 32767; số ngẫu nhiên lớn không bao giờ xuất hiện, phân bố lệch. Dùng mt19937 và uniform_int_distribution.
  • Hash 32 bit và nghịch lý ngày sinh. Một cặp đụng độ với xác suất 2−32 nghe nhỏ, nhưng k giá trị hash tạo ra ≈k22 cặp. Với k=105, số cặp đụng độ kỳ vọng ≈10102·232≈1.2: gần như chắc chắn sai. Khi đưa nhiều hash vào set/map/sắp xếp, dùng hash 64 bit (mt19937_64, unsigned long long) hoặc double hash.
  • Dùng xor khi cần so sánh đa tập. z⊕z=0, nên đa tập {1,1,2} và {2} có cùng xor. Bài mẫu chỉ an toàn vì độ dài đoạn bằng đúng k (đã chứng minh ở trên). Khi cần đếm cả số lần xuất hiện, dùng tổng mod 264 và nhớ so độ dài (hoặc số phần tử) riêng nếu cần.
  • Hiểu sai cận sai số Monte Carlo. Cận pk chỉ đúng khi k lần chạy độc lập. Lỗi điển hình: tạo mt19937 rng(seed) bên trong vòng lặp với cùng seed (hoặc seed theo time(0) thay đổi theo giây), nên k lần thử dùng cùng một dãy số và xác suất sai vẫn là p, không phải pk. Tạo một bộ sinh toàn cục và dùng xuyên suốt. Và nhớ nhân với số truy vấn: 106 truy vấn với mỗi câu sai 2−20 cho xác suất có câu sai ≈1, phải tăng số vòng lên khoảng 40.
  • Quên trộn ở thuật toán gia tăng. Welzl hay quicksort viết đúng nhưng quên shuffle (hoặc chọn chốt cố định) vẫn đúng đáp án nhưng TLE O(n2) hoặc O(n3) trên test có thứ tự đặc biệt (mảng đã sắp xếp, điểm trên đường tròn theo thứ tự góc).
  • Kỳ vọng không phải trường hợp xấu nhất của một lần chạy. Thuật toán Las Vegas O(n) kỳ vọng có thể (với xác suất cực nhỏ) chạy lâu hơn. Đừng tối ưu bằng cách "chạy đến khi hết thời gian" dựa trên đồng hồ nếu không cần: kết quả khó tái hiện khi debug. Khi debug, tạm thời dùng seed cố định để tái hiện lỗi, rồi đổi lại seed theo thời gian trước khi nộp.
  • Sinh số thực rồi ép kiểu. (int)(rnd01() * n) có thể ra đúng n khi sai số làm tròn đẩy giá trị lên 1.0 (hiếm nhưng có). Sinh chỉ số bằng uniform_int_distribution<int>(0, n - 1).

Biến thể / Mở rộng

  • Đếm cặp/đoạn bằng nhau sau khi băm. Sau xor/sum hashing, nhiều bài thành "đếm số cặp L<R có PL=PR" (trong cả mảng: dùng map đếm tần số; trong đoạn truy vấn: dùng thuật toán Mo hoặc xử lý offline).
  • Băm cây và băm đồ thị. Băm cây con để kiểm tra đẳng cấu cây có gốc: hash của một nút là hàm (ngẫu nhiên hóa) của đa tập hash các con, ví dụ h(v)=∏c(rd+h(c))modM với rd ngẫu nhiên theo độ sâu.
  • Kiểm tra đồng nhất đa thức (Schwartz-Zippel). Tổng quát của Freivalds: đa thức khác 0 bậc d trên trường kích thước M bằng 0 tại điểm ngẫu nhiên với xác suất ≤dM. Đây là nền tảng của hash đa thức và của nhiều thuật toán đại số (định thức ngẫu nhiên để kiểm tra đồ thị có ghép cặp hoàn hảo).
  • Color coding. Tô màu ngẫu nhiên các đỉnh bằng k màu rồi tìm đường đi k đỉnh có màu khác nhau bằng QHĐ bitmask; một đường cố định được tô "đẹp" với xác suất k!kk≥e−k, lặp O(ek) lần.
  • Quickselect ngẫu nhiên. Tìm phần tử nhỏ thứ k trong O(n) kỳ vọng (nth_element của C++ dùng ý tưởng này kèm cơ chế dự phòng).

Bài tập luyện

  • Gen bò (Gold) (cownomicsg) (Nâng cao) Tìm đoạn vị trí ngắn nhất phân biệt hai đàn bò; băm đoạn gen mỗi con bằng hash đa thức với cơ số ngẫu nhiên rồi kiểm tra hai tập hash rời nhau, kết hợp tìm kiếm nhị phân hoặc hai con trỏ theo độ dài.
  • Tính tương thích bò (cowcompat) (Kỳ cựu) Đếm cặp bò không chung vị kem bằng bao hàm loại trừ trên 31 tập con khác rỗng của mỗi bò; cần bảng băm với hàng triệu khóa, nơi hàm băm chống hack quyết định có qua thời gian hay không.
  • Cặp song trùng (doubprof) (Chuyên gia) Đếm cặp đỉnh có cùng tập kề (không tính nhau) với n,m≤106; gán mỗi đỉnh một số 64 bit ngẫu nhiên, tổng trọng số hàng xóm biến bài thành đếm giá trị bằng nhau (xét riêng tập kề đóng cho cặp kề nhau).
  • Vùng đất bỏ hoang (antiquity) (Chuyên gia) Thêm/gỡ hàng rào hình chữ nhật và hỏi hai ô có đi tới nhau được không; gán trọng số ngẫu nhiên cho mỗi hàng rào, cộng lên hình chữ nhật bằng Fenwick 2D, hai ô liên thông khi tổng bằng nhau.
  • Tia laser trong thực tại song song (laserray) (Chuyên gia) Chiếu các điểm lên mặt phẳng vuông góc với tia rồi tìm đường tròn bao nhỏ nhất của hình chiếu cho mỗi màn chơi; cần thuật toán Welzl trộn ngẫu nhiên O(n) kỳ vọng.
  • Bài đăng (voi26_post) (Chuyên gia) Đếm đoạn "toàn vẹn" trong đoạn truy vấn; xor hashing với trọng số các lần xuất hiện của mỗi chủ đề có xor bằng 0 biến điều kiện thành PL−1=PR, phần còn lại là bài đếm cặp bằng nhau trên đoạn bằng cấu trúc dữ liệu.
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