NỘI DUNG
Thuật toán quay lui là gì?
Thuật toán quay lui là một kỹ thuật giải quyết bài toán bằng cách thử từng khả năng một cho đến khi tìm được lời giải hoặc kiểm tra tất cả các khả năng mà không có lời giải phù hợp. Thuật toán này thường được sử dụng trong các bài toán tìm kiếm và liệt kê tất cả các lời giải có thể.
Cơ bản, thuật toán quay lui hoạt động bằng cách xây dựng một cây tìm kiếm trạng thái, mỗi nút trạng thái đại diện cho một bước trong quá trình tìm kiếm. Thuật toán duyệt qua cây theo chiều sâu, kiểm tra từng trạng thái và quyết định xem có tiếp tục đi xuống nhánh con hay trở lại nhánh cha và thử một lựa chọn khác.
Thuật toán quay lui thường được triển khai bằng đệ quy, trong đó hàm đệ quy gọi lại chính nó để tiếp tục tìm kiếm các trạng thái tiếp theo. Khi tìm thấy một lời giải, thuật toán dừng lại và trả về kết quả, hoặc tiếp tục tìm kiếm cho đến khi kiểm tra tất cả các khả năng.
Thuật toán quay lui thường có thể được tối ưu bằng cách sử dụng các kỹ thuật như cắt tỉa (pruning) để loại bỏ các trạng thái không cần thiết và tránh duyệt qua các khả năng không cần thiết. Điều này giúp cải thiện hiệu suất và giảm thời gian chạy của thuật toán.
Tóm lại, thuật toán quay lui là một phương pháp mạnh mẽ để giải quyết các bài toán tìm kiếm và liệt kê lời giải. Tuy nhiên, nó cũng có thể đòi hỏi đến mức thời gian và bộ nhớ lớn, đặc biệt là khi kích thước của không gian tìm kiếm lớn.
Dưới đây là 20 ví dụ về các bài toán áp dụng thuật toán quay lui trong ngôn ngữ Python.
Tìm tất cả các hoán vị của một danh sách số nguyên
def permute(nums):
result = []
backtrack(nums, [], result)
return result
def backtrack(nums, path, result):
if not nums:
result.append(path)
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], path + [nums[i]], result)
nums = [1, 2, 3]
print(permute(nums))
Tìm tất cả các tập con có tổng bằng một số cho trước
def combination_sum(nums, target):
result = []
nums.sort()
backtrack(nums, target, [], result)
return result
def backtrack(nums, target, path, result):
if target == 0:
result.append(path)
if target < 0:
return
for i in range(len(nums)):
backtrack(nums[i:], target - nums[i], path + [nums[i]], result)
nums = [2, 3, 6, 7]
target = 7
print(combination_sum(nums, target))
Tìm tất cả các chuỗi con không trùng nhau của một chuỗi ký tự
def find_substrings(s):
result = []
backtrack(s, '', result)
return result
def backtrack(s, path, result):
if path:
result.append(path)
for i in range(len(s)):
backtrack(s[i+1:], path + s[i], result)
s = 'abc'
print(find_substrings(s))
Tìm tất cả các lời giải của bài toán Sudoku
def solve_sudoku(board):
solve(board)
def solve(board):
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(board, i, j, num):
board[i][j] = num
if solve(board):
return True
board[i][j] = '.'
return False
return True
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num or board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
return False
return True
board = [['5', '3', '.', '.', '7', '.', '.', '.', '.'],
['6', '.', '.', '1', '9', '5', '.', '.', '.'],
['.', '9', '8', '.', '.', '.', '.', '6', '.'],
['8', '.', '.', '.', '6', '.', '.', '.', '3'],
['4', '.', '.', '8', '.', '3', '.', '.', '1'],
['7', '.', '.', '.', '2', '.', '.', '.', '6'],
['.', '6', '.', '.', '.', '.', '2', '8', '.'],
['.', '.', '.', '4', '1', '9', '.', '.', '5'],
['.', '.', '.', '.', '8', '.', '.', '7', '9']]
solve_sudoku(board)
for row in board:
print(row)
Tìm tất cả các hoán vị của một chuỗi ký tự
def permute_string(s):
result = []
backtrack(list(s), 0, len(s) - 1, result)
return result
def backtrack(s, left, right, result):
if left == right:
result.append(''.join(s))
else:
for i in range(left, right + 1):
s[left], s[i] = s[i], s[left]
backtrack(s, left + 1, right, result)
s[left], s[i] = s[i], s[left]
s = "ABC"
print(permute_string(s))
Tìm tất cả các cách sắp xếp các quân cờ con trên bàn cờ vua kích thước NxN sao cho chúng không tấn công nhau
def solve_n_queens(n):
result = []
queens = [-1] * n
backtrack(queens, 0, result)
return result
def backtrack(queens, row, result):
n = len(queens)
if row == n:
result.append(generate_board(queens))
else:
for col in range(n):
if is_safe(queens, row, col):
queens[row] = col
backtrack(queens, row + 1, result)
queens[row] = -1
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or queens[i] - i == col - row or queens[i] + i == col + row:
return False
return True
def generate_board(queens):
board = []
n = len(queens)
for i in range(n):
row = ['.'] * n
row[queens[i]] = 'Q'
board.append(''.join(row))
return board
n = 4
print(solve_n_queens(n))
Tìm tất cả các cách chia một tập hợp số thành các tập con có tổng bằng nhau
def can_partition(nums):
target = sum(nums)
if target % 2 != 0:
return False
target //= 2
visited = [False] * len(nums)
return backtrack(nums, 0, target, 0, visited)
def backtrack(nums, start, target, curr_sum, visited):
if target == curr_sum:
return True
if curr_sum > target:
return False
for i in range(start, len(nums)):
if not visited[i]:
visited[i] = True
if backtrack(nums, i + 1, target, curr_sum + nums[i], visited):
return True
visited[i] = False
return False
nums = [1, 5, 11, 5]
print(can_partition(nums))
Tìm tất cả các lời giải của bài toán N-Queens II (số cách xếp N quân hậu trên bàn cờ không tấn công nhau)
def total_n_queens(n):
count = 0
queens = [-1] * n
backtrack(queens, 0, count)
return count
def backtrack(queens, row, count):
n = len(queens)
if row == n:
count += 1
else:
for col in range(n):
if is_safe(queens, row, col):
queens[row] = col
count = backtrack(queens, row + 1, count)
queens[row] = -1
return count
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or queens[i] - i == col - row or queens[i] + i == col + row:
return False
return True
n = 4
print(total_n_queens(n))
Tìm tất cả các tập con có tổng bằng một số cho trước (sử dụng mỗi phần tử chỉ một lần)
def combination_sum_unique(nums, target):
result = []
nums.sort()
backtrack(nums, target, [], result)
return result
def backtrack(nums, target, path, result):
if target == 0:
result.append(path)
if target < 0:
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
backtrack(nums[i+1:], target - nums[i], path + [nums[i]], result)
nums = [10, 1, 2, 7, 6, 1, 5]
target = 8
print(combination_sum_unique(nums, target))
Tìm tất cả các chuỗi con có độ dài k cho trước của một chuỗi ký tự
def find_substrings_k(s, k):
result = []
backtrack(s, k, '', result)
return result
def backtrack(s, k, path, result):
if len(path) == k:
result.append(path)
else:
for i in range(len(s)):
backtrack(s[i+1:], k, path + s[i], result)
s = 'abc'
k = 2
print(find_substrings_k(s, k))
Tìm tất cả các lời giải của bài toán Palindrome Partitioning (chia chuỗi thành các chuỗi con đối xứng)
def partition(s):
result = []
backtrack(s, [], result)
return result
def backtrack(s, path, result):
if not s:
result.append(path)
for i in range(1, len(s) + 1):
if is_palindrome(s[:i]):
backtrack(s[i:], path + [s[:i]], result)
def is_palindrome(s):
return s == s[::-1]
s = "aab"
print(partition(s))
Tìm tất cả các lời giải của bài toán Combination Sum III (tìm các tập con có kích thước k và tổng bằng n)
def combination_sum3(k, n):
result = []
backtrack(range(1, 10), k, n, [], result)
return result
def backtrack(nums, k, target, path, result):
if target == 0 and len(path) == k:
result.append(path)
if target < 0 or len(path) == k:
return
for i in range(len(nums)):
backtrack(nums[i+1:], k, target - nums[i], path + [nums[i]], result)
k = 3
n = 7
print(combination_sum3(k, n))
Tìm tất cả các lời giải của bài toán Letter Combinations of a Phone Number (tạo chuỗi ký tự từ số điện thoại)
def letter_combinations(digits):
if not digits:
return []
mapping = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
result = []
backtrack(digits, mapping, '', result)
return result
def backtrack(digits, mapping, path, result):
if not digits:
result.append(path)
return
for char in mapping[digits[0]]:
backtrack(digits[1:], mapping, path + char, result)
digits = '23'
print(letter_combinations(digits))
Tìm tất cả các lời giải của bài toán Permutations II (tìm tất cả các hoán vị có phần tử trùng lặp)
def permute_unique(nums):
result = []
nums.sort()
backtrack(nums, [], result, [False] * len(nums))
return result
def backtrack(nums, path, result, used):
if len(path) == len(nums):
result.append(path)
return
for i in range(len(nums)):
if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
continue
used[i] = True
backtrack(nums, path + [nums[i]], result, used)
used[i] = False
nums = [1, 1, 2]
print(permute_unique(nums))
Tìm tất cả các lời giải của bài toán Word Search (tìm từ trong ma trận ký tự)
def exist(board, word):
for i in range(len(board)):
for j in range(len(board[0])):
if backtrack(board, i, j, word):
return True
return False
def backtrack(board, row, col, word):
if len(word) == 0:
return True
if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[0]:
return False
temp = board[row][col]
board[row][col] = '#'
result = backtrack(board, row + 1, col, word[1:]) or \
backtrack(board, row - 1, col, word[1:]) or \
backtrack(board, row, col + 1, word[1:]) or \
backtrack(board, row, col - 1, word[1:])
board[row][col] = temp
return result
board = [['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
word = "ABCCED"
print(exist(board, word))
Tìm tất cả các lời giải của bài toán Combinations (tìm tất cả các tập con kích thước k từ một tập con số)
def combine(n, k):
result = []
backtrack(range(1, n + 1), k, [], result)
return result
def backtrack(nums, k, path, result):
if k == 0:
result.append(path)
return
for i in range(len(nums)):
backtrack(nums[i+1:], k - 1, path + [nums[i]], result)
n = 4
k = 2
print(combine(n, k))
Tìm tất cả các lời giải của bài toán Subsets (tìm tất cả các tập con của một tập hợp số)
def subsets(nums):
result = []
backtrack(nums, 0, [], result)
return result
def backtrack(nums, start, path, result):
result.append(path)
for i in range(start, len(nums)):
backtrack(nums, i + 1, path + [nums[i]], result)
nums = [1, 2, 3]
print(subsets(nums))
Tìm tất cả các lời giải của bài toán Combination Sum II (tìm tất cả các tập con có tổng bằng một số cho trước, có phần tử trùng lặp)
def combination_sum2(candidates, target):
result = []
candidates.sort()
backtrack(candidates, target, [], result, 0)
return result
def backtrack(candidates, target, path, result, start):
if target == 0:
result.append(path)
return
if target < 0:
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]:
continue
backtrack(candidates, target - candidates[i], path + [candidates[i]], result, i + 1)
candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8
print(combination_sum2(candidates, target))
Tìm tất cả các lời giải của bài toán Generate Parentheses (tạo chuỗi ngoặc đúng)
def generate_parentheses(n):
result = []
backtrack(n, n, '', result)
return result
def backtrack(left, right, path, result):
if left == 0 and right == 0:
result.append(path)
return
if left > 0:
backtrack(left - 1, right, path + '(', result)
if right > left:
backtrack(left, right - 1, path + ')', result)
n = 3
print(generate_parentheses(n))
Tìm tất cả các lời giải của bài toán Combination Sum IV (tìm tất cả các cách tạo ra một số cho trước bằng tổng các số trong một tập hợp, có thể lặp lại)
def combination_sum4(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target+ 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp[target]
nums = [1, 2, 3]
target = 4
print(combination_sum4(nums, target))
Trên đây à 20 ví dụ bài toán áp dụng thuật toán quay lui trong Python. Hy vọng rằng chúng có thể giúp bạn hiểu và áp dụng thuật toán này vào các bài toán khác nhau. Cảm ơn các bạn đã đọc hết bài viết./.