Thuật toán quay lui (Back-tracking algorithm)

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ạ

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