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 trang

thắI (cụ thể là một cây) + Tim kiểm giải pháp = tim kiểm vết tàn trền khổng gian trang thái

n 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, xi, xe x A A là một tập hợp) sao cho

mỗi phần tử < ss="" )="s" hoa="" mần="" ràng="" buộc="" nào="">

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

A = (1,2 ,n} vdi Vk Ss, vdi Vik