Search Problem: biến một bài toán thành không gian tìm kiếm

Giả sử bạn có một mê cung. Với mắt người, ta có thể nhìn các lối đi và thử từng hướng. Máy tính thì không có khái niệm mơ hồ như “đi về phía có vẻ đúng”. Ta phải mô tả chính xác máy đang ở đâu, được phép làm gì và thế nào là hoàn thành.

Đó là bước đầu tiên của Search: mô hình hóa bài toán.

Ý tưởng trước: Search là khám phá một cây khả năng

Từ một trạng thái, ta có nhiều hành động. Mỗi hành động đưa ta tới trạng thái mới. Từ các trạng thái mới lại có thêm lựa chọn.

Nếu số lựa chọn lớn, ta không thể kiểm tra tùy tiện. Ta cần một search algorithm quyết định trạng thái nào nên khám phá trước.

Nhưng trước khi nói DFS hay BFS, cần thống nhất ngôn ngữ của bài toán.

Một Search Problem gồm những gì?

CS50 AI mô tả search problem bằng các thành phần chính: agent, state, initial state, actions, transition model, state space, goal test và path cost.

Agent

Agent là thực thể thực hiện quyết định.

Trong bài toán mê cung, có thể coi agent là nhân vật đang di chuyển. Trong ứng dụng bản đồ, agent có thể là đại diện của chiếc xe cần chọn đường.

State

State là một mô tả đủ dùng về tình huống hiện tại.

Ví dụ với grid:

S . .
# # .
. . G

Nếu mục tiêu chỉ là đi từ S đến G, state có thể rất đơn giản:

state = (row, col)

Ví dụ (0, 1) nghĩa là đang ở hàng 0, cột 1.

Điểm quan trọng:

State không nhất thiết lưu “mọi thứ trong thế giới”, nhưng phải lưu đủ thông tin để quyết định bước tiếp theo.

Trong Tic-Tac-Toe, chỉ lưu vị trí hiện tại là chưa đủ; state phải chứa cả bàn cờ.

Initial State

Initial State là nơi bắt đầu tìm kiếm, thường ký hiệu là $s_0$.

Ví dụ:

start = (0, 0)

Actions

Actions(s) trả về những hành động hợp lệ tại state s.

Trong grid:

UP, DOWN, LEFT, RIGHT

nhưng không phải lúc nào cả bốn đều hợp lệ. Ta không thể đi xuyên tường hay ra ngoài bản đồ.

Ví dụ:

def actions(state):
    # trả về các hướng đi hợp lệ từ state
    ...

Transition Model

Transition Model trả lời câu hỏi:

Nếu đang ở state s và thực hiện action a, state tiếp theo là gì?

Ta thường viết:

Đọc công thức này rất đơn giản:

• s: đang ở đâu;
• a: làm gì;
• s': sau đó ở đâu.

Ví dụ:

def result(state, action):
    row, col = state

    if action == "RIGHT":
        return (row, col + 1)

State Space

State Space là tập tất cả state có thể đạt tới từ initial state thông qua các action hợp lệ.

Ta có thể hình dung state space như graph:

• node của graph biểu diễn state;
• cạnh biểu diễn action/transition.

Không phải search algorithm “tạo ra thế giới”; nó chỉ khám phá dần state space.

Goal Test

Goal Test kiểm tra state hiện tại có phải mục tiêu không.

Ví dụ:

def goal_test(state, goal):
    return state == goal

Search sẽ tiếp tục cho đến khi gặp một state thỏa goal test hoặc không còn state nào để thử.

Path Cost

Hai đường đều tới đích nhưng chưa chắc tốt như nhau.

Ví dụ:

A -> B -> G       2 bước
A -> C -> D -> G  3 bước

Nếu mỗi bước có cost bằng 1, đường đầu tốt hơn.

Nhưng trên bản đồ thật, mỗi cạnh có thể có chi phí khác nhau:

A -> B: 20 phút
A -> C:  3 phút
C -> D:  3 phút
D -> G:  3 phút

Lúc này đường nhiều cạnh hơn lại nhanh hơn.

Tổng chi phí đường đi thường ký hiệu:

Đừng sợ ký hiệu. Nó chỉ nói rằng:

chi phí của cả đường = cộng chi phí từng bước.

Solution và Optimal Solution

Solution

Một solution là chuỗi hành động đưa initial state tới goal.

RIGHT -> RIGHT -> DOWN -> DOWN

Optimal Solution

Optimal solution là lời giải có path cost nhỏ nhất theo cách ta định nghĩa cost.

Điều này dẫn tới một phân biệt quan trọng:

“ít bước nhất” chỉ đồng nghĩa với “rẻ nhất” khi các bước có cùng chi phí.

Nếu cạnh có trọng số khác nhau, chỉ đếm số cạnh là chưa đủ.

State và Node không phải một thứ

Đây là chỗ rất dễ nhầm.

State

State thuộc về bài toán.

Ví dụ:

(2, 3)

Node

Node thuộc về thuật toán search. Nó bao bọc state và lưu thêm thông tin để biết ta đã tới state này bằng cách nào.

Một phiên bản Python dễ đọc:

from dataclasses import dataclass

@dataclass
class Node:
    state: object
    parent: "Node | None"
    action: object | None
    path_cost: float = 0

Tại sao cần parent?

Giả sử cuối cùng tìm thấy Goal. Nếu mỗi node biết cha của nó, ta có thể đi ngược:

Sau đó đảo lại để lấy đường:

Start -> B -> D -> Goal

Frontier: danh sách “những nơi đã biết nhưng chưa xét”

Đây là ý tưởng quan trọng nhất trước khi học DFS/BFS.

Hãy hình dung ba nhóm state:

1. chưa từng thấy;
2. đã thấy và đang chờ xét;
3. đã xét xong.

Frontier là nhóm số 2.

Search strategy khác nhau chủ yếu ở câu hỏi:

Khi frontier có nhiều node, lấy node nào ra trước?

• DFS: lấy node mới thêm gần nhất;
• BFS: lấy node chờ lâu nhất;
• Greedy: lấy node được ước lượng gần goal nhất;
• A*: cân bằng chi phí đã đi và chi phí ước lượng còn lại.

Explored Set: tránh đi vòng

Xét graph:

Nếu không nhớ state đã xét, thuật toán có thể chạy:

A -> B -> C -> A -> B -> C -> ...

Vì vậy ta thường có explored:

explored = set()

Khi xử lý xong một state:

explored.add(state)

Và không thêm lại các state đã biết.

Trong code thật, còn phải chú ý cả state đang có trong frontier, không chỉ explored, để tránh tạo nhiều bản sao không cần thiết.

Khung Search tổng quát

Trước khi học từng thuật toán, hãy nhớ skeleton này:

1. Đưa initial state vào frontier.
2. Lặp:
   a. Nếu frontier rỗng -> không có lời giải.
   b. Lấy một node khỏi frontier.
   c. Nếu node là goal -> trả lời giải.
   d. Đánh dấu node đã explored.
   e. Expand node:
      - sinh các state kế tiếp;
      - state mới hợp lệ thì đưa vào frontier.

Mermaid:

Một ví dụ chạy tay

Graph:

Ban đầu:

frontier = [A]
explored = {}

Lấy A, sinh B, C:

frontier = [B, C]
explored = {A}

Bây giờ thuật toán phải quyết định lấy B hay C trước. Chính quy tắc lấy node tạo ra các thuật toán khác nhau.

Code skeleton tối giản

Đây chưa phải DFS hay BFS; ta cố ý để phần remove_from_frontier() chưa xác định.

def search(start, goal):
    frontier = [Node(start, None, None, 0)]
    explored = set()

    while frontier:
        node = remove_from_frontier(frontier)

        if node.state == goal:
            return node

        explored.add(node.state)

        for action, next_state, step_cost in expand(node.state):
            if next_state in explored:
                continue

            child = Node(
                state=next_state,
                parent=node,
                action=action,
                path_cost=node.path_cost + step_cost,
            )
            frontier.append(child)

    return None

Ta chưa cần thuộc code. Hãy hiểu bốn ý:

1. frontier giữ node đang chờ;
2. mỗi vòng lấy một node;
3. goal thì dừng;
4. chưa goal thì sinh node con.

Reconstruct path

Khi tìm được goal node:

def reconstruct_path(node):
    actions = []
    states = []

    while node.parent is not None:
        actions.append(node.action)
        states.append(node.state)
        node = node.parent

    states.append(node.state)  # start

    actions.reverse()
    states.reverse()
    return actions, states

reverse() cần thiết vì ta lần từ Goal về Start.

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

“State chính là node”

Không. Nhiều node về lý thuyết có thể trỏ tới cùng một state qua các đường khác nhau. State là tình huống; node là bản ghi của thuật toán.

“Tới goal là xong nên thuật toán nào cũng cho đường tốt nhất”

Sai. Search strategy quyết định thứ tự khám phá, vì vậy có thuật toán tìm được lời giải nhưng không đảm bảo lời giải tối ưu.

“Ít bước nhất luôn là rẻ nhất”

Chỉ đúng nếu mọi step cost giống nhau.

“Explored chỉ để tăng tốc”

Nó còn giúp tránh cycle khiến thuật toán lặp vô hạn trên graph hữu hạn có chu trình.

Tóm tắt thuật ngữ

Tự kiểm tra

Cho bài toán robot đi trong phòng dạng grid.

1. State nên là gì?
2. Actions(s) trả gì?
3. Result(s, RIGHT) có nghĩa gì?
4. Tại sao cần parent trong Node?
5. Frontier và explored khác nhau thế nào?
6. Nếu mọi bước cost 1, path cost có thể tính đơn giản ra sao?
7. Nếu có một vòng A -> B -> C -> A, điều gì có thể xảy ra nếu không dùng explored set?

Phần tiếp theo chỉ thay đổi một câu hỏi: ta lấy node nào khỏi frontier trước? Từ đó có DFS và BFS.

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