Uninformed Search: DFS và BFS

Giả sử frontier đang có năm node. Ta biết chúng đều là những hướng có thể thử, nhưng không có thêm thông tin hướng nào gần goal hơn.

Ta vẫn phải chọn một node để mở rộng trước.

Đây là uninformed search: thuật toán không dùng một ước lượng riêng về vị trí goal; nó chỉ dựa trên cấu trúc đã khám phá.

Hai chiến lược kinh điển là Depth-First Search (DFS) và Breadth-First Search (BFS).

Cùng một skeleton, khác cách quản lý frontier

Nhớ khung chung:

DFS và BFS khác nhau chủ yếu ở bước “lấy một node”.

DFS -> Stack -> Last In, First Out (LIFO)
BFS -> Queue -> First In, First Out (FIFO)

Depth-First Search - đi sâu trước

Trực giác

Hình dung bạn tìm một file trong nhiều thư mục:

Documents/
├── School/
│   ├── AI/
│   │   ├── Week1/
│   │   └── Week2/
│   └── Web/
└── Personal/

DFS chọn một nhánh rồi đi sâu hết mức có thể trước khi quay lại thử nhánh khác.

Một thứ tự DFS có thể là:

A -> B -> D -> F -> E -> C -> G

Thứ tự chính xác còn phụ thuộc thứ tự neighbor được thêm vào stack.

Stack và LIFO

Stack giống chồng đĩa:

Phần tử vào cuối cùng được lấy ra đầu tiên.

Python list đã có thể đóng vai stack:

stack = []
stack.append("A")
stack.append("B")
stack.append("C")

print(stack.pop())  # C

DFS pseudocode

push Start vào stack

while stack không rỗng:
    node = pop()

    nếu node là Goal:
        trả lời giải

    nếu node chưa explored:
        đánh dấu explored
        sinh các node con
        push các node con vào stack

DFS code dễ đọc

Ví dụ graph dạng adjacency list:

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

Cài DFS:

def dfs(graph, start, goal):
    stack = [start]
    parent = {start: None}

    while stack:
        state = stack.pop()

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

        for neighbor in graph[state]:
            if neighbor not in parent:
                parent[neighbor] = state
                stack.append(neighbor)

    return None

Hàm dựng đường:

def build_path(parent, goal):
    path = []
    current = goal

    while current is not None:
        path.append(current)
        current = parent[current]

    path.reverse()
    return path

Ở đây dictionary parent đồng thời giúp:

• nhớ đường đi;
• tránh thêm một state nhiều lần.

DFS mạnh ở đâu?

DFS có thể hữu ích khi:

• chỉ cần tìm một lời giải;
• lời giải có thể nằm sâu;
• muốn dùng ít bộ nhớ hơn BFS trong nhiều trường hợp;
• bài toán naturally phù hợp recursion/backtracking.

Nhưng DFS có nhược điểm lớn:

Lời giải đầu tiên DFS tìm thấy không nhất thiết là lời giải ngắn nhất hay rẻ nhất.

Ví dụ:

Nếu DFS đi nhánh A trước, nó có thể tìm:

S -> A -> B -> C -> G

trong khi đường ngắn hơn là:

S -> X -> G

Breadth-First Search - đi theo từng lớp

Trực giác

BFS không lao sâu vào một nhánh. Nó xét:

1. tất cả state cách Start 1 bước;
2. rồi tất cả state cách 2 bước;
3. rồi 3 bước;
4. …

Vì thế, nếu mọi bước cùng cost, goal đầu tiên BFS gặp sẽ nằm ở độ sâu nhỏ nhất.

Queue và FIFO

Queue giống xếp hàng:

vào sau -> [ C ][ B ][ A ] -> ra trước

A đến trước nên được xử lý trước.

Python nên dùng deque:

from collections import deque

queue = deque()
queue.append("A")
queue.append("B")
queue.append("C")

print(queue.popleft())  # A

BFS pseudocode

đưa Start vào queue

while queue không rỗng:
    node = popleft()

    nếu node là Goal:
        trả lời giải

    sinh các node con chưa thấy
    đưa chúng vào cuối queue

BFS code

from collections import deque


def bfs(graph, start, goal):
    queue = deque([start])
    parent = {start: None}

    while queue:
        state = queue.popleft()

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

        for neighbor in graph[state]:
            if neighbor not in parent:
                parent[neighbor] = state
                queue.append(neighbor)

    return None

So sánh với DFS chỉ cần nhìn hai dòng:

# DFS
state = stack.pop()

# BFS
state = queue.popleft()

Nhưng thay đổi nhỏ đó làm thứ tự khám phá khác hẳn.

Chạy BFS bằng tay

Graph:

Giả sử neighbor xét trái sang phải.

BFS mở rộng theo “lớp”.

BFS có luôn tối ưu không?

Câu này cần nói cẩn thận.

Trong ngữ cảnh graph không trọng số hoặc mọi step cost bằng nhau, BFS tìm đường có ít bước nhất, nên đó cũng là đường có cost nhỏ nhất.

Nhưng nếu cost khác nhau:

BFS có thể thích đường 2 cạnh:

S -> A -> G
cost = 101

trong khi đường 3 cạnh:

S -> B -> C -> G
cost = 3

rẻ hơn rất nhiều.

Vì vậy ghi nhớ chính xác:

BFS tối ưu về số bước khi mỗi bước có cùng chi phí; nó không phải thuật toán minimum-cost tổng quát cho graph có trọng số khác nhau.

Completeness: có chắc tìm được lời giải không?

Ta dùng từ complete để nói một thuật toán sẽ tìm được lời giải nếu lời giải tồn tại, dưới các giả định phù hợp.

Ở mức nhập môn:

• BFS thường được xem là complete nếu branching hữu hạn;
• DFS trên không gian hữu hạn và có kiểm soát visited có thể tìm lời giải, nhưng trên không gian vô hạn hoặc có nhánh sâu vô hạn, nó có thể mắc kẹt.

Ví dụ tưởng tượng:

Nếu DFS cứ đi nhánh trái vô hạn, nó chưa chắc quay lại G.

Bộ nhớ: vì sao BFS dễ “phình” hơn?

Giả sử mỗi state sinh khoảng 3 state mới.

Depth 0: 1
Depth 1: 3
Depth 2: 9
Depth 3: 27
Depth 4: 81

BFS phải giữ rất nhiều node của cả lớp đang chờ. DFS chủ yếu giữ đường đang đi cùng các nhánh chưa thử, nên trong nhiều bài toán có thể dùng ít bộ nhớ hơn.

Không cần thuộc công thức complexity ở giai đoạn này. Chỉ cần hiểu:

Nếu số nhánh tăng nhanh, BFS có thể tốn RAM rất mạnh.

So sánh nhanh

Khi nào chọn gì?

Chọn BFS khi

• graph không trọng số / step cost giống nhau;
• cần shortest path theo số bước;
• độ sâu lời giải không quá lớn.

Chọn DFS khi

• chỉ cần một lời giải;
• memory quan trọng;
• bài toán backtracking hoặc cần thăm sâu;
• không yêu cầu shortest path.

Không nên biến bảng này thành luật cứng. Việc chọn thuật toán còn phụ thuộc kích thước và cấu trúc state space.

Một ghi chú về recursion

DFS thường được viết rất tự nhiên bằng recursion:

def dfs_recursive(graph, state, goal, visited):
    if state == goal:
        return True

    visited.add(state)

    for neighbor in graph[state]:
        if neighbor not in visited:
            if dfs_recursive(graph, neighbor, goal, visited):
                return True

    return False

Nếu bạn mới học code, hãy hiểu recursion như sau:

Hàm giải bài toán hiện tại bằng cách gọi lại chính nó cho một bài toán nhỏ hơn: “thử tìm từ neighbor này”.

Không cần ép dùng recursion nếu phiên bản stack dễ hiểu hơn.

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

Đánh dấu visited quá muộn

Nếu graph có nhiều đường dẫn tới cùng state, có thể thêm cùng một state vào frontier nhiều lần.

Một cách đơn giản là dùng parent/visited ngay khi phát hiện state mới.

Dùng list.pop(0) cho BFS lớn

Nó chạy được nhưng không hiệu quả vì phải dịch các phần tử. Dùng:

from collections import deque
queue.popleft()

Nghĩ DFS luôn thăm A, B, C theo một thứ tự cố định

Thứ tự DFS phụ thuộc thứ tự neighbor và thứ tự push vào stack.

Tự kiểm tra

1. Vì sao DFS tương ứng Stack?
2. Vì sao BFS tương ứng Queue?
3. Nếu mọi cạnh cost 1, tại sao BFS tìm được đường ít bước nhất?
4. Nếu edge cost khác nhau, vì sao BFS có thể không tối ưu?
5. Graph rất rộng nhưng lời giải nằm sâu: BFS gặp vấn đề gì?
6. Chỉ cần kiểm tra “có đường hay không”, không cần shortest path: DFS có thể hợp lý ở điểm nào?
7. Hãy tự mô phỏng DFS và BFS trên cùng một graph và ghi lại thứ tự node được lấy khỏi frontier.

DFS và BFS hoàn toàn “mù” về vị trí goal. Nếu ta biết thêm một ước lượng hướng nào gần đích hơn, ta có thể dùng informed search.

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