Informed Search: Greedy Best-First và A*

DFS và BFS chỉ nhìn những gì đã khám phá. Nhưng con người giải mê cung thường không hoàn toàn “mù”: nếu goal nằm phía đông, ta có xu hướng ưu tiên những ô đi về phía đông.

Informed Search đưa thêm kiến thức kiểu đó vào quá trình tìm kiếm.

Từ khóa trung tâm là heuristic.

Heuristic: một “ước lượng có lý”

Giả sử bạn đang ở Hà Nội và cần tới một địa điểm ở Hải Phòng. Nếu có hai tuyến, một tuyến đang dẫn về phía Sơn Tây còn một tuyến hướng đông, bạn có thể đoán tuyến hướng đông hứa hẹn hơn dù chưa tính toàn bộ hành trình.

Heuristic làm việc tương tự:

$h(n)$ là một hàm ước lượng chi phí còn lại từ node n tới goal.

Nó không cần chính xác tuyệt đối. Nó là thông tin giúp search ưu tiên node nào có vẻ tốt hơn.

Manhattan Distance

Trên grid chỉ cho đi lên, xuống, trái, phải, một heuristic phổ biến là Manhattan distance.

Nếu đang ở:

(x1, y1)

và goal là:

(x2, y2)

thì:

Đọc công thức:

1. lấy chênh lệch số hàng;
2. lấy chênh lệch số cột;
3. cộng lại.

Ví dụ từ (1, 2) tới (4, 6):

Ta ước lượng cần ít nhất khoảng 7 bước nếu bỏ qua tường.

Chú ý: heuristic bỏ qua một số chi tiết. Nếu có tường lớn chắn giữa, đường thật có thể dài hơn 7.

Greedy Best-First Search

Trực giác

Greedy Best-First Search luôn hỏi:

Trong frontier, node nào có vẻ gần goal nhất ngay lúc này?

Nó chọn node có h(n) nhỏ nhất.

priority = h(n)

Ví dụ frontier:

Greedy chọn B.

Mermaid intuition

Greedy ưu tiên B vì 3 nhỏ nhất.

Greedy dùng Priority Queue

Stack và Queue ưu tiên theo thứ tự vào. Greedy cần ưu tiên theo một con số.

Ta dùng priority queue.

Python có heapq:

import heapq

frontier = []
heapq.heappush(frontier, (8, "A"))
heapq.heappush(frontier, (3, "B"))
heapq.heappush(frontier, (5, "C"))

priority, state = heapq.heappop(frontier)
print(state)  # B

Greedy có vấn đề gì?

Nó chỉ nhìn phần còn lại, không nhìn phần đã đi.

Giả sử:

Greedy chọn A vì:

Nhưng ta đã mất cost 100 để tới A. Đây có thể là quyết định rất tệ.

Greedy giống người chỉ nhìn biển “còn 1 km tới đích” nhưng quên rằng mình vừa đi vòng 100 km để tới đó.

A*: nhìn cả đường đã đi lẫn đường còn lại

A* sửa điểm yếu trên bằng cách kết hợp hai đại lượng:

$g(n)$ - chi phí đã đi

Đây là chi phí thật từ Start tới node n.

$h(n)$ - chi phí ước lượng còn lại

Đây là heuristic từ n tới Goal.

$f(n)$ - tổng đánh giá

Đọc bằng lời:

ước lượng tổng chi phí của một lời giải đi qua node này = chi phí đã trả + chi phí dự đoán còn lại.

A* chọn node có f(n) nhỏ nhất.

Ví dụ A* từng bước

Frontier có:

• Greedy chọn A vì h=2 nhỏ nhất.
• A* chọn C vì f=7 nhỏ nhất.

A* đang nói:

“A có vẻ gần goal, nhưng đường tới A đã khá tốn. C cân bằng hơn.”

Greedy và A* nhìn cùng một node khác nhau thế nào?

Code Greedy tối giản

Graph có (neighbor, step_cost):

graph = {
    "S": [("A", 2), ("B", 4)],
    "A": [("G", 8)],
    "B": [("G", 3)],
    "G": [],
}

h = {
    "S": 5,
    "A": 1,
    "B": 3,
    "G": 0,
}

Greedy:

import heapq


def greedy_best_first(graph, start, goal, h):
    frontier = [(h[start], start)]
    parent = {start: None}

    while frontier:
        _, state = heapq.heappop(frontier)

        if state == goal:
            return build_path(parent, goal)

        for neighbor, _cost in graph[state]:
            if neighbor not in parent:
                parent[neighbor] = state
                heapq.heappush(frontier, (h[neighbor], neighbor))

    return None

Biến _cost không được dùng. Đó chính là điểm quan trọng: Greedy không quan tâm chi phí đã đi.

Code A* phiên bản dễ học

import heapq


def a_star(graph, start, goal, h):
    frontier = [(h[start], start)]

    came_from = {start: None}
    g_cost = {start: 0}

    while frontier:
        _, state = heapq.heappop(frontier)

        if state == goal:
            return build_path(came_from, goal)

        for neighbor, step_cost in graph[state]:
            new_g = g_cost[state] + step_cost

            # Lần đầu thấy neighbor, hoặc tìm được đường rẻ hơn tới neighbor
            if neighbor not in g_cost or new_g < g_cost[neighbor]:
                g_cost[neighbor] = new_g
                came_from[neighbor] = state

                f = new_g + h[neighbor]
                heapq.heappush(frontier, (f, neighbor))

    return None

Điểm quan trọng nhất nằm ở:

new_g = g_cost[state] + step_cost
f = new_g + h[neighbor]

Và A* cho phép cập nhật nếu tìm được đường rẻ hơn tới cùng một state.

Heuristic tốt là heuristic như thế nào?

Heuristic ảnh hưởng rất mạnh đến số node phải khám phá.

Nếu $h(n)=0$ với mọi node

A* chỉ còn:

Nó không còn định hướng về Goal. Về ý tưởng, nó hành xử như Uniform-Cost Search.

Nếu heuristic gần chi phí thật

A* có thể hướng search rất tốt và giảm số node không cần thiết.

Nếu heuristic “quá tự tin” và sai

A* có thể mất đảm bảo tối ưu tùy điều kiện và cách triển khai.

CS50 nhấn mạnh hai tính chất cho heuristic của A*: admissible và consistent.

Admissible - không được đoán quá lớn

Heuristic admissible nếu nó không bao giờ ước lượng chi phí còn lại lớn hơn chi phí tối ưu thật sự.

Viết:

Trong đó $h^*(n)$ là chi phí thật tối ưu từ n tới Goal.

Không cần nhớ ký hiệu ngay. Hãy nhớ:

Admissible = được phép lạc quan, không được bi quan quá mức.

Ví dụ chi phí thật còn 5:

• h=3: được;
• h=5: được;
• h=8: overestimate, không admissible.

Manhattan distance trên grid 4 hướng thường admissible khi mỗi bước cost 1 vì bỏ qua tường chỉ làm đường ước lượng ngắn hơn hoặc bằng đường thật.

Consistent - ước lượng phải “mượt” giữa hai state kề nhau

Với node n, successor n', và chi phí bước c:

Hiểu bằng lời:

Ước lượng từ n tới Goal không nên lớn hơn “đi một bước sang n' rồi cộng ước lượng từ n'”.

Sơ đồ:

Consistency gần với bất đẳng thức tam giác: đi trực tiếp theo ước lượng không nên “đắt” vô lý so với đi qua neighbor.

Ở mức nhập môn, quan trọng nhất là hiểu heuristic không phải con số tùy ý; nó có những điều kiện ảnh hưởng đến tính đúng/tối ưu của A*.

A* có luôn nhanh nhất không?

Không.

• heuristic xấu có thể khiến A* mở rộng nhiều node;
• priority queue và lưu g tốn thêm chi phí;
• với bài toán nhỏ, BFS có thể đơn giản và đủ tốt;
• một heuristic rất tốt có thể giúp A* vượt trội.

A* nổi tiếng không phải vì “luôn nhanh nhất”, mà vì nó có cách kết hợp rất có nguyên tắc giữa chi phí thật đã đi và ước lượng còn lại.

Bảng so sánh

Chọn heuristic như thế nào?

Heuristic nên:

1. tính nhanh;
2. có liên quan tới khoảng cách/chi phí thật;
3. nếu cần guarantee của A*, thỏa các điều kiện cần thiết;
4. đủ đơn giản để chi phí tính heuristic không lớn hơn lợi ích của nó.

Ví dụ:

Những lỗi thường gặp

Nhầm $g$ và $h$

• g: đã đi thật bao nhiêu;
• h: đoán còn bao nhiêu.

Nghĩ Greedy là “A* nhưng nhanh hơn”

Không. Hai thuật toán tối ưu theo priority khác nhau và có tính chất khác nhau.

Nghĩ heuristic phải chính xác

Nếu biết chính xác cost còn lại ở mọi state thì bài toán gần như đã được giải. Heuristic chỉ cần là một ước lượng hữu ích.

Nghĩ A* chỉ cần visited boolean

Trong graph có trọng số, có thể tìm được một đường rẻ hơn tới state đã thấy. Vì vậy code A* thường lưu g_cost tốt nhất, không chỉ “đã thấy/chưa thấy”.

Tự kiểm tra

1. h(n) đại diện điều gì?
2. Greedy chọn node dựa trên giá trị nào?
3. A* khác Greedy ở chỗ nào?
4. Nếu g(A)=100, h(A)=1 và g(B)=3, h(B)=5, Greedy chọn ai? A* chọn ai?
5. Vì sao Manhattan distance có thể sai so với đường thật nhưng vẫn hữu ích?
6. “Admissible” nghĩa là gì bằng lời của bạn?
7. Nếu $h(n)=0$ ở mọi node, A* còn ưu tiên dựa trên thông tin gì?

Cho tới đây ta tìm đường trong môi trường “trung lập”. Phần tiếp theo khó hơn một chút: nếu có một đối thủ cũng đang chủ động chọn hành động để làm ta thất bại thì sao?

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