Ứng dụng NN - nearest hub, giảm màu ảnh, hạt vật lý
Bốn ứng dụng tìm kiếm lân cận: trạm trung chuyển gần nhất, bài toán tập trung và phân tán, giảm màu ảnh, tương tác hạt và tối ưu truy vấn đa chiều.
Trung bìnhThuật toán ~45 phút
Ôn lại trước khi học
Giới thiệu
Bài này học 4 ứng dụng tìm điểm gần nhất. Ứng dụng này phủ từ giao hàng tới ảnh và vật lý.
Kiến thức cần nhớ
Trạm gần nhất tập trung
- Mỗi đơn hàng cần trạm gần nhất để giảm phí ship.
- Cách tập trung: một máy giữ hết trạm bằng k-d tree.
- Truy vấn , đơn giản dễ bảo trì.
- Ví dụ đời thường: một tổng đài điều hết xe trong thành phố.
Phân tán và 3 rắc rối
- Chia bản đồ thành vùng, mỗi máy giữ một vùng.
- Tốn độ trễ mạng HTTP khi hỏi nhiều máy.
- Khó giữ đồng bộ khi trạm đóng mở liên tục.
- Ví dụ đời thường: nhiều chi nhánh thì khó biết chỗ nào còn hàng.
Giảm màu ảnh và hạt vật lý
- Mỗi pixel tìm màu gần nhất trong bảng màu nhỏ.
- Tập nhỏ thì duyệt hết, khỏi cần cây phức tạp.
- Hạt vật lý: mỗi hạt chỉ tương tác trong bán kính.
- Ví dụ đời thường: pha sơn gần nhất với mẫu, bầy cá chỉ nhìn bạn gần.
| Ứng dụng | Cấu trúc hợp | Lý do |
|---|---|---|
| Trạm tĩnh ít chiều | k-d tree | Cân bằng, nhanh |
| Bản đồ động 2D | R-tree | Tách gộp cục bộ |
| Bảng màu nhỏ | Duyệt hết | Vài trăm màu khỏi cây |
| Tải cao phân tán | Chia vùng | Hết nghẽn một máy |
Ví dụ
- Input: đơn trùng vị trí trạm A -> Output: gán đúng A, khoảng cách 0.
- Câu này kiểm tra biên trùng vị trí xử lý đúng.
- Input: bán kính tương tác bằng 0 -> Output: không cặp hạt nào tương tác.
- Câu này kiểm tra truy vấn vùng ở biên dưới.
💻 Bài tập
Ngôn ngữ: C++ (hoặc Python cho phần ảnh). Dùng KDTree ngày 45 và thêm hàm nearest đơn giản (có thể dùng bản của ngày 69 sau này, hôm nay viết bản cơ bản có cắt nhánh). Nộp vào day-046/.
Bài 1: Gán đơn hàng cho trạm gần nhất
| Hàm | Yêu cầu |
|---|---|
int nearestBrute(const std::vector<Point> &hubs, Point q) | Quét hết, |
int nearestKD(const KDTree<2> &t, Point q) | Đi xuống lá rồi quay lui, chỉ thăm nhánh bên kia khi khoảng cách tới mặt chia nhỏ hơn đáp án hiện tại |
hubs = (0,0) (10,0) (0,10); q=(1,1) -> hub 0; q=(9,2) -> hub 1
q trùng hub -> khoảng cách 0
Sinh 10.000 trạm và 100.000 đơn ngẫu nhiên. Kiểm tra 2 hàm cho cùng đáp án. In thời gian.
Bài 2: Giảm màu ảnh
Đọc ảnh PPM (P3 hoặc P6), tự viết bộ đọc. Bảng màu 16 màu cố định (ví dụ bảng màu CGA).
- Mỗi pixel đổi thành màu gần nhất trong bảng (khoảng cách Euclid trong RGB). Ghi ra ảnh mới.
- So thời gian giữa quét 16 màu và k-d tree 16 màu. Giải thích vì sao tập nhỏ thì quét nhanh hơn.
Bài 3: Hạt tương tác trong bán kính (nâng cao)
Mô phỏng 5000 hạt ngẫu nhiên trong hộp . Với bán kính r = 0.01:
- Đếm số cặp hạt cách nhau dưới
rbằng 2 cách: quét mọi cặp và truy vấn vùng k-d tree. - Cách thứ 3: chia lưới ô cỡ
r, chỉ xét 9 ô lân cận. - In số cặp (3 cách phải bằng nhau) và thời gian.
r = 0 -> 0 cặp
✅ Tiêu chí hoàn thành
-
nearestKDkhớpnearestBrutetrên 100.000 truy vấn. - Ảnh giảm màu xuất ra đúng, có ảnh trước và sau trong repo.
- Bài 3: 3 cách cho cùng số cặp, có bảng thời gian.
- Viết được khi nào nên dùng cây, khi nào quét thẳng là đủ.
❓ Câu hỏi ôn tập
- Cách tập trung tìm trạm gần nhất thế nào?
- Phân tán gặp 3 khó khăn nào?
- Giảm màu ảnh là tìm gì gần nhất?
- Khi nào nên duyệt hết thay vì dùng cây?
🌕 Bạn đã hoàn thành ngày 46. Làm hết bài tập phía trên rồi sang ngày tiếp theo.