Thuật toán tìm kiếm A* là gì: cách hoạt động, code và độ phức tạp

A* giải bài toán gì

Thuật toán Dijkstra mở rộng các nút theo vòng khoảng cách tăng dần theo mọi hướng, kể cả những hướng đi xa khỏi đích. Khi bạn biết đích ở đâu, đó là công việc lãng phí. A* thêm một heuristic, tức ước lượng quãng đường còn lại, để cuộc tìm kiếm bị kéo về phía đích. Đây là thuật toán chuẩn để tìm đường trong game, robot và bản đồ.

A* được Peter Hart, Nils Nilsson và Bertram Raphael mô tả năm 1968 trong bài “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”.

Ý tưởng bằng lời đơn giản

1. Đưa nút xuất phát vào hàng đợi ưu tiên (tập mở) với g = 0 và f = h(start).
2. Lấy ra nút có f nhỏ nhất. Nếu đó là đích, dựng lại đường đi và dừng.
3. Với mỗi nút kề, tính g tạm thời = g(current) + chi phí cạnh. Nếu tốt hơn g đã biết của nút kề, ghi lại, đặt nút cha, rồi đẩy nút kề vào với f = g + h.
4. Nếu tập mở rỗng thì không có đường đi.

Với h(n) = 0 cho mọi nút, A* trở thành đúng thuật toán Dijkstra. Với heuristic hoàn hảo, nó đi thẳng dọc một đường đi tối ưu.

Chọn heuristic

Một heuristic là chấp nhận được (admissible) nếu nó không bao giờ đánh giá quá cao chi phí còn lại thực tế. Nó là nhất quán (consistent, hay đơn điệu) nếu h(n) <= cost(n, m) + h(m) với mọi cạnh n → m. Heuristic nhất quán cũng chấp nhận được, và với chúng mỗi nút chỉ cần được mở rộng một lần.

Cài đặt bằng Python trên lưới

Lưới dưới đây có 5 hàng và 7 cột; # đánh dấu tường ở cột 5. Các ô được ghi là (row, column). Di chuyển lên, xuống, trái, phải với chi phí 1, nên khoảng cách Manhattan vừa chấp nhận được vừa nhất quán.

import heapq
def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
    g = {start: 0}
    parent = {start: None}
    open_heap = [(h(start), start)]
    while open_heap:
        f, cur = heapq.heappop(open_heap)
        if cur == goal:
            path = []
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            return path[::-1]
        if f > g[cur] + h(cur):
            continue                      # outdated entry
        r, c = cur
        for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != "#":
                ng = g[cur] + 1
                if ng < g.get(nb, float("inf")):
                    g[nb] = ng
                    parent[nb] = cur
                    heapq.heappush(open_heap, (ng + h(nb), nb))
    return None
grid = [".......",
        ".....#.",
        ".....#.",
        ".....#.",
        "......."]
path = a_star(grid, (2, 3), (2, 6))
print(len(path) - 1, path)
# 7 [(2, 3), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]

Ví dụ từng bước

Trong lưới ở trên, điểm xuất phát (2, 3) cách đích (2, 6) 3 bước theo đường thẳng, nên f đầu tiên là 0 + 3 = 3. Bức tường chặn đường thẳng đó, và đường đi ngắn nhất thực sự có 7 bước. A* khám phá điều này theo từng giai đoạn: nó mở rộng mọi ô có f nhỏ nhất, và khi hết thì đến f nhỏ nhất tiếp theo.

A* đã mở rộng 15 trong số 32 ô trống. Thuật toán Dijkstra (A* với h = 0) mở rộng cả 32, vì mọi ô trống đều cách điểm xuất phát tối đa 7 bước. Trên các bản đồ rộng và thoáng, mức tiết kiệm còn lớn hơn nhiều.

Độ phức tạp thời gian và không gian

Các biến thể tiết kiệm bộ nhớ gồm IDA* (A* tăng dần độ sâu), chỉ giữ đường đi hiện tại, đổi lại phải thăm lại các nút.

Khi nào dùng A* và ứng dụng thực tế

• Dùng A* khi chỉ có một đích và có ước lượng rẻ, chấp nhận được về chi phí còn lại, chẳng hạn khoảng cách hình học trên bản đồ.
• Dùng Dijkstra khi cần khoảng cách đến nhiều hoặc mọi nút, hoặc khi không có heuristic hữu ích. Dùng BFS cho đồ thị không trọng số khi heuristic mang lại ít lợi ích.
• Trò chơi điện tử: di chuyển đơn vị trên bản đồ ô vuông và lưới điều hướng (navigation mesh).
• Robot và lập kế hoạch tuyến đường, thường kết hợp với các điểm mốc hoặc phân cấp tính trước.
• Giải câu đố: 8-puzzle và 15-puzzle với khoảng cách Manhattan của các ô số làm heuristic.