Thuật toán quay lui là gì: cách hoạt động, code và ví dụ

Quay lui giải bài toán gì

Một số bài toán đòi hỏi mọi cách sắp xếp thỏa một tập quy tắc, hoặc chỉ một cách bất kỳ: đặt 8 quân hậu sao cho không quân nào tấn công nhau, điền một lưới Sudoku, liệt kê mọi tập con của một tập có tổng bằng giá trị đích, tìm mọi cách tách một chuỗi thành các từ trong từ điển. Không có công thức thông minh nào; bạn phải tìm kiếm. Thử mù quáng mọi tổ hợp hoàn chỉnh thì quá chậm, nhưng hầu hết các tổ hợp một phần đã không hợp lệ chỉ sau vài lựa chọn.

Quay lui kiểm tra các quy tắc sau mỗi lựa chọn. Khi một lời giải một phần vi phạm quy tắc, nó bỏ ngay cả nhánh đó của cây tìm kiếm và quay lại thử phương án tiếp theo.

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

1. Nếu lời giải một phần hiện tại đã hoàn chỉnh, ghi nhận nó.
2. Nếu không, với mỗi lựa chọn tiếp theo có thể: nếu lựa chọn được phép, thực hiện nó (chọn).
3. Đệ quy để mở rộng lời giải thêm (khám phá).
4. Hoàn tác lựa chọn, để phương án kế tiếp bắt đầu từ cùng trạng thái (bỏ chọn).

Không gian tìm kiếm là một cây: gốc là lời giải rỗng, mỗi tầng thêm một lựa chọn, và các lá là các ứng viên hoàn chỉnh. Quay lui là tìm kiếm theo chiều sâu trên cây này, còn cắt tỉa nghĩa là cắt bỏ các cây con không thể chứa lời giải.

Ví dụ: 4-Queens

Đặt 4 quân hậu trên bàn cờ 4 × 4, mỗi hàng một quân, sao cho không hai quân nào cùng cột hoặc cùng đường chéo. Các cột được đánh số từ 0 đến 3.

Tiếp tục tìm kiếm sẽ thấy lời giải duy nhất còn lại, 2, 0, 3, 1, là ảnh đối xứng gương của lời giải đầu.

Cài đặt bằng Python

Giữ các tập cột và đường chéo đã dùng để mỗi phép kiểm tra an toàn là O(1). Trên một đường chéo row - col là hằng số, và trên đường chéo kia row + col là hằng số.

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

Cùng mẫu này sinh ra mọi tập con và mọi hoán vị:

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Với tập con và hoán vị thông thường trong code thực tế, itertools.combinations và itertools.permutations nhanh hơn. Hãy tự viết quay lui khi bạn cần cắt tỉa bằng các quy tắc riêng của bài toán.

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

Quay lui không thể nhanh hơn kích thước đầu ra: nếu phải liệt kê n! hoán vị, bạn cần ít nhất n! bước. Cắt tỉa chỉ giúp bằng cách bỏ qua các nhánh không cho ra gì.

Biến thể và lỗi thường gặp

• Quên hoàn tác: nếu trạng thái không được khôi phục sau lời gọi đệ quy, các nhánh sau sẽ thấy những lựa chọn cũ.
• Thêm chính list đang dùng: result.append(current) lưu một tham chiếu sẽ bị thay đổi sau đó; hãy thêm current.copy().
• Phần tử trùng trong đầu vào: sắp xếp các phần tử và bỏ qua phần tử bằng phần tử trước ở cùng độ sâu để tránh tập con hoặc hoán vị trùng lặp.
• Dừng ở lời giải đầu tiên: trả về True từ đệ quy và dừng các vòng lặp khi một lời giải là đủ, như trong chương trình giải Sudoku.
• Sắp thứ tự tốt hơn: thử lựa chọn bị ràng buộc nhiều nhất trước (với Sudoku là ô trống có ít ứng viên nhất). Điều này thường thu nhỏ cây đáng kể.

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

• Thỏa mãn ràng buộc: Sudoku, ô chữ, tô màu bản đồ, lập thời khóa biểu và xếp lịch thi.
• Các bộ giải SAT và công cụ logic kiểu Prolog được xây trên tìm kiếm quay lui với cắt tỉa mạnh.
• Công cụ biểu thức chính quy ở nhiều ngôn ngữ, gồm re của Python, dùng quay lui; các mẫu viết tệ có thể quay lui theo hàm mũ (“catastrophic backtracking”).
• Bài phỏng vấn: subsets, permutations, combination sum, N-Queens, word search trên lưới, palindrome partitioning, generate parentheses, letter combinations of a phone number.