Bài 8.1 - Tư duy backtracking với Python

Trong thế giới lập trình, chúng ta thường xuyên đối mặt với các bài toán đòi hỏi phải tìm kiếm một giải pháp hoặc tất cả các giải pháp từ một không gian lựa chọn khổng lồ. Hãy tưởng tượng bạn đang cố gắng tìm đường thoát khỏi một mê cung phức tạp, hoặc sắp xếp các quân cờ trên bàn cờ sao cho chúng không tấn công lẫn nhau. Những bài toán này có một điểm chung: chúng liên quan đến việc đưa ra các lựa chọn và kiểm tra xem những lựa chọn đó có dẫn đến giải pháp hợp lệ hay không.

Và đó chính là lúc kỹ thuật Backtracking (Quay lui) phát huy sức mạnh của nó.

Backtracking là gì? Cuộc phiêu lưu "Thử và Sai" có hệ thống

Backtracking là một thuật toán tổng quát để tìm kiếm tất cả (hoặc một vài) giải pháp cho các bài toán thỏa mãn ràng buộc. Nó hoạt động dựa trên ý tưởng xây dựng từng bước một ứng cử viên cho giải pháp. Tại mỗi bước, thuật toán sẽ kiểm tra xem ứng cử viên hiện tại có còn tiềm năng để phát triển thành một giải pháp hoàn chỉnh hay không.

Nếu ứng cử viên hiện tại vẫn tiềm năng và chưa hoàn thành: Thuật toán đưa ra một lựa chọn tiếp theo và tiếp tục xây dựng ứng cử viên.
Nếu ứng cử viên hiện tại không còn tiềm năng (vi phạm ràng buộc): Thuật toán nhận ra rằng đường này là "ngõ cụt". Nó sẽ quay lui (backtrack) về bước trước đó và thử một lựa chọn khác.
Nếu ứng cử viên hiện tại là một giải pháp hoàn chỉnh: Thuật toán ghi nhận giải pháp này và có thể tiếp tục quay lui để tìm kiếm các giải pháp khác nếu có.

Hãy hình dung lại ví dụ mê cung. Bạn đi theo một lối đi (lựa chọn). Nếu gặp tường (vi phạm ràng buộc), bạn không cố đâm vào tường mà quay lại ngã rẽ cuối cùng và thử lối đi khác (quay lui và thử lựa chọn khác). Cứ như vậy, bạn sẽ duyệt qua các khả năng cho đến khi tìm thấy lối ra (giải pháp) hoặc xác định rằng không có lối ra nào từ điểm xuất phát đó.

Backtracking thường được triển khai bằng đệ quy (recursion). Mỗi lời gọi đệ quy đại diện cho việc đưa ra một quyết định tại một bước trong quá trình xây dựng giải pháp.

Cấu trúc chung của một hàm Backtracking

Hầu hết các bài toán giải quyết bằng Backtracking có thể được mô tả bằng một hàm đệ quy có dạng:

def solve(current_state, ...):
    # 1. Kiểm tra điều kiện dừng / Trường hợp cơ sở (Base Case)
    # Nếu current_state là một giải pháp hoàn chỉnh:
    #     Lưu trữ/Xử lý giải pháp
    #     return (hoặc tiếp tục nếu muốn tìm tất cả giải pháp)

    # 2. Lặp qua các lựa chọn có thể có từ current_state
    for choice in possible_choices_from(current_state):
        # 3. Áp dụng lựa chọn
        new_state = apply_choice(current_state, choice)

        # 4. Kiểm tra ràng buộc (Constraint Check)
        # Nếu new_state là hợp lệ (thỏa mãn ràng buộc):
            # 5. Đệ quy (Thăm nhánh mới)
            # solve(new_state, ...)

            # 6. QUAY LUI (Undo Choice) - RẤT QUAN TRỌNG!
            # Hoàn trả trạng thái về như trước khi áp dụng choice
            # (Để các vòng lặp tiếp theo có thể thử các lựa chọn khác từ current_state ban đầu)

    # 7. Nếu không có lựa chọn nào dẫn đến giải pháp từ trạng thái này:
    #    Hàm kết thúc, quay trở về bước gọi trước đó (đệ quy trả về)

Bước "QUAY LUI (Undo Choice)" là trái tim của Backtracking, phân biệt nó với các thuật toán duyệt cây đơn giản. Nó đảm bảo rằng sau khi khám phá một nhánh của không gian tìm kiếm, trạng thái được khôi phục lại để các nhánh khác có thể được thử từ cùng một điểm xuất phát.

Hãy cùng xem xét một vài ví dụ kinh điển để hiểu rõ hơn cách Backtracking hoạt động trong Python.

Ví dụ 1: Tìm tất cả các Tập con (Subsets)

Bài toán: Cho một tập hợp (hoặc danh sách) các số nguyên phân biệt, trả về tất cả các tập hợp con (bao gồm cả tập hợp rỗng).

Phân tích Backtracking:

Không gian tìm kiếm: Mỗi tập con có thể được tạo ra bằng cách quyết định với mỗi phần tử trong tập hợp ban đầu là "có chọn nó vào tập con hiện tại hay không".
Lựa chọn: Tại mỗi bước, xem xét phần tử tiếp theo trong danh sách ban đầu. Lựa chọn là: 1) Bao gồm phần tử này vào tập con hiện tại, hoặc 2) Loại trừ phần tử này khỏi tập con hiện tại.
Ràng buộc: Không có ràng buộc phức tạp, chúng ta chỉ đơn giản muốn liệt kê tất cả các khả năng.
Trường hợp cơ sở: Khi đã xem xét qua tất cả các phần tử trong danh sách ban đầu, tập con hiện tại đã hoàn chỉnh.

Code Python:

def find_all_subsets(nums):
    results = [] # Danh sách để lưu trữ tất cả các tập con tìm được
    n = len(nums)

    def backtrack(index, current_subset):
        # Trường hợp cơ sở: Đã xem xét hết các phần tử
        if index == n:
            # Thêm bản sao của tập con hiện tại vào kết quả
            results.append(list(current_subset))
            return

        # Lựa chọn 1: KHÔNG bao gồm nums[index] vào tập con hiện tại
        backtrack(index + 1, current_subset)

        # Lựa chọn 2: CÓ bao gồm nums[index] vào tập con hiện tại
        current_subset.append(nums[index])
        backtrack(index + 1, current_subset)

        # QUAY LUI: Bỏ phần tử nums[index] vừa thêm vào
        # để các lựa chọn khác (trong vòng lặp for nếu có,
        # hoặc trong các lời gọi đệ quy trước đó) có thể được thử
        current_subset.pop()

    # Bắt đầu quá trình backtrack từ phần tử đầu tiên (index 0)
    # với tập con ban đầu là rỗng
    backtrack(0, [])
    return results

# Ví dụ sử dụng:
nums_example = [1, 2, 3]
all_subsets = find_all_subsets(nums_example)
print(f"Tập hợp ban đầu: {nums_example}")
print(f"Tất cả các tập con: {all_subsets}")

# Output mong đợi:
# Tập hợp ban đầu: [1, 2, 3]
# Tất cả các tập con: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
# (Thứ tự có thể khác tùy thuộc vào cách duyệt cây, nhưng các tập con là đủ)

Giải thích Code:

find_all_subsets(nums): Hàm chính nhận danh sách nums và trả về danh sách các tập con.
results = []: Một danh sách dùng chung để thu thập tất cả các giải pháp (tập con) khi chúng được tìm thấy.
backtrack(index, current_subset): Hàm đệ quy là trái tim của thuật toán.
- index: Chỉ số của phần tử trong nums mà chúng ta đang xem xét tại bước này.
- current_subset: Danh sách hiện tại đang được xây dựng.
if index == n:: Đây là trường hợp cơ sở. Khi index bằng độ dài của nums, điều đó có nghĩa là chúng ta đã xem xét qua tất cả các phần tử. current_subset lúc này là một tập con hoàn chỉnh, nên chúng ta thêm bản sao của nó vào results (dùng list(current_subset) để tránh việc results lưu trữ tham chiếu đến cùng một danh sách current_subset có thể bị thay đổi sau này).
backtrack(index + 1, current_subset): Đây là lựa chọn đầu tiên - không bao gồm nums[index]. Chúng ta đơn giản bỏ qua phần tử này và chuyển sang xem xét phần tử tiếp theo (index + 1). current_subset không thay đổi.
current_subset.append(nums[index]): Đây là bước áp dụng lựa chọn thứ hai - bao gồm nums[index]. Chúng ta thêm phần tử hiện tại vào current_subset.
backtrack(index + 1, current_subset): Sau khi thêm phần tử, chúng ta đệ quy để tiếp tục xây dựng tập con với phần tử tiếp theo (index + 1) và current_subset đã được cập nhật.
current_subset.pop(): Đây là bước QUAY LUI. Sau khi lời gọi đệ quy backtrack(index + 1, current_subset) ở trên trả về (tức là đã khám phá xong tất cả các tập con có chứa nums[index] từ trạng thái hiện tại), chúng ta phải loại bỏ nums[index] khỏi current_subset. Điều này khôi phục lại current_subset về trạng thái trước khi chúng ta thêm nums[index], cho phép vòng lặp (hoặc logic code) ở mức gọi trước đó có thể tiếp tục và thử các lựa chọn khác (ví dụ: không thêm nums[index] vào tập con nếu chúng ta đảo thứ tự hai lời gọi đệ quy).

Ví dụ này minh họa cách Backtracking khám phá không gian tìm kiếm dưới dạng một cây nhị phân: tại mỗi "nút" (tương ứng với việc xem xét một phần tử nums[index]), có hai "nhánh" (bao gồm hoặc không bao gồm phần tử đó). Bước pop() là hành động leo ngược cây về nút cha.

Ví dụ 2: Bài toán N-Queens (Xếp N quân Hậu)

Bài toán: Cho một bàn cờ vua kích thước N×N, đặt N quân Hậu lên bàn cờ sao cho không có hai quân Hậu nào tấn công lẫn nhau. Một quân Hậu tấn công theo hàng ngang, hàng dọc và hai đường chéo. Tìm tất cả các cấu hình hợp lệ.

Phân tích Backtracking:

Không gian tìm kiếm: Đặt N quân Hậu vào N vị trí trên bàn cờ N×N. Có N² vị trí cho quân Hậu đầu tiên, (N²-1) cho quân thứ hai, ... Đây là một không gian rất lớn.
Cải tiến không gian tìm kiếm: Vì không có hai quân Hậu nào có thể ở cùng một hàng hoặc cùng một cột, mỗi quân Hậu phải ở một hàng và một cột riêng biệt. Điều này có nghĩa là chúng ta có thể giới hạn việc tìm kiếm bằng cách đặt một quân Hậu vào mỗi hàng, và chỉ cần quyết định xem quân Hậu ở hàng r sẽ nằm ở cột c nào.
Lựa chọn: Tại hàng hiện tại row, thử đặt quân Hậu vào từng cột col từ 0 đến N-1.
Ràng buộc: Một quân Hậu chỉ có thể được đặt ở vị trí (row, col) nếu vị trí đó không bị tấn công bởi bất kỳ quân Hậu nào đã được đặt ở các hàng 0 đến row-1. Cần kiểm tra cột và hai đường chéo.
Trường hợp cơ sở: Đã đặt thành công quân Hậu vào tất cả N hàng (từ hàng 0 đến hàng N-1).

Code Python:

def solve_nqueens(n):
    results = [] # Danh sách để lưu trữ tất cả các giải pháp (cấu hình bàn cờ)

    # Sử dụng set để kiểm tra ràng buộc O(1) thay vì duyệt lại toàn bộ bàn cờ
    cols_occupied = set() # Lưu các cột đã có hậu
    diag1_occupied = set() # Lưu hiệu số hàng - cột (r - c) cho đường chéo chính
    diag2_occupied = set() # Lưu tổng hàng + cột (r + c) cho đường chéo phụ

    # board sẽ là một danh sách các chuỗi, mỗi chuỗi biểu diễn một hàng.
    # '.' là ô trống, 'Q' là quân Hậu.
    # Khởi tạo bàn cờ rỗng:
    board = [["." for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        # Trường hợp cơ sở: Đã đặt thành công quân Hậu vào tất cả N hàng
        if row == n:
            # Chuyển cấu hình bàn cờ từ list of lists sang list of strings
            # trước khi thêm vào results
            formatted_board = ["".join(r_list) for r_list in board]
            results.append(formatted_board)
            return

        # Lặp qua các cột có thể đặt quân Hậu ở hàng hiện tại (row)
        for col in range(n):
            # Kiểm tra ràng buộc: Có thể đặt quân Hậu ở (row, col) không?
            # Kiểm tra cột, đường chéo chính (hiệu số r-c), đường chéo phụ (tổng r+c)
            if col in cols_occupied or \
               (row - col) in diag1_occupied or \
               (row + col) in diag2_occupied:
                # Nếu vị trí (row, col) bị tấn công, bỏ qua cột này và thử cột tiếp theo
                continue

            # Nếu vị trí hợp lệ: Áp dụng lựa chọn - Đặt quân Hậu ở (row, col)
            cols_occupied.add(col)
            diag1_occupied.add(row - col)
            diag2_occupied.add(row + col)
            board[row][col] = "Q"

            # Đệ quy: Chuyển sang xử lý hàng tiếp theo
            backtrack(row + 1)

            # QUAY LUI: Hoàn tác lựa chọn - Xóa quân Hậu vừa đặt
            # (Để các lựa chọn cột khác ở hàng 'row' có thể được thử)
            cols_occupied.remove(col)
            diag1_occupied.remove(row - col)
            diag2_occupied.remove(row + col)
            board[row][col] = "."

    # Bắt đầu quá trình backtrack từ hàng đầu tiên (row 0)
    backtrack(0)
    return results

# Ví dụ sử dụng với N=4:
n_example = 4
solutions = solve_nqueens(n_example)
print(f"Số giải pháp cho bài toán {n_example}-Queens: {len(solutions)}")
print("Các giải pháp:")
for i, sol in enumerate(solutions):
    print(f"Giải pháp {i + 1}:")
    for row_str in sol:
        print(row_str)
    print("-" * n_example)

# Output mong đợi cho N=4 (sẽ có 2 giải pháp):
# Số giải pháp cho bài toán 4-Queens: 2
# Các giải pháp:
# Giải pháp 1:
# .Q..
# ...Q
# Q...
# ..Q.
# ----
# Giải pháp 2:
# ..Q.
# Q...
# ...Q
# .Q..
# ----

Giải thích Code:

solve_nqueens(n): Hàm chính, nhận kích thước n của bàn cờ.
results = []: Danh sách lưu các cấu hình bàn cờ hợp lệ.
cols_occupied, diag1_occupied, diag2_occupied: Các set là cách hiệu quả để kiểm tra nhanh chóng xem một cột hoặc đường chéo có bị chiếm đóng bởi quân Hậu nào ở các hàng trước đó hay không.
- col xác định cột.
- row - col là hằng số trên một đường chéo đi từ trái trên xuống phải dưới.
- row + col là hằng số trên một đường chéo đi từ trái dưới lên phải trên.
board = [["." for _ in range(n)] for _ in range(n)]: Biểu diễn bàn cờ dưới dạng danh sách các danh sách ký tự.
backtrack(row): Hàm đệ quy, cố gắng đặt quân Hậu vào row hiện tại.
if row == n:: Trường hợp cơ sở. Nếu đã xử lý xong N hàng (tức là row đạt đến n), chúng ta đã tìm thấy một cấu hình hợp lệ. Tạo bản sao của board dưới dạng danh sách các chuỗi và thêm vào results.
for col in range(n):: Lặp qua các lựa chọn. Tại hàng row, thử đặt quân Hậu vào từng cột col.
if col in cols_occupied or ...: Kiểm tra ràng buộc. Kiểm tra xem vị trí (row, col) có an toàn để đặt Hậu không bằng cách xem các set có chứa col, row - col, row + col hay không.
cols_occupied.add(col), etc., board[row][col] = "Q": Áp dụng lựa chọn. Nếu an toàn, đánh dấu cột và đường chéo là đã bị chiếm đóng và đặt 'Q' lên bàn cờ.
backtrack(row + 1): Đệ quy. Chuyển sang xử lý hàng tiếp theo.
cols_occupied.remove(col), etc., board[row][col] = ".": QUAY LUI. Sau khi lời gọi đệ quy cho hàng row + 1 kết thúc (cho dù nó có tìm được giải pháp từ trạng thái đó hay không), chúng ta phải hoàn tác việc đặt quân Hậu ở (row, col). Điều này xóa dấu hiệu chiếm đóng khỏi các set và đặt lại ô trên bàn cờ thành '.', cho phép vòng lặp for col tiếp tục và thử đặt quân Hậu ở cột col + 1 (nếu có).

Ví dụ N-Queens thể hiện rõ ràng tầm quan trọng của bước quay lui (remove từ set và đặt lại board[row][col] = "."). Nếu không có bước này, các lựa chọn đặt Hậu ở các cột khác trong cùng một hàng row sẽ bị ảnh hưởng sai bởi quân Hậu đã đặt trước đó, hoặc các lời gọi đệ quy ở các hàng sau sẽ không thể thử các vị trí đã "tạm thời" bị chiếm đóng.

Ví dụ 3: Tìm đường đi trong Mê cung đơn giản (Maze Solver)

Bài toán: Cho một mê cung được biểu diễn bằng lưới 2D (ví dụ: '.' là đường đi, '#' là tường, 'S' là điểm bắt đầu, 'E' là điểm kết thúc). Tìm xem có đường đi từ 'S' đến 'E' hay không. (Chúng ta sẽ tìm một đường đi và dừng lại).

Phân tích Backtracking:

Không gian tìm kiếm: Tất cả các con đường có thể đi từ điểm bắt đầu.
Lựa chọn: Tại vị trí hiện tại, thử đi theo 4 hướng: Lên, Xuống, Trái, Phải.
Ràng buộc: Không được đi vào tường ('#'), không được đi ra ngoài biên giới mê cung, và không được đi lại vào ô đã thăm trong cùng một đường đi (để tránh lặp vô hạn).
Trường hợp cơ sở: Đã đến được điểm kết thúc ('E').

Code Python:

def solve_maze(maze):
    rows = len(maze)
    cols = len(maze[0]) if rows > 0 else 0

    # Tìm điểm bắt đầu 'S'
    start_row, start_col = -1, -1
    for r in range(rows):
        for c in range(cols):
            if maze[r][c] == 'S':
                start_row, start_col = r, c
                break
        if start_row != -1: break

    # Nếu không tìm thấy điểm bắt đầu, không có đường đi
    if start_row == -1:
        return False

    # Sử dụng bản sao của mê cung để đánh dấu các ô đã đi
    # Tránh sửa đổi mê cung gốc nếu cần dùng lại
    visited_maze = [list(row) for row in maze]

    # Các hướng có thể di chuyển: (delta_row, delta_col)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Lên, Xuống, Trái, Phải

    def backtrack(r, c):
        # 1. Kiểm tra điều kiện dừng / Trường hợp cơ sở: Đã đến đích
        if visited_maze[r][c] == 'E':
            return True # Tìm thấy đường đi!

        # 2. Áp dụng lựa chọn: Đánh dấu ô hiện tại là đã thăm ('V' - visited)
        # Tránh lặp vô hạn bằng cách không quay lại ô này trong cùng một đường đi
        if visited_maze[r][c] != 'S': # Không đánh dấu 'S' là 'V' ngay để có thể bắt đầu
             visited_maze[r][c] = 'V'

        # 3. Lặp qua các lựa chọn: Thử đi theo 4 hướng
        for dr, dc in directions:
            new_r, new_c = r + dr, c + dc

            # Kiểm tra ràng buộc cho ô mới:
            # - Có nằm trong biên giới mê cung không?
            # - Có phải là tường '#' không?
            # - Có phải là ô đã thăm 'V' không? (tránh lặp)
            if 0 <= new_r < rows and 0 <= new_c < cols and \
               visited_maze[new_r][new_c] != '#' and \
               visited_maze[new_r][new_c] != 'V':

                # 4. Đệ quy: Nếu ô mới hợp lệ, thử đi đến đó
                if backtrack(new_r, new_c):
                    # Nếu lời gọi đệ quy trả về True, có nghĩa là
                    # đã tìm thấy đường đi từ ô mới đến đích
                    return True # Truyền tín hiệu tìm thấy đường đi lên

        # 6. QUAY LUI: Nếu không có hướng nào từ (r, c) dẫn đến đích
        # Điều này chỉ cần thiết nếu muốn tìm TẤT CẢ các đường đi
        # hoặc nếu 'V' có ý nghĩa khác. Trong trường hợp chỉ tìm MỘT đường
        # và thoát sớm như này, bước unmarking không thực sự cần thiết
        # cho tính đúng đắn, nhưng là *bản chất* của backtracking
        # và cần thiết nếu bạn muốn "undo" việc đánh dấu để thử các đường khác
        # từ một điểm rẽ nhánh trước đó.
        # Nếu muốn minh họa rõ bước quay lui:
        if visited_maze[r][c] == 'V':
             visited_maze[r][c] = '.' # Hoàn trả ô về trạng thái ban đầu (trừ 'S'/'E')

        # 7. Không tìm thấy đường đi từ (r, c)
        return False

    # Bắt đầu quá trình backtrack từ điểm 'S'
    return backtrack(start_row, start_col)

# Ví dụ sử dụng mê cung:
maze_example = [
    "S.##",
    ".#..",
    "..#E",
    "###."
]

# Chuyển chuỗi thành list of lists để có thể sửa đổi (đánh dấu 'V')
maze_list = [list(row) for row in maze_example]

if solve_maze(maze_list):
    print("Có đường đi trong mê cung!")
    # (Lưu ý: Hàm này chỉ kiểm tra sự tồn tại, không trả về đường đi)
    # (Để trả về đường đi, bạn cần lưu lại path_taken trong hàm đệ quy)
else:
    print("Không có đường đi trong mê cung.")

# Ví dụ mê cung không có đường đi:
maze_no_path = [
    "S##",
    "#E#",
    "###"
]
maze_no_path_list = [list(row) for row in maze_no_path]

if solve_maze(maze_no_path_list):
    print("Có đường đi trong mê cung (ví dụ 2)!")
else:
    print("Không có đường đi trong mê cung (ví dụ 2).")

# Output mong đợi:
# Có đường đi trong mê cung!
# Không có đường đi trong mê cung (ví dụ 2).

Giải thích Code:

solve_maze(maze): Hàm chính, nhận mê cung dưới dạng danh sách các chuỗi.
Tìm điểm 'S': Đoạn code tìm tọa độ start_row, start_col.
visited_maze = [list(row) for row in maze]: Tạo bản sao mê cung. Việc này quan trọng vì thuật toán sẽ đánh dấu các ô đã thăm. Nếu bạn chỉ muốn kiểm tra sự tồn tại của đường đi và không cần giữ lại mê cung gốc, bạn có thể sửa trực tiếp mê cung được truyền vào (nếu nó đã là list of lists).
directions: Danh sách các bộ (dr, dc) biểu thị 4 hướng di chuyển.
backtrack(r, c): Hàm đệ quy, cố gắng tìm đường đi từ vị trí hiện tại (r, c).
if visited_maze[r][c] == 'E': return True: Trường hợp cơ sở. Nếu ô hiện tại là 'E', chúng ta đã đến đích và trả về True.
if visited_maze[r][c] != 'S': visited_maze[r][c] = 'V': Áp dụng lựa chọn. Đánh dấu ô hiện tại là đã thăm. Điều này ngăn chặn việc thuật toán đi vòng tròn hoặc lặp lại các bước không cần thiết.
for dr, dc in directions:: Lặp qua các lựa chọn. Thử di chuyển theo từng hướng.
new_r, new_c = r + dr, c + dc: Tính toán tọa độ ô mới.
if 0 <= new_r < rows and ...: Kiểm tra ràng buộc. Kiểm tra xem ô mới có hợp lệ để di chuyển tới không (trong biên, không phải tường, chưa thăm).
if backtrack(new_r, new_c): return True: Đệ quy. Nếu ô mới hợp lệ, gọi đệ quy để thử tìm đường đi từ ô đó. Nếu lời gọi đệ quy trả về True, điều đó có nghĩa là một đường đi đến đích đã được tìm thấy thông qua ô mới này. Chúng ta có thể dừng tìm kiếm và truyền True lên các lớp gọi trên.
if visited_maze[r][c] == 'V': visited_maze[r][c] = '.': QUAY LUI. Nếu vòng lặp for directions kết thúc mà không tìm thấy đường đi nào (tức là không có lời gọi đệ quy nào trả về True), điều đó có nghĩa là từ ô (r, c) này, không có đường nào dẫn đến đích. Nếu ô (r, c) đã được đánh dấu là 'V' (và không phải 'S' hoặc 'E'), chúng ta có thể hoàn trả nó về trạng thái '.' để các đường đi khác (xuất phát từ các điểm rẽ nhánh trước đó) có thể có khả năng đi qua ô này. Ví dụ, nếu bạn đi từ A -> B -> C và C là ngõ cụt, khi quay lui từ C, bạn unmark C. Sau đó, bạn quay lui từ B, thử hướng khác B -> D. Lúc này, ô C đã được "mở khóa" và có thể được thăm lại nếu cần thiết trên một đường đi khác từ một điểm rẽ nhánh khác.
return False: Nếu sau khi thử tất cả các hướng mà không tìm thấy đường đi, hàm trả về False.

Ví dụ mê cung này minh họa cách backtracking có thể được sử dụng để tìm một giải pháp, và việc đánh dấu đã thăm kết hợp với quay lui giúp khám phá không gian tìm kiếm một cách hiệu quả mà không bị lặp.

Khi nào sử dụng Backtracking?

Backtracking là một kỹ thuật tuyệt vời cho các bài toán có cấu trúc như sau:

Có thể xây dựng giải pháp từng bước một: Mỗi bước thêm một phần tử, đưa ra một quyết định, hoặc gán một giá trị.
Tại mỗi bước, có một tập hợp các lựa chọn rõ ràng.
Có ràng buộc: Có thể kiểm tra tính hợp lệ của ứng cử viên giải pháp hiện tại ở bất kỳ bước nào và xác định sớm liệu nó có không thể phát triển thành một giải pháp hoàn chỉnh được nữa không (còn gọi là pruning - tỉa cành). Khả năng này là mấu chốt để Backtracking hiệu quả hơn duyệt toàn bộ không gian một cách mù quáng.
Bạn cần tìm tất cả các giải pháp, hoặc một giải pháp.

Một số bài toán kinh điển sử dụng Backtracking bao gồm:

Bài toán N-Queens
Giải Sudoku
Tìm tất cả các Hoán vị (Permutations)
Tìm tất cả các Tổ hợp (Combinations)
Bài toán Tổng con tập hợp (Subset Sum)
Tìm đường đi trong đồ thị hoặc mê cung
Tô màu đồ thị (Graph Coloring)

Tuy nhiên, cần lưu ý rằng Backtracking có thể có độ phức tạp về thời gian rất cao (thường là hàm mũ), đặc biệt nếu không có các ràng buộc mạnh mẽ để thực hiện pruning hiệu quả. Mặc dù vậy, đối với nhiều bài toán, nó là cách tiếp cận đơn giản và trực quan nhất để bắt đầu.

Tóm kết (trong phạm vi bài học)

Backtracking là một kỹ thuật thuật toán mạnh mẽ dựa trên ý tưởng khám phá không gian tìm kiếm một cách có hệ thống bằng cách xây dựng giải pháp từng bước, kiểm tra tính hợp lệ (ràng buộc) và quay lui khi gặp ngõ cụt. Việc triển khai Backtracking trong Python thường sử dụng đệ quy, nơi mỗi lời gọi đệ quy đại diện cho một quyết định, và bước hoàn tác (undo) sau lời gọi đệ quy là hành động quay lui vật lý trong code. Nắm vững tư duy này sẽ mở ra cánh cửa giải quyết nhiều bài toán phức tạp trong lập trình.

Comments

There are no comments at the moment.