Sự khác biệt giữa Backtracking và Đệ quy là gì?
Sự khác biệt giữa Backtracking và Đệ quy là gì?
Đệ quy (recursion) là kỹ thuật lập trình: hàm tự gọi lại chính nó. Backtracking (quay lui) là chiến lược giải bài toán tìm kiếm, thường được cài đặt bằng đệ quy. Hai khái niệm không ngang hàng: backtracking dùng đệ quy, nhưng đệ quy không nhất thiết là backtracking.
Đệ quy thuần (không quay lui): giai thừa, Fibonacci, duyệt cây. Mỗi lời gọi giải một bài toán con rồi trả kết quả, không có bước “hoàn tác”.
def fact(n):
return 1 if n <= 1 else n * fact(n - 1)
Backtracking: xây lời giải từng bước. Ở mỗi bước ta chọn một lựa chọn, khám phá tiếp, nếu ngõ cụt hoặc đã xong thì hoàn tác (undo) lựa chọn rồi thử cái khác. Kết hợp cắt nhánh (pruning) để bỏ sớm những nhánh chắc chắn sai, nên nhanh hơn vét cạn.
def permutations(nums):
res, path, used = [], [], [False] * len(nums)
def dfs():
if len(path) == len(nums):
res.append(path[:]) # ghi nhận lời giải
return
for i, x in enumerate(nums):
if used[i]:
continue # cắt nhánh: đã dùng
used[i] = True; path.append(x) # chọn
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.