1. Ý tưởng cốt lõi
Hill Climbing (Leo đồi) là thuật toán tìm kiếm cục bộ: tại mỗi bước, nó chỉ nhìn vào các nút kề ngay lập tức và chuyển sang nút có h(n) thấp nhất — không lưu lịch sử, không quay lui.
Hình ảnh trực quan
Hãy tưởng tượng bạn đứng trên một bề mặt đồi núi trong sương mù. Bạn không nhìn thấy toàn cảnh — chỉ biết độ dốc ngay dưới chân. Bạn luôn bước xuống chỗ thấp hơn, cho đến khi không còn chỗ nào thấp hơn xung quanh. Đó là cực tiểu cục bộ — dù toàn cục có thể còn thấp hơn nữa.
2. Quy tắc thực hiện (6 bước)
- Bắt đầu tại nút khởi đầu. Đây là nút hiện tại.
- Sinh tất cả nút kề (các nút có thể đến từ nút hiện tại).
- Chọn nút kề có h(n) nhỏ nhất. Nếu hòa → chọn theo thứ tự bảng chữ cái.
- Nếu h(nút kề tốt nhất) < h(nút hiện tại) → di chuyển đến đó.
- Nếu không có nút kề nào cải thiện (h ≥ h hiện tại) → dừng (cực tiểu cục bộ).
- Lặp lại từ bước 2 cho đến khi đến đích hoặc dừng.
3. Tính chất
| Tính chất | Hill Climbing |
|---|---|
| Dùng h(n)? | ✓ Có |
| Theo dõi g(n) (chi phí đường đi)? | ✗ Không |
| Có danh sách OPEN? | ✗ Không |
| Có thể quay lui? | ✗ Không |
| Đảm bảo tìm được đích? | ✗ Không |
| Đảm bảo tối ưu? | ✗ Không |
| Độ phức tạp bộ nhớ | O(1) — chỉ lưu nút hiện tại |
Kết luận: Hill Climbing nhanh và tiết kiệm bộ nhớ, nhưng không đầy đủ và không tối ưu. Nó có thể bị kẹt tại cực tiểu cục bộ — nút có h nhỏ hơn tất cả các nút kề, nhưng chưa phải đích.
4. Đồ thị minh họa
Đồ thị có hướng 6 nút dưới đây. Số trong khung vàng là giá trị heuristic
h(n) — ước lượng khoảng cách còn lại đến đích T. Số trên cạnh là chi phí di chuyển.
5. Giải Hill Climbing — phương pháp kẻ bảng
Mỗi hàng là một bước. Cột Quyết định giải thích vì sao chọn hoặc dừng.
| Bước | Nút hiện tại | h(hiện tại) | Nút kề | h(kề) | Quyết định |
|---|---|---|---|---|---|
| 1 | S | 9 | A, B | 5, 7 | h(A)=5 < 9 → chọn A |
| 2 | A | 5 | C, D | 3, 4 | h(C)=3 < 5 → chọn C |
| 3 | C | 3 | D | 4 | h(D)=4 > 3 → DỪNG ⚑ |
Kết quả
Hill Climbing bị kẹt tại C (cực tiểu cục bộ). Không tìm được đường đến T.
Tại sao C là cực tiểu cục bộ? C chỉ có một nút kề là D với h(D)=4. Vì 4 > 3 = h(C), Hill Climbing không thể tiến thêm. Dù có thể đến T qua C→D→T, thuật toán không biết điều này — nó không nhìn xa hơn một bước và không có bộ nhớ nào lưu lại nhánh B đã bỏ qua ở bước 1.
6. So sánh: Greedy Best-First trên cùng đồ thị
Greedy Best-First cũng dùng h(n), nhưng duy trì danh sách OPEN và xét toàn bộ nút đã thấy — không bao giờ "quên" một nhánh.
| Bước | OPEN (nút, h) | Mở rộng | Thêm vào OPEN | Ghi chú |
|---|---|---|---|---|
| 0 | {(S,9)} | S | A(5), B(7) | Bắt đầu |
| 1 | {(A,5),(B,7)} | A | C(3), D(4) | h(A)=5 nhỏ nhất |
| 2 | {(C,3),(D,4),(B,7)} | C | D(4)* | h(C)=3 nhỏ nhất |
| 3 | {(D,4),(B,7)} | D | T(0) | D đã trong OPEN; chỉ thêm T |
| 4 | {(T,0),(B,7)} | T | — | h(T)=0 → ĐẾN ĐÍCH ✓ |
*D đã có trong OPEN với h=4; không thêm lại.
Đường đi Greedy: S → A → C → D → T
Chi phí: g = 2 + 1 + 3 + 6 = 12
| Tiêu chí | Hill Climbing | Greedy Best-First |
|---|---|---|
| Danh sách OPEN | ✗ | ✓ |
| Quay lui / thử lại | ✗ | ✓ (qua OPEN) |
| Bộ nhớ | O(1) | O(b·d) |
| Tìm được đích? | ✗ (kẹt tại C) | ✓ |
| Chi phí đường đi | — | 12 (không tối ưu) |
| Tối ưu? | ✗ | ✗ |
7. HC thuần túy vs HC hiện đại (slide)
Tên "Hill Climbing" được dùng theo hai nghĩa khác nhau trong tài liệu AI. Phân biệt rõ để không nhầm lẫn giữa slide tuần 3 và bài lab tuần 4.
HC thuần túy AIMA
Tìm kiếm cục bộ. Chỉ lưu nút hiện tại. Di chuyển đến nút kề tốt hơn hoặc dừng. Không có OPEN list. Đây là định nghĩa trong Artificial Intelligence: A Modern Approach (Russell & Norvig, chương 4).
HC hiện đại Slide
DFS có hướng dẫn bởi heuristic. Giữ một danh sách OPEN,
sắp xếp nút con theo h, đẩy vào đầu OPEN.
Đây là thủ tục trong slides/2.Searching_2.pdf
và cách Winston / MIT 6.034 dạy ("HC có backup").
| Tính chất | HC thuần túy (AIMA) | HC hiện đại (slide) |
|---|---|---|
| Dùng h(n)? | Có | Có |
| Có OPEN / fringe? | Không — chỉ lưu nút hiện tại | Có — ngăn xếp sắp xếp theo h |
| Xử lý nút con | Chỉ giữ nút kề tốt nhất (cải thiện h) | Sắp xếp toàn bộ theo h, đẩy vào đầu OPEN |
| Có thể quay lui? | Không | Có (qua các mục còn lại trong OPEN) |
| Trên đồ thị ví dụ | Kẹt tại C — bỏ lỡ T | Có thể tìm T qua OPEN |
| Bộ nhớ | O(1) | Như DFS — tỷ lệ với độ sâu × nhánh |
| Đảm bảo tìm đích? | Không — kẹt tại cực tiểu cục bộ | Không — rủi ro như DFS, nhưng không mất bộ nhớ |
| Tên sách giáo khoa | AIMA "hill-climbing search" | Winston HC; Poole gọi là heuristic depth-first search |
Lưu ý đặt tên
AIMA giữ tên "hill climbing" cho dạng cục bộ thuần túy. Poole & Mackworth gọi dạng OPEN-list là heuristic depth-first search. Cả hai tên đều có cơ sở trong tài liệu. Điều quan trọng khi làm bài là xác định quy tắc nào được yêu cầu áp dụng.
8. Điểm mấu chốt cần nhớ
- Hill Climbing không có bộ nhớ — khi đến C, nó đã "quên" S và A. Không có cách nào quay lại nhánh B.
- Cực tiểu cục bộ ≠ cực tiểu toàn cục — h(C)=3 nhỏ hơn mọi nút kề, nhưng T (h=0) mới là đích thực sự.
- Greedy thoát được vì OPEN list đã lưu D từ bước 2 — khi C mở rộng ra D, D đã sẵn sàng trong hàng đợi.
- Cả hai không tối ưu — chúng không theo dõi g(n), chỉ dùng h(n). Muốn tối ưu cần A*.
- HC thuần túy (tuần 4) ≠ HC hiện đại (slide tuần 3): dạng slide là DFS hướng dẫn bởi h và có OPEN list, không phải local search.
9. Bẫy thường gặp khi làm bài
| Lỗi sai | Đúng |
|---|---|
| HC tiếp tục dù h(kề) = h(hiện tại) | HC dừng khi không có kề nào tốt hơn nghiêm ngặt (h < h hiện tại) |
| Greedy không thêm D vào OPEN vì "đã thấy" | Greedy thêm vào OPEN khi chưa có; nếu đã có thì giữ, không thêm lại |
| Tính chi phí Greedy theo số bước | Chi phí = tổng trọng số cạnh, không phải số bước |
| Nhầm h(n) với g(n) | h(n) = ước lượng còn lại đến đích; g(n) = chi phí đã đi từ đầu |
| Dùng quy tắc HC "hiện đại" (OPEN list) khi bài yêu cầu HC thuần túy | Đọc kỹ đề — nếu yêu cầu "local search" hoặc "không có OPEN" thì dùng HC thuần túy |
Tài liệu tham khảo
- Russell, S. & Norvig, P. — Artificial Intelligence: A Modern Approach. Hill-climbing search là tìm kiếm cục bộ không có fringe (chương 4).
- Winston, P. — MIT 6.034. Hill climbing là DFS với nút con sắp xếp theo heuristic và đẩy vào đầu hàng đợi.
- Poole, D. & Mackworth, A. — Artificial Intelligence: Foundations of Computational Agents. Dạng OPEN-list được gọi là heuristic depth-first search.
-
Slide môn học:
slides/2.Searching_2.pdf— Hill climbing dạng hiện đại (OPEN-list).