Trong hướng dẫn này, bạn sẽ tìm hiểu thuật toán quay lui là gì. Ngoài ra, bạn sẽ tìm thấy một ví dụ về cách tiếp cận backtracking.
Thuật toán backtracking là một thuật toán giải quyết vấn đề sử dụng cách tiếp cận bạo lực để tìm ra đầu ra mong muốn.
Phương pháp Brute force thử tất cả các giải pháp có thể và chọn các giải pháp mong muốn / tốt nhất.
Thuật ngữ backtracking gợi ý rằng nếu giải pháp hiện tại không phù hợp, hãy quay lại và thử các giải pháp khác. Do đó, đệ quy được sử dụng trong cách tiếp cận này.
Cách tiếp cận này được sử dụng để giải quyết các vấn đề có nhiều giải pháp. Nếu bạn muốn có một giải pháp tối ưu, bạn phải lập trình động.
Cây không gian trạng thái
Cây trạng thái không gian là cây đại diện cho tất cả các trạng thái có thể có (giải pháp hoặc không giải) của bài toán từ gốc là trạng thái ban đầu đến lá là trạng thái cuối.
Cây không gian trạng thái
Thuật toán bẻ khóa
Backtrack (x) nếu x không phải là một giải pháp trả về false nếu x là một giải pháp mới, thêm vào danh sách các giải pháp backtrack (mở rộng x)
Ví dụ về Phương pháp theo dõi Backtracking
Bài toán: Bạn muốn tìm tất cả các cách có thể để xếp 2 nam và 1 nữ trên 3 chiếc ghế dài. Ràng buộc: Cô gái không nên ngồi trên băng ghế giữa.
Bài giải: Có tổng là 3! = 6 khả năng. Chúng tôi sẽ thử tất cả các khả năng và có được các giải pháp khả thi. Chúng tôi thử đệ quy tất cả các khả năng.
Tất cả các khả năng là:
Tất cả các khả năng
Cây không gian trạng thái sau đây cho thấy các giải pháp khả thi.
Cây trạng thái với tất cả các giải pháp
Ứng dụng thuật toán bẻ khóa
- Để tìm tất cả các Đường Hamilton có trong biểu đồ.
- Để giải quyết vấn đề N Queen.
- Giải quyết vấn đề mê cung.
- Vấn đề về chuyến du lịch của Hiệp sĩ.
