Giới thiệu
Thuật toán quay lui (backtracking) là một kỹ thuật giải quyết bài toán phổ biến trong lĩnh vực toán học và khoa học máy tính. Thuật toán này giải quyết các bài toán tìm kiếm và liệt kê tất cả các giải pháp có thể của một bài toán.
Thuật toán quay lui thường được sử dụng khi ta có một bài toán tìm kiếm hoặc liệt kê tất cả các giải pháp có thể, nhưng không thể giải quyết bằng phương pháp thực hiện đầy đủ các giải pháp. Thay vào đó, thuật toán quay lui sẽ thử từng giải pháp theo trình tự và kiểm tra xem giải pháp đó có thỏa mãn yêu cầu của bài toán hay không. Nếu không thỏa mãn, thuật toán quay lại và thử giải pháp khác.
Thuật toán quay lui thường được sử dụng trong các bài toán liên quan đến đồ thị, cấu trúc dữ liệu cây, tìm kiếm chuỗi, và các bài toán khác. Thuật toán này có thể tối ưu hóa bằng cách cắt nhánh (pruning), tức là không thử các giải pháp không thể dẫn đến giải pháp tốt nhất của bài toán.
Thuật toán quay lui có thể được cài đặt bằng đệ quy hoặc không đệ quy, tùy thuộc vào bài toán cụ thể và phương pháp triển khai.
Mô tả thuật toán
Thuật toán quay lui là một thuật toán đệ quy để giải quyết các bài toán tìm kiếm hoặc liệt kê tất cả các giải pháp có thể của một bài toán. Thuật toán này thử từng giải pháp theo trình tự và kiểm tra xem giải pháp đó có thỏa mãn yêu cầu của bài toán hay không. Nếu không thỏa mãn, thuật toán quay lại và thử giải pháp khác.
Cách hoạt động của thuật toán quay lui như sau:
- Xác định các giải pháp tiềm năng và xây dựng cấu trúc dữ liệu phù hợp để lưu trữ các giải pháp đó.
- Bắt đầu với một giải pháp đơn giản nhất, ví dụ như một trường hợp đơn giản hoặc một giải pháp rỗng.
- Kiểm tra xem giải pháp đó có thỏa mãn yêu cầu của bài toán hay không. Nếu đúng, lưu trữ giải pháp đó và dừng thuật toán. Nếu không đúng, quay lại bước trước đó và thử một giải pháp khác.
- Lặp lại bước 3 cho tất cả các giải pháp tiềm năng, đến khi tìm thấy giải pháp thỏa mãn yêu cầu hoặc đã kiểm tra tất cả các giải pháp và không tìm thấy giải pháp nào thỏa mãn.
- Trả về kết quả hoặc tiếp tục thực hiện thuật toán nếu cần.
Trong quá trình thực hiện, thuật toán quay lui có thể tối ưu hóa bằng cắt nhánh (pruning), tức là không thử các giải pháp không thể dẫn đến giải pháp tốt nhất của bài toán. Điều này giúp thuật toán chạy nhanh hơn và tiết kiệm bộ nhớ hơn.
Ví dụ về thuật toán quay lui
Một ví dụ phổ biến về thuật toán quay lui là bài toán N-queens, trong đó cần đặt N con hậu trên bàn cờ NxN sao cho không có hai con hậu nào cùng đường chéo, hàng hoặc cột với nhau.
Ví dụ, nếu ta cần đặt 4 con hậu trên bàn cờ 4×4, ta có thể sử dụng thuật toán quay lui để tìm tất cả các cách đặt hậu. Các bước thực hiện của thuật toán như sau:
- Tạo một mảng 1 chiều với N phần tử để lưu vị trí hàng của các con hậu, ban đầu tất cả các phần tử đều được gán bằng -1.
- Tạo một hàm để kiểm tra xem vị trí đặt hậu mới có hợp lệ không, tức là không trùng hàng, cột hoặc đường chéo với bất kỳ hậu nào đã được đặt trên bàn cờ.
- Sử dụng đệ quy để thử tất cả các vị trí đặt hậu cho hàng đầu tiên. Nếu vị trí hợp lệ, đặt hậu vào vị trí đó và tiếp tục đệ quy để đặt hậu cho hàng tiếp theo. Nếu không hợp lệ, quay lại bước trước và thử vị trí khác.
- Nếu đã đặt được N con hậu, lưu trữ giải pháp và dừng thuật toán.
- Nếu đã thử hết tất cả các vị trí đặt hậu cho hàng đầu tiên mà không tìm được giải pháp, quay lại bước trước và thử các vị trí khác cho hàng trước đó.
- Lặp lại bước 5 cho tất cả các hàng, đến khi tìm được giải pháp hoặc đã kiểm tra hết tất cả các giải pháp
Cài đặt thuật toán quay lui với Python
Để cài đặt thuật toán quay lui với Python, ta cần làm các bước sau:
- Xác định các bước cơ bản của thuật toán.
- Viết một hàm đệ quy để thực hiện các bước cơ bản.
- Tạo một mảng để lưu trữ các giá trị trung gian và kết quả cuối cùng.
- Gọi hàm đệ quy với các giá trị đầu vào phù hợp.
Dưới đây là một ví dụ về cách cài đặt thuật toán quay lui để giải bài toán N-queens:
def is_valid(board, row, col):
for i in range(row):
if board[i] == col or \
board[i] - i == col - row or \
board[i] + i == col + row:
return False
return True
def n_queens(board, row, n, solutions):
if row == n:
solutions.append(board[:])
return
for col in range(n):
if is_valid(board, row, col):
board[row] = col
n_queens(board, row+1, n, solutions)
board[row] = -1
n = 4
board = [-1] * n
solutions = []
n_queens(board, 0, n, solutions)
print(solutions)
Kết quả của chương trình sẽ là một danh sách các giải pháp có thể có cho bài toán N-queens, với mỗi giải pháp là một danh sách các vị trí cột của các con hậu trên bàn cờ NxN./.
