Thuật toán bẻ khóa
Thuật toán quay lui là gì?
Quay lui là một thuật toán tìm kiếm các kết hợp có thể để giải quyết vấn đề tính toán. Nó xây dựng dần dần các ứng viên và loại bỏ những ứng viên không thỏa mãn các ràng buộc đã cho. Kỹ thuật này rất hữu ích trong các tình huống mà bạn phải chọn một giải pháp khả thi trong số nhiều kết quả có thể.
Thuật toán này được coi là tốt hơn và hiệu quả hơn phương pháp Brute Force. Không giống như Bruteforce, thử tất cả các giải pháp có thể, Backtracking tập trung vào việc chỉ tìm một giải pháp cuối cùng theo khó khăn. Nó cũng tiết kiệm thời gian và bộ nhớ bằng cách hoàn tác bước cuối cùng (quay lại) và thử một tùy chọn khác sau khi đi đến ngõ cụt. Ngoài ra, nó dừng lại ngay khi tìm thấy giải pháp hợp lệ.
Quay lui là một kỹ thuật được sử dụng rộng rãi vì nó có thể giải quyết các vấn đề phức tạp mà không tiêu tốn quá nhiều tài nguyên. Nó đặc biệt hữu ích cho các vấn đề mà nhiều ràng buộc phải được thỏa mãn, chẳng hạn như Sudoku, bài toán n queen và lập lịch. Bằng cách điều hướng thông minh qua các giải pháp tiềm năng, quay lui có thể tìm ra câu trả lời thỏa mãn mọi điều kiện. Điều này làm cho nó trở nên vô giá đối với các nhiệm vụ đòi hỏi cả độ chính xác và hiệu quả.
Thuật toán quay lui hoạt động như thế nào?
Thuật toán quay lui là một kỹ thuật giải quyết vấn đề liên quan đến việc tìm ra các giải pháp hợp lệ từng bước. Nếu các ràng buộc của một bước không thỏa mãn một số điều kiện nhất định, thuật toán sẽ quay lại bước trước đó.
Sau đó, nó tiếp tục với các kết hợp khả thi khác thỏa mãn các ràng buộc đã cho. Vì có nhiều kết hợp khả thi nên nó chọn một trong những tùy chọn thỏa đáng nhất và giải quyết vấn đề theo trình tự. Kỹ thuật thuật toán này hữu ích khi bạn cần giải quyết một hoặc nhiều tùy chọn khả thi. Rút lui có nghĩa là hủy bỏ lựa chọn của bạn bất cứ khi nào một tình huống phát sinh không mang lại giải pháp hợp lệ.
Thuật toán quay lui có các bước sau đây nói chung để giải quyết một vấn đề:
Bước 1) Khởi tạo: Bắt đầu với giải pháp ban đầu rỗng/một phần.
Bước 2) Lựa chọn:Dựa trên các tiêu chí và ràng buộc cụ thể, hãy chọn một tùy chọn để mở rộng giải pháp hiện tại.
Bước 3) Khám phá: Giải quyết đệ quy bằng cách xem xét ứng viên đã chọn và tiến hành quá trình giải quyết vấn đề.
Bước 4) Kiểm tra ràng buộc: Kiểm tra xem giải pháp một phần hiện tại có vi phạm bất kỳ ràng buộc nào ở mọi bước không. Nếu có, hãy quay lại bước trước và thử một ứng viên khác.
Bước 5) Chấm dứt:Quá trình quay lui dừng lại khi tìm được giải pháp hợp lệ hoặc tất cả các kết hợp đã được sử dụng hết.
Bước 6) Quay lại: Nếu tùy chọn hiện tại không giải quyết được vấn đề đã cho, nó sẽ trở về trạng thái trước đó. Sau đó, nó sẽ xem xét tùy chọn mới để giải quyết vấn đề đã cho.
Bước 7) Lặp lại: Tiếp tục thực hiện các bước này cho đến khi vấn đề được giải quyết hoặc đã thử hết tất cả các tùy chọn.
Bản chất đệ quy của thuật toán quay lui
Thuật toán quay lui có bản chất đệ quy. Điều này có nghĩa là thuật toán tự gọi mình với các tham số khác nhau cho đến khi tìm ra giải pháp hoặc đã thử nghiệm tất cả các khả năng:
def find_solutions(n, other_params): if found_a_solution(): increment_solutions_found() display_solution() if solutions_found >= solution_target: exit_program() return for val in range(first, last+1): if is_valid(val, n): apply_value(val, n) find_solutions(n + 1, other_params) remove_value(val, n)
Các thuật ngữ phổ biến liên quan đến các vấn đề quay lui
Sau đây là một số thuật ngữ cơ bản liên quan đến kỹ thuật Backtracking:
- Giải pháp vector: Biểu diễn các giải pháp dưới dạng n-tuples, như (X1, X2, …, Xn).
- Những ràng buộc: Quy tắc giới hạn giá trị X, ngầm định và rõ ràng.
- Không gian giải pháp: Tất cả các giá trị X hợp lệ thỏa mãn các ràng buộc rõ ràng.
- Cây không gian tiểu bang: Biểu diễn không gian giải pháp dưới dạng cây.
- Không gian trạng thái: Mô tả các đường dẫn trong cây không gian trạng thái.
- Trạng thái vấn đề: Các nút trong cây tìm kiếm biểu diễn các giải pháp một phần.
- Trạng thái giải pháp: Các trạng thái tạo thành các bộ giải pháp hợp lệ trong S.
- Trả lời các tiểu bang: Thỏa mãn các ràng buộc ngầm định và đưa ra các giải pháp mong muốn.
- Nút hứa hẹn: Dẫn đến các giải pháp mong muốn và vẫn khả thi.
- Nút không hứa hẹn: Dẫn đến trạng thái không khả thi, không được khám phá thêm.
- Nút trực tiếp: Được tạo ra với những đứa trẻ chưa được khám phá.
- Nút E: Nút trực tiếp với thế hệ con đang diễn ra.
- Nút chết: Không có sự mở rộng nào thêm cho tất cả các phần tử con được tạo ra.
- Tạo nút theo chiều sâu: Sử dụng nút trực tiếp mới nhất làm nút E tiếp theo.
- Hàm giới hạn: Tối đa hóa hoặc tối thiểu hóa B(x1, x2, …, Xa) để tối ưu hóa.
- Cây tĩnh: Công thức cây độc lập với trường hợp vấn đề.
- Cây động: Công thức cây thay đổi tùy theo từng trường hợp vấn đề.
Khi nào nên sử dụng thuật toán quay lui?
Chúng ta có thể chọn kỹ thuật Quay lui để giải quyết một vấn đề phức tạp khi:
- Có nhiều sự lựa chọn: Quay lui là phù hợp nếu có nhiều lựa chọn ở mỗi bước của quá trình giải quyết vấn đề. Các lựa chọn này có thể liên quan đến việc lựa chọn các mục và di chuyển.
- Không có lựa chọn tốt nhất rõ ràng:Khi không có đủ thông tin để xác định lựa chọn tốt nhất trong số các tùy chọn có sẵn, có thể sử dụng thuật toán Quay lui.
- Quyết định này dẫn đến nhiều sự lựa chọn hơn: Bạn có thể chọn kỹ thuật quay lui để xem xét lại các lựa chọn một cách có hệ thống.
- Cần phải khám phá tất cả các giải pháp có thể:Quay lui là phương pháp khám phá tất cả các giải pháp một cách có hệ thống bằng cách đưa ra một loạt các quyết định dựa trên nhau.
Các loại vấn đề quay lui
Có ba loại vấn đề trong thuật toán quay lui: vấn đề quyết định, vấn đề tối ưu hóa và vấn đề liệt kê. Chúng ta hãy tìm hiểu về chúng bên dưới.
- Vấn đề quyết định: Trong loại bài toán này, mục tiêu là xác định xem có tồn tại giải pháp khả thi hay không. Chúng ta kiểm tra các câu trả lời "có" và "không". Ví dụ, bài toán n-quân hậu. Đây là bài toán quyết định kiểm tra khả năng đặt n quân hậu trên bàn cờ vua n × n mà không tấn công lẫn nhau.
- Vấn đề tối ưu hóa: Trong các bài toán tối ưu hóa, mục tiêu là tìm ra giải pháp khả thi tốt nhất trong số nhiều lựa chọn. Điều này có thể liên quan đến việc xác định giá trị cực đại và cực tiểu của một hàm hoặc biến nhất định. Ví dụ, hãy xem xét bài toán ba lô, trong đó mục tiêu là tối đa hóa tổng giá trị của các vật phẩm trong túi trong khi vẫn tuân thủ giới hạn trọng lượng của nó.
- Vấn đề liệt kê: Mục tiêu của nó là tìm ra tất cả các giải pháp khả thi cho một vấn đề nhất định. Chúng tôi liệt kê mọi tùy chọn hợp lệ mà không bỏ sót bất kỳ điều gì. Một ví dụ là tạo ra tất cả các tổ hợp chữ cái khả thi từ một tập hợp ký tự nhất định.
Ứng dụng của Backtracking & Ví dụ
Có nhiều ứng dụng khác nhau của Backtracking. Một số trong số chúng được giải thích bên dưới với mã giả của chúng.
- Sudoku Solver: Bài toán này chứa lưới con 3×3 với các số trùng lặp. Kỹ thuật quay lui sẽ cho thấy giải pháp trả về false, cho biết cần phải đặt số khác.
- Vấn đề N-Queen:Phương pháp quay lui xác định cách sắp xếp quân hậu trên bàn cờ vua N × N sao cho không quân nào có thể đe dọa lẫn nhau.
- Vấn đề tổng tập hợp con: Được sử dụng để tìm tập hợp con các số từ một tập hợp nhất định có tổng bằng một tổng mục tiêu cụ thể.
- Vấn đề về chu trình Hamilton: Có thể áp dụng phương pháp quay lui để tìm một hành trình khép kín trong đồ thị đi qua mỗi đỉnh đúng một lần.
- Bài toán Chuột trong Mê cung:Kỹ thuật quay lui được sử dụng để tìm đường đi của một con chuột từ điểm bắt đầu của mê cung đến lối ra.
function solveSudoku(board): if no empty cells: return true # Sudoku is solved for each empty cell (row, col): for num from 1 to 9: if num is valid in (row, col): place num in (row, col) if solveSudoku(board): return true remove num from (row, col) return false # No valid solution
function solveNQueens(board, col): if col >= N: return true # All queens are placed for each row in the column col: if isSafe(board, row, col): place queen at (row, col) if solveNQueens(board, col + 1): return true remove queen from (row, col) return false # No valid solution in this branch
function subsetSum(nums, target, index, currentSubset): if target == 0: print(currentSubset) # Subset with the target sum found return if index >= len(nums) or target < 0: return currentSubset.add(nums[index]) subsetSum(nums, target - nums[index], index + 1, currentSubset) currentSubset.remove(nums[index]) subsetSum(nums, target, index + 1, currentSubset)
Ưu điểm và nhược điểm của thuật toán quay lui
Ưu điểm của thuật toán quay lui
Kỹ thuật quay lui được sử dụng để giải quyết các vấn đề phức tạp. Nó có nhiều ưu điểm như:
- Kỹ thuật quay lui có hiệu quả trong việc xử lý các ràng buộc.
- Phương pháp này rất tốt để giải quyết các bài toán tối ưu hóa.
- Kỹ thuật này có hiệu quả với nhiều loại vấn đề khác nhau.
- Quy trình này có thể giúp xem xét tất cả các giải pháp có thể.
- Vì nó có thể quay lại nên tiết kiệm được nhiều bộ nhớ hơn so với kỹ thuật Bruteforce.
Nhược điểm của thuật toán quay lui
Kỹ thuật quay lui cũng có một số hạn chế, chẳng hạn như độ phức tạp về thời gian. Kỹ thuật này có những nhược điểm sau:
- Không có giải pháp nào được đảm bảo.
- Nó chậm hơn vì có nhiều sự kết hợp.
- Nó có độ phức tạp về thời gian cao vì có nhiều khả năng.
- Không phù hợp với những ràng buộc thời gian thực vì việc tìm ra giải pháp tốt nhất có thể mất nhiều thời gian.
- Hiệu quả phụ thuộc vào mức độ phức tạp của vấn đề.
Sự khác biệt giữa Backtracking và Recursion
Đệ quy | Quay lui |
---|---|
Gọi chính nó cho đến khi đạt được trường hợp cơ sở. | Sử dụng đệ quy để xem xét tất cả các khả năng cho đến khi tìm được kết quả khả thi tốt nhất. |
Phương pháp tiếp cận từ dưới lên. | Phương pháp tiếp cận từ trên xuống. |
Không có giá trị nào bị loại bỏ. | Các giải pháp không khả thi sẽ bị từ chối. |
Kết luận
Quay lui là một chiến lược thuật toán hữu ích để giải quyết các vấn đề phức tạp bằng cách khám phá các giải pháp khả thi một cách có hệ thống và quay lui khi cần thiết. Chúng ta có thể mong đợi các kỹ thuật quay lui sẽ được cải thiện với những cải tiến về sức mạnh tính toán và hiệu quả thuật toán. Những tiến bộ này sẽ cho phép chúng giải quyết các vấn đề lớn hơn và phức tạp hơn một cách hiệu quả.
Ngoài ra, các mô hình học máy có thể hướng dẫn các quyết định quay ngược dựa trên các mẫu đã học trước đó.
Tất cả những cải tiến công nghệ này sẽ cách mạng hóa các thuật toán quay lui, biến chúng thành một công cụ mạnh mẽ và linh hoạt để giải quyết các vấn đề phức tạp trong nhiều lĩnh vực.