Vét cạn

Giới thiệu

Quay lui, vét cạn, thử sai, duyệt,...là người ta muốn nói đến cùng một phương trong lặp trình, đó là tìm nghiệm của một bài toán bằng cách thử hết các phương án có thể. Đối với con người, cách này không khả thi vì số lượng phép tính là quá lớn. Nhưng với máy tính, nhờ tốc độ xử lý nhanh nên tỏ ra hiệu quả trong trường hợp này. Ưu điểm của phương pháp này là luôn có thể tìm ra nghiệm, nhưng khuyết điểm là lượng xử lý quá nhiều, độ phức tạp cao, nên chỉ thích hợp cho các bài toán có tập dữ liệu nhỏ.

Mô hình vét cạn

- Tìm cách biểu diễn nghiệm thành dạng vector ( x1, x2, ..., xi, ...), sau đó tìm cách lấp dần các thành phần xi vào

- Xác định tập Si để chọn ra thành phần xi

- Tìm các điều kiện để một vector đã chọn là nghiệm của bài toán

* Lượt đồ tổng quát như sau