Thuật toán quay lui Backtracking
Tác giả: PT Nguyễn Tiến Thành.
1. Mở đầu
Trong thế giới khoa học máy tính, có hai khái niệm cơ bản mà mọi lập trình viên cần nắm được đó là cấu trúc dữ liệu và giải thuật. Hai khái niệm này thường song hành nhau và giúp chúng ta giải quyết các bài toán một cách hiệu quả mất. Theo kinh nghiệm của bản thân tác giả thì càng làm việc lâu năm trong lĩnh vực khoa học máy tính chúng ta sẽ càng cần phải thành thạo trong việc thiết kế và sử dụng cấu trúc dữ liệu và thuật toán.
Với mong muốn chia sẻ kiến thức cho các bạn học viên mới bắt đầu tiếp xúc với bộ môn khoa học máy tính, ở bài viết này mình sẽ chia sẻ cùng các bạn học viên về giải thuật backtracking, một trong những giải thuật cơ bản và đã được tiếp xúc trong quá trình học ở câu lạc bộ.
Trong khóa học How to code complex, trong lesson 7: Mutual Reference chúng ta đã được học về Backtracking Search. Đây là một ứng dụng của thuật toán Backtracking (hay còn gọi là quay lui) trong việc giải quyết một bài toán tìm kiếm trên cấu trúc dữ liệu dạng tree. Trong khuôn khổ của bài viết này mình sẽ chia sẻ chi tiết hơn về ý tưởng tổng thể của thuật toán Backtracking và ứng dụng trong việc giải một số bài toán điển hình
2. Backtracking là gì?
Thuật toán backtracking là một phương pháp giải quyết các bài toán tìm kiếm, liệt kê hoặc xây dựng, nơi mà các output được tạo ra bằng cách thử từng lựa chọn một và từ bỏ những lựa chọn không dẫn đến kết quả hợp lý. Thuật toán này thường được sử dụng cho các vấn đề tìm kiếm có cấu trúc và tối ưu.
Backtracking thường thực hiện theo cách đệ quy. Trong quá trình thực hiện, nó duyệt qua mỗi lựa chọn có thể và thử từng lựa chọn một, gọi đệ quy để kiểm tra xem lựa chọn đó có dẫn đến một giải pháp hay không. Nếu lựa chọn hiện tại không dẫn đến giải pháp, thuật toán quay lại và thử lựa chọn khác.
3. Cách thuật toán hoạt động
Thuật toán backtracking hoạt động dựa trên việc thử từng lựa chọn có thể và quay lui khi gặp điều kiện không thỏa mãn. Dưới đây là mô tả chi tiết về cách thuật toán backtracking hoạt động.
- Bước 1 khởi tạo: Bắt đầu với một trạng thái ban đầu và khởi tạo các biến cần thiết để bắt đầu quá trình backtracking.
- Bước 2 kiểm tra điều kiện: Kiểm tra xem đã đạt được điều kiện dừng của bài toán hay chưa. Điều kiện này có thể là việc tìm thấy giải pháp hoặc đã thử tất cả các lựa chọn mà không tìm được giải pháp. Nếu điều kiện dừng được thỏa mãn thì thuật toán sẽ trả về kết quả và kết thúc tại đây.
- Bước 3 lựa chọn và kiểm tra ràng buộc: Chọn một lựa chọn trong không gian tìm kiếm và kiểm tra xem lựa chọn đó có thỏa mãn các ràng buộc của bài toán hay không. Nếu lựa chọn không thỏa mãn ràng buộc, quay lại và thử lựa chọn khác.
- Bước 4 cập nhật trạng thái: Cập nhật trạng thái của bài toán dựa trên lựa chọn đã chọn. Có thể cập nhật các biến, mảng hoặc cấu trúc dữ liệu khác để thể hiện trạng thái hiện tại.
- Bước 5 đệ quy: Thực hiện đệ quy để tiếp tục tìm kiếm các lựa chọn tiếp theo. Quá trình đệ quy sẽ được lặp lại cho đến khi tìm được giải pháp hoặc không còn lựa chọn nào khả thi.
- Bước 6 quay lui: Khi đã thử tất cả các lựa chọn hoặc không thể tiếp tục, quay lại trạng thái trước đó và thử các lựa chọn khác. Quá trình này được gọi là quay lui và cho phép ta khám phá các lựa chọn khác mà chưa được thử.
- Bước 7 trả về kết quả: Khi quá trình backtracking kết thúc, trả về giải pháp tìm được (nếu có) hoặc một tín hiệu rằng không có giải pháp nào tồn tại.
Quá trình backtracking sẽ tiếp tục cho đến khi một giải pháp được tìm thấy hoặc khi đã thử hết tất cả các lựa chọn mà không tìm ra giải pháp. Thuật toán này trở nên hiệu quả khi chúng ta có khả năng loại bỏ các nhánh tìm kiếm không cần thiết bằng cách thiết lập các điều kiện ràng buộc và thực hiện cắt nhánh. Việc này giúp giảm bớt khối lượng tính toán và tăng tốc độ tìm kiếm giải pháp.
Để có thể hiểu rõ hơn về thuật toán Backtracking, thì chúng ta sẽ cùng nhau biểu diễn dưới dạng lưu đồ:
– Bắt đầu từ nút gốc “Bước khởi tạo”, thuật toán bắt đầu quá trình backtracking.
– Ở bước “Kiểm tra điều kiện”, thuật toán kiểm tra xem đã đạt được điều kiện dừng của bài toán chưa. Nếu đã tìm thấy giải pháp, thuật toán kết thúc và trả về giải pháp.
– Trong trường hợp chưa tìm thấy giải pháp, thuật toán tiếp tục chọn một lựa chọn và thử nghiệm.
– Sau đó, thuật toán kiểm tra ràng buộc của lựa chọn.
– Nếu lựa chọn không thỏa mãn ràng buộc, thuật toán quay lại và thử một lựa chọn khác.
– Nếu lựa chọn thỏa mãn ràng buộc, thuật toán tiếp tục thử nghiệm và quay lại nếu cần thiết. Quá trình tiếp tục cho đến khi tìm thấy giải pháp hoặc đã thử hết tất cả các lựa chọn mà không tìm thấy giải pháp.
4. Ví dụ minh họa
Để hiểu rõ về thuật toán backtracking, thì chúng ta cùng nhau thử sức qua một bài toán cụ thể:
Xếp hậu (N-Queens Problem). Trong bài toán này, chúng ta cần đặt N quân hậu lên một bàn cờ kích thước NxN sao cho không có hai quân hậu nào tấn công nhau theo quy tắc của cờ vua. Điều này đòi hỏi mỗi quân hậu đặt trên một hàng, một cột và không chia sẻ đường chéo với bất kỳ quân hậu nào khác. Dưới đây là một ví dụ về input và output của bài toán xếp hậu:
Input: N = 4
Output:
[0, 1, 0, 0],
[0, 0, 0, 1],
[1, 0, 0, 0],
[0, 0, 1, 0]
Hoặc là:
[0, 0, 1, 0],
[1, 0, 0, 0],
[0, 0, 0, 1],
[0, 1, 0, 0]
Trong trường hợp này, chúng ta có một bàn cờ có kích thước 4×4 và cần tìm tất cả các cách xếp các quân hậu trên bàn cờ sao cho chúng không tấn công nhau. Có hai kết quả được hiển thị ở trên, mỗi giải pháp là một ma trận 4×4, trong đó mỗi phần tử có giá trị 0 nếu không có quân hậu và 1 nếu có quân hậu. Để hiểu rõ hơn nữa thì đây là quy trình cụ thể của thuật toán backtracking khi giải quyết bài toán Xếp hậu.
Bước 1. Khởi tạo:
– Tạo một bàn cờ rỗng kích thước NxN và đánh dấu tất cả các ô trống là chưa đặt quân hậu.
Bước 2. Bắt đầu từ hàng đầu tiên:
Bước 3. Đệ quy:
– Với mỗi ô trống trên hàng đó thử đặt quân hậu vào ô đó và kiểm tra xem nó có bị tấn công bởi quân hậu nào đã đặt trên bàn cờ hay không.
– Nếu ô không bị tấn công, đánh dấu ô đó là đã đặt quân hậu và tiếp tục đệ quy để đặt quân hậu trên hàng tiếp theo.
– Nếu ô bị tấn công, thử ô tiếp theo trên hàng đó.
Bước 4. Quay lui (Backtrack):
– Nếu không tìm được ô trống trên hàng đó để đặt quân hậu, quay lại hàng trước đó và thử đặt quân hậu vào ô tiếp theo trên hàng đó.
Bước 5. Lưu trữ kết quả:
– Nếu đã đặt được n quân hậu trên bàn cờ, lưu trữ kết quả và thoát khỏi đệ quy.
Bước 6. Quay lại và thử cách đặt quân hậu khác:
– Nếu đã kiểm tra tất cả các ô trên bàn cờ nhưng không tìm được cách đặt quân hậu hợp lệ, quay lại và thử cách đặt quân hậu khác.
Quy trình này sử dụng đệ quy để thử từng ô trống trên mỗi hàng của bàn cờ và sử dụng quay lui để thử lại khi không thể đặt quân hậu trong một số trường hợp.
Code thực hiện N-Queens bằng Python:
Giải thích code:
1. Hàm “is_safe”:
– Hàm này được sử dụng để kiểm tra xem có thể đặt quân hậu tại một vị trí cụ thể trên bàn cờ hay không. Nó kiểm tra các điều kiện sau:
– Không có quân hậu nào trên cùng hàng bên trái.
– Không có quân hậu nào trên cùng đường chéo trên bên trái.
– Không có quân hậu nào trên cùng đường chéo dưới bên trái.
2. Hàm “solve_n_queens_util”:
– Đây là hàm chính của thuật toán backtracking. Nó được sử dụng để thử tất cả các cách để đặt các quân hậu lên bàn cờ.
– Hàm này nhận ba tham số:
“board”: Ma trận đại diện cho bàn cờ.
“col”: Cột hiện tại mà chúng ta đang cố gắng đặt quân hậu.
“N”: Kích thước của bàn cờ (số hàng và số cột).
– Hàm này sử dụng đệ quy để thử đặt quân hậu vào mỗi hàng của cột “col”. Nếu không thể đặt quân hậu ở một hàng cụ thể, nó sẽ tiếp tục đệ quy để thử các hàng khác.
– Nếu không thể đặt được quân hậu vào bất kỳ hàng nào, hàm này sẽ quay lui để thử cách đặt quân hậu ở cột trước đó.
3. Hàm “solve_n_queens”:
– Đây là hàm gọi đầu tiên để giải bài toán xếp hậu.
– Nó tạo ra một bàn cờ rỗng bằng cách khởi tạo một ma trận với tất cả các giá trị là 0.
– Sau đó, nó gọi hàm “solve_n_queens_util” để bắt đầu quá trình giải quyết bài toán.
– Nếu không có giải pháp nào tồn tại, nó sẽ in ra thông báo “Không có giải pháp cho bài toán”.
Thuật toán backtracking được thực hiện bằng cách thử từng cách đặt quân hậu một cách tuần tự trên các hàng của bàn cờ và quay lui khi gặp phải các trường hợp không thể giải quyết được. Điều này cho phép thuật toán tìm kiếm qua tất cả các giải pháp có thể một cách hiệu quả.
Minh họa thuật toán N-Queens
5. Ứng dụng Backtracking vào một số bài toán khác
Bài toán Mã hóa và Giải mã: Trong bài toán mã hóa và giải mã bằng mã Morse, thuật toán backtracking được sử dụng để xử lí các bài toán liên quan đến việc mã hóa và giải mã thông điệp.
Cụ thể, backtracking có thể được sử dụng để giải mã một chuỗi Morse thành chuỗi ký tự tiếng Anh và ngược lại. Khi giải mã, thuật toán thử từng ký tự Morse và kiểm tra xem nó tương ứng với ký tự nào trong bảng chữ cái của mã Morse. Khi mã hóa, thuật toán tạo ra chuỗi Morse từ chuỗi ký tự ban đầu. Qua đó, backtracking giúp mã hóa và giải mã thông điệp bằng mã Morse một cách linh hoạt và hiệu quả.
Bài toán Mạng lưới từ (Word Grid Puzzle): Trong bài toán mạng lưới từ, chúng ta cần tìm tất cả các từ hợp lệ trong một lưới ký tự theo các hướng khác nhau (dọc, ngang, chéo). Backtracking có thể được sử dụng để kiểm tra từng ô và thử các từ có thể được tạo từ vị trí hiện tại. Bằng cách thử từng từ một cách đệ quy và loại bỏ các trường hợp không hợp lệ, thuật toán backtracking giúp tìm kiếm và xác định các từ trong mạng lưới một cách hiệu quả.
6. Ưu điểm và hạn chế của Backtrack
Ưu điểm: thuật toán Backtracking luôn đảm bảo duyệt qua tất cả các lựa chọn và không bỏ sót bất kỳ một lựa chọn nào. Ngoài ra thuật toán được triển khai một các dễ dàng và logic bằng cách sử dụng cùng với đệ quy hoặc vòng lặp
Nhược điểm: trong trường hợp một số bài toán có kích thước rất lớn hoặc là bài toán có nhiều điều kiện phức tạp, thuật toán Backtracking tiêu tốn nhiều bộ nhớ để duyệt, thử và quay lui tất cả lựa chọn. Điều này, sẽ khiến mất rất nhiều thời gian để ra kết quả. Ví dụ như là bài tìm kiếm đường đi ngắn nhất trong đô thị. Trong bài toán này, chúng ta cần tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đô thị. Thì với bài toán này không áp dụng thuật toán backtracking vì với đồ thị lớn thì số lượng đường đi rất lớn và phức tạp. Thuật toán Backtracking sẽ phải thử mọi khả năng kết hợp các cạnh và đỉnh để tìm kiếm ra đường đi có thể chứ không phải đường đi ngắn nhất. Điều này tốn rất nhiều thời gian để thực hiện trong khi bài toán đòi hỏi thời gian thực thi nhanh. Thay vào đó chúng ta có thể sử dụng thuật toán Dijkstra để tìm ra đường đi ngắn nhất một cách hiểu quả và đảm bảo.
7. Các phương pháp tối ưu và cải tiến cho thuật toán Backtrack
Cắt nhánh và nhánh cận (Pruning):
Trong thuật toán backtrack, khi thực hiện việc thử từng khả năng một để tìm ra giải pháp, chúng ta ta sẽ kiểm tra các ràng buộc và điều kiện để xác định xem một nhánh nào đó có khả năng dẫn đến kết quả hợp lệ hay không. Cắt nhánh và nhánh cận được áp dụng khi ta nhận thấy rằng một nhánh cụ thể của cây quyết định không thể đưa đến một giải pháp hợp lệ hoặc tốt hơn. Ví dụ, trong bài toán xếp hậu (N-Queens Problem), khi ta đặt một quân hậu vào bàn cờ, ta có thể sử dụng kỹ thuật cắt nhánh và nhánh cận để loại bỏ các vị trí trên bàn cờ mà chắc chắn sẽ không thể đặt được quân hậu mà không bị tấn công. Như vậy, thay vì thử tất cả các vị trí trên bàn cờ, ta chỉ cần thử các vị trí tiềm năng, giảm bớt thời gian và công sức cần thiết cho thuật toán. Phương pháp cắt nhánh và nhánh cận giúp tối ưu hóa thuật toán backtrack, giúp thuật toán hoạt động hiệu quả hơn và giảm bớt thời gian tìm kiếm giải pháp. Tối ưu hóa bằng hàm nhận dạng (Heuristic Function): Phương pháp Tối ưu hóa bằng hàm nhận dạng (Heuristic Function) là một kỹ thuật quan trọng được áp dụng trong thuật toán backtrack, nhằm cải thiện hiệu suất của thuật toán bằng cách đánh giá tính khả thi của một phần giải pháp và dự đoán xem nó có dẫn đến giải pháp tối ưu hay không. Kỹ thuật này dựa trên việc sử dụng các hàm nhận dạng để ước lượng và đánh giá các phần của giải pháp trong quá trình tìm kiếm. Ví dụ, trong bài toán tìm đường đi ngắn nhất trong một đồ thị, khi ta thử từng đường đi một để tìm đường đi tối ưu, ta có thể sử dụng hàm nhận dạng để đánh giá tính khả thi của một đường đi tiềm năng. Hàm nhận dạng có thể dựa trên các thông tin như khoảng cách từ đỉnh hiện tại đến đích, hoặc số lượng cạnh còn lại để duyệt qua. Đường đi nào có ước lượng khoảng cách ngắn hơn có thể được ưu tiên thử trước, giúp giảm thiểu thời gian tìm kiếm và tối ưu hóa thuật toán.
8. Kết luận
Như vậy chúng ta đã có một cái nhìn khá tổng thể về thuật toán quay lui. Hy vọng từ đó các bạn sẽ biết cách ứng dụng thuật toán vào giải quyết những vấn đề cụ thể khi lập trình. Có một lưu ý nhỏ là trong thực tế, khi viết chương trình đa phần các thư viện, framework, … đã hỗ trợ lập trình viên bằng cách tạo ra các hàm, lớp để thực thi sẵn thuật toán nên nhiều khi chúng ta chỉ cần biết cách sử dụng thuật toán và gọi hàm mà không cần biết cụ thể bên trong hàm như thế nào. Điều này sẽ giúp tốc độ hoàn thành chương trình nhanh hơn rất nhiều tuy nhiên các lập bạn vẫn nên tìm hiểu cụ thể xem thuật toán được thực hiện cụ thể như thế nào để hiểu sâu hơn về ý tưởng, tránh việc chỉ sử dụng hàm có sẵn mà không hiểu bên trong được viết như nào.
1,494 total views, 3 views today