Bài giảng Thuật toán nâng cao - Chương 8: Quay lui - Nguyễn Thanh Bình

Quay lui (backtracking)

| 0 Tìm kiếm vét cạn trong một không gian trang thái của bài toán

- Các giải pháp của bài toán được biểu hiện bởi một không gian trở 10 | thải (cụ thể là một cây). + Tìm kiễm giải pháp = tìm kiếm vết tàn trên không gian trang thái

| 0 Thường được sử dụng để giải quyết các bài toán yêu cầu tìm kiếm

Các phần tử của một tập hợp thoả mãn một số trang bốc

| 0 Nhiều bài toán được giải quyết bởi thuật toán quay lui cỏ dạng:

« Tim tập con S của A, x4, x. xAA là một tập hợp) sao cho mà phân tử: = =

5 ho mãn tàng buộc nào đó

Vi du + Tim tất cả các hoán vị của {1,2, -, n}

A = (1,2 ,n} vdi Vk

Svi Vik