A* heuristic và Prim cây khung nhỏ nhất
Thuật toán A* với hàm heuristic chấp nhận được, so sánh với Dijkstra, và thuật toán Prim tìm cây khung nhỏ nhất bằng tính chất lát cắt.
Trung bìnhThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học A* đi thẳng tới đích nhờ heuristic. Bài cũng học Prim nối mọi đỉnh rẻ nhất.
Kiến thức cần nhớ
A* thêm la bàn
- Dijkstra lan đều mọi hướng nên lãng phí khi biết đích.
- A* ưu tiên theo f = g + h, g là đã đi, h là đoán còn lại.
- h bằng 0 thì thành Dijkstra, g bằng 0 thì thành tham lam.
- Ví dụ đời thường: đi giao hàng nhìn biển chỉ đường thay vì đi vòng.
Heuristic tốt
- Chấp nhận được: không bao giờ đoán vượt quá thật.
- Nhất quán: đoán ở đây không vượt cạnh sang cộng đoán bên kia.
- Ví dụ đời thường: đường chim bay luôn ngắn hơn đường bộ quanh co.
- Đoán vượt quá thì nhanh nhưng đường ra không tối ưu.
Prim nuôi một cây
- Bắt đầu từ một đỉnh, mỗi bước kết nạp đỉnh rẻ nhất.
- Dùng heap lưu chi phí nối rẻ nhất từ cây ra ngoài.
- Dựa trên lát cắt: cạnh nhẹ nhất qua cắt thuộc MST.
- Ví dụ đời thường: kéo điện nối mọi nhà bằng ít dây nhất.
| Thuật toán | Mục tiêu | Cấu trúc |
|---|---|---|
| Dijkstra | Đường rẻ từ nguồn | Heap theo khoảng cách |
| A* | Đường rẻ tới đích | Heap theo g + h |
| Prim | Cây nối mọi đỉnh | Heap theo cạnh nối |
Ví dụ
- Input: A-B 2, B-C 3, A-C 10, đích C -> Output: đường A-B-C tổng 5.
- Câu này cho thấy A* không bị dụ bởi cạnh tắt đắt.
- Input: hình vuông cạnh 1, chéo 3 -> Output: MST tổng 3 gồm 3 cạnh vuông.
- Câu này cho thấy Prim bỏ chéo đắt để lấy cạnh rẻ.
💻 Bài tập
Ngôn ngữ: C++. Nộp vào day-043/.
Bài 1: A* trên lưới
Lưới R x C, # là tường. Đi 4 hướng, mỗi bước chi phí 1.
| Hàm | Yêu cầu |
|---|---|
int astar(const Grid&, Pos s, Pos t, Heuristic h, int &expanded) | Trả độ dài ngắn nhất, không có đường trả -1. expanded đếm số ô lấy ra khỏi heap |
int manhattan(Pos a, Pos b) | |
int zero(Pos, Pos) | Luôn 0, biến A* thành Dijkstra |
int overestimate(Pos a, Pos b) | 3 * manhattan, không chấp nhận được |
Lưới 50x50 trống, S=(0,0), E=(49,49):
h = zero -> 98, expanded ~ 2500
h = manhattan -> 98, expanded ít hơn nhiều
h = overestimate-> có thể > 98 khi có tường chắn: dựng 1 lưới chứng minh
Bài 2: Prim với heap
std::pair<long long, std::vector<std::pair<int,int>>> prim(const WGraph &g); // vô hướng
Hình vuông 0-1(1), 1-2(1), 2-3(1), 3-0(1), chéo 0-2(3), 1-3(3) -> tổng 3
A-B 2, B-C 3, A-C 10 -> tổng 5
Kiểm tra: tổng trọng số Prim bằng Kruskal (ngày 33) trên 100 đồ thị liên thông ngẫu nhiên.
Bài 3: Tìm đường trên bản đồ có tọa độ (nâng cao)
- Sinh 5000 điểm ngẫu nhiên trên mặt phẳng. Nối mỗi điểm với 6 điểm gần nhất, trọng số là khoảng cách Euclid.
- Chạy Dijkstra và A* (heuristic Euclid) cho 100 cặp ngẫu nhiên. In độ dài trung bình và số đỉnh mở rộng trung bình của mỗi thuật toán. Độ dài phải bằng nhau.
- Viết 3 câu: vì sao heuristic Euclid chấp nhận được trong bài này.
✅ Tiêu chí hoàn thành
- A* với
manhattanluôn cho cùng độ dài vớizero. - Có lưới chứng minh heuristic đoán vượt cho đường không tối ưu.
- Prim khớp Kruskal trên 100 đồ thị.
- Bảng số đỉnh mở rộng Bài 3 có số thật.
❓ Câu hỏi ôn tập
- Công thức f trong A* gồm gì?
- Heuristic chấp nhận được nghĩa là gì?
- Prim mỗi bước chọn cạnh nào?
- Khi nào A* thành Dijkstra?
🌕 Bạn đã hoàn thành ngày 43. Làm hết bài tập phía trên rồi sang ngày tiếp theo.