Search: nối các ý tưởng lại với nhau

Sau khi học từng thuật toán riêng lẻ, phần dễ quên nhất lại là câu hỏi quan trọng nhất:

Khi gặp một bài toán mới, làm sao biết mình đang giải loại search nào và nên bắt đầu từ đâu?

Note này nối toàn bộ phần Search thành một bức tranh chung, kèm một số bài nhỏ để tự kiểm tra. Không cần làm như bài tập bắt buộc; hãy dùng nó để phát hiện chỗ mình “tưởng hiểu nhưng chưa giải thích được”.

Bản đồ Search

Nếu chỉ nhớ một sơ đồ của cả tuần, hãy nhớ sơ đồ này.

Bước 1 - Mô hình hóa đúng trước khi chọn thuật toán

Cho mê cung:

S . # . .
. . # . #
# . . . .
. # # . G

Một mô hình hợp lý:

state        = (row, col)
initial      = tọa độ S
actions      = UP/DOWN/LEFT/RIGHT nếu hợp lệ
result       = tọa độ sau khi di chuyển
goal test    = state == G
path cost    = số bước, nếu mỗi bước cost 1

Nếu state không đủ thông tin, thuật toán tốt đến đâu cũng không cứu được model sai.

Câu hỏi

Nếu robot còn có hướng đang quay mặt và chỉ được FORWARD, TURN_LEFT, TURN_RIGHT, state (row, col) đã đủ chưa?

Gợi ý: chưa. Hai robot ở cùng ô nhưng quay hai hướng khác nhau có tập action/result khác nhau. State nên chứa cả hướng.

state = (row, col, direction)

Đây là ví dụ quan trọng về câu “state phải chứa đủ thông tin để quyết định tương lai”.

Bước 2 - Frontier quyết định hành vi search

Cùng graph:

DFS

Frontier là Stack.

Một traversal có thể đi:

A -> C -> F -> G

nếu C được pop trước B.

BFS

Frontier là Queue.

BFS đi theo lớp:

A
B, C
D, E, F
G

Greedy

Frontier là Priority Queue với priority:

h(n)

A*

Priority:

f(n)=g(n)+h(n)

Nói cách khác, các thuật toán search có thể chia sẻ rất nhiều code; khác biệt lớn nằm ở policy chọn node tiếp theo và cách cập nhật cost.

Bước 3 - Chọn thuật toán theo thông tin bài toán

Case A: mê cung không trọng số, cần ít bước nhất

Khởi đầu hợp lý: BFS.

Lý do: mỗi bước cost 1, BFS đi theo depth nên goal đầu tiên cho số bước nhỏ nhất.

Case B: mê cung rất lớn, biết tọa độ goal

Có thể thử A* với Manhattan distance.

Lý do: heuristic giúp hướng search về phía goal thay vì mở rộng đồng đều mọi hướng.

Case C: chỉ cần biết có đường hay không, không cần shortest path

DFS có thể đủ đơn giản.

Case D: có đối thủ chọn hành động ngược mục tiêu của ta

Path-finding search không đủ. Cần nghĩ theo Adversarial Search / Minimax.

Case E: graph có edge cost khác nhau, không có heuristic

BFS không đảm bảo minimum cost. Một thuật toán tự nhiên là Uniform-Cost Search. CS50 Week 0 tập trung DFS/BFS/Greedy/A*, nhưng về mặt tư duy, hãy nhớ g(n) mới là thứ phải tối ưu khi cost khác nhau.

Bài nhỏ 1 - DFS hay BFS?

Graph:

DFS đi nhánh A trước có thể trả đường nào?
BFS trả đường nào nếu mọi cạnh cost 1?
Tại sao hai thuật toán đều “đúng” về việc tìm được Goal nhưng chất lượng solution khác nhau?

Đáp án ngắn: DFS có thể trả S-A-B-C-G; BFS tìm S-X-G vì đây là đường ít cạnh hơn.

Bài nhỏ 2 - BFS có còn tối ưu?

đường 2 cạnh có cost 100;
đường 3 cạnh có cost 3.

BFS tối ưu theo depth, không theo tổng edge weight. Đây là lý do phải luôn hỏi “path cost được định nghĩa là gì?”.

Bài nhỏ 3 - Greedy và A*

Cho frontier:

Node	$g(n)$	$h(n)$
A	2	9
B	4	4
C	20	1
D	3	5

Greedy

Chỉ nhìn h, nên chọn C.

A*

Tính:

A: 2 + 9  = 11
B: 4 + 4  = 8
C: 20 + 1 = 21
D: 3 + 5  = 8

A* chọn B hoặc D tùy tie-breaking.

Điểm cần hiểu: node gần goal theo heuristic chưa chắc là đường tổng thể tốt.

Bài nhỏ 4 - Heuristic admissible hay không?

State	Chi phí thật còn lại	$h(n)$
A	8	6
B	5	5
C	3	4

Tại C:

h(C)=4>3

Heuristic đã overestimate, nên không admissible.

Bài nhỏ 5 - Minimax tính tay

MIN values:

A = min(3,7) = 3
B = min(4,2) = 2
C = min(5,1) = 1

MAX chọn:

\max(3,2,1)=3

=> chọn A.

Bài nhỏ 6 - Khi nào prune?

MAX đã có một nhánh giá trị 5.

Ở nhánh tiếp theo là MIN, child đầu tiên đã có giá trị 3.

MIN có thể giữ 3 hoặc tìm số còn thấp hơn. Nhánh này không thể vượt 5 từ góc nhìn MAX.

=> các child còn lại có thể prune.

Đây là Alpha-Beta bằng trực giác trước khi nhớ alpha >= beta.

Một implementation map đơn giản

Nếu muốn tự code lại Search từ đầu, có thể đi theo thứ tự:

Đừng bắt đầu bằng một class framework lớn. Với người mới học code, cài phiên bản nhỏ chạy được trên graph 7–10 node giúp hiểu thuật toán nhanh hơn nhiều.

Mẫu graph Python để tự thử

graph = {
    "A": [("B", 1), ("C", 1)],
    "B": [("D", 1), ("E", 1)],
    "C": [("F", 1)],
    "D": [],
    "E": [("G", 1)],
    "F": [("G", 1)],
    "G": [],
}

Từ đây bạn có thể:

bỏ cost để viết DFS/BFS;
giữ cost để viết A*;
tự đặt heuristic dictionary;
in frontier ở mỗi vòng để quan sát thuật toán.

Ví dụ debug hữu ích:

print("current:", state)
print("frontier:", frontier)

Search dễ hiểu hơn rất nhiều khi nhìn được frontier thay đổi.

“Tôi cần nhớ công thức nào?”

Không nhiều.

Path cost đã đi

g(n)=\text{cost}(\mathrm{Start}, n)

Heuristic

h(n)\approx \text{cost}(n, \mathrm{Goal})

A*

f(n)=g(n)+h(n)

Consistency của heuristic

h(n)\le c(n,n')+h(n')

Minimax

Không cần thuộc ký hiệu dài trước. Chỉ cần nhớ:

MAX -> chọn lớn nhất
MIN -> chọn nhỏ nhất
terminal -> utility

“Tôi cần nhớ code nào?”

Cũng không nên học thuộc code. Cần hiểu pattern:

frontier
while frontier:
    lấy node
    goal test
    expand
    thêm node mới

Rồi nhớ cấu trúc dữ liệu:

DFS    -> stack
BFS    -> queue
Greedy -> priority h
A*     -> priority g+h

Nếu hiểu những điều này, bạn có thể viết lại code với vài lần tra cú pháp Python.

Checklist hiểu bài

Sau phần Search, bạn nên tự giải thích được các câu sau mà không cần đọc định nghĩa:

Nếu chưa giải thích được một mục, quay lại đúng section đó. Không cần đọc lại cả tuần.

Từ Search sang Knowledge

Search trả lời:

“Trong các hành động có thể làm, ta nên đi theo chuỗi nào?”

Nhưng nhiều bài toán còn đòi hỏi máy biết các mệnh đề về thế giới và suy luận từ chúng.

Ví dụ:

Nếu A đúng thì B đúng.
A đang đúng.
Ta có thể kết luận gì?

Đó là chủ đề tiếp theo: Knowledge.

Bản tiếng Anh đang soạn.