Thuật toán quay lui (Back-tracking algorithm) là gì ?
Thuật toán quay lui dùng để giải các bài toán liệt kê cấu hình
Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chon bằng cách thử tất cả các khả năng
Bài toán minh hoạ Thuật toán quay lui
Ví dụ điển hình là thuật toán xếp hậu: đặt lần lượt các quân hậu lên bàn cờ sao cho quân hậu đặt sau không ăn được quan đã đặt trước đó.
Dead end: trạng thái chưa kết thúc, nhưng ta không thể đặt thêm được một quân hậu nào nữa.
Khi rơi vào trạng thái dead end ta phải tiến hành quay lui (backtrack) lại lựa chọn gần nhất để thử một khả năng có thể khác.
Thuật toán
Thử tìm kiếm lời giải đày đủ cho bài toán từ việc xây dựng lời giải bộ phận, trong đó lời giải bộ phận phải luôn phù hợp với yêu cầu bài toán.
Trong quá trình thực hiện, thuật toán mở rộng dần lời giải bộ phận. Nếu việc mở rộng khiến lời giải bộ phận vi phạm yêu cầu bài toán thì tiến hành quay lui, loại bỏ sửa đổi gần nhất và thử một khả năng xây dựng lời giải bộ phận có thể khác.
Giải thuật bài toán 8 con hậu
Thử lần lượt từng vị trí hàng Nếu vị trí thử không bị con hậu nào tấn công thì con hậu thứ 8 là an toàn Đệ quy với con hậu tiếp theo Xoá để tiếp tục thử vị trí [row+1,column]
Kiểm tra an toàn
Loạt bài hướng dẫn Cấu trúc dữ liệu và giải thuật của chúng tôi dựa trên nguồn tài liệu của trang: Tutorialspoint
