Embedded Files
Nguồn tham khảo:
Competitive Programming 4, Steven Halim
Nội dung
Nội dung
Bình luận:
Bình luận:
Dù được đa số các bạn học sinh, sinh viên biết đến với tên gọi "vét trâu - Brute Force", Backtracking vẫn có tầm quan trọng đáng kể ngay cả trong lập trình thi đấu. Việc sử dụng backtracking liệt kê ra các cấu hình của kết quả bài toán cho ta một góc nhìn để tìm ra giải thuật tốt hơn. Hơn nữa, dù có tìm ra giải thuật tốt, backtracking vẫn là một cổ máy kiểm tra tính đúng đắn của giải thuật một cách chuẩn xác. Tuy nhiên, nắm được kỹ thuật cũng như tìm ra phương pháp hiệu quả để backtrack là một nghệ thuật đòi hỏi các bạn phải luyện tập nhiều.
Một vài mẹo nhỏ:
Một vài mẹo nhỏ:
Nhận ra một bài toán có thể giải bằng backtracking:
Nhận ra một bài toán có thể giải bằng backtracking:
Bài toán yêu cầu liệt kê tất cả các cấu hình có thể của không gian mẫu
Có không gian mẫu nhỏ, trường hợp xấu nhất cũng chỉ tốn tầm 10^8 thao tác thực hiện
Có thời gian cho phép dài, và có tìm năng rút bớt các thao tác duyệt (nhánh cận)
Có thể tiền xử lý, tính toán (Pre-caculated)
Những bài toán thuộc loại khó nhưng không có tính chất gì đặc biệt.
Triển khai backtracking cho những bạn mới làm quen:
Triển khai backtracking cho những bạn mới làm quen:
Bước 1: Tạo vector nghiệm X có k thành phần: x1, x2, ..., xk (dùng cấu trúc dữ liệu bất kỳ: mảng, vector, ...)
Bước 2: Với mỗi xi, xác định không gian ứng viên Si để chọn các ứng viên điền vào cho nó.
Bước 3: Xác định điều kiện nghiệm: điều kiện để một vector đã đầy đủ các thành phần và đáp ứng điều kiện để là một nghiệm, nếu thỏa thì xuất ra nghiệm hoặc push nghiệm này vào thùng chứa nghiệm.
Bước 4: Nếu chưa thỏa điểu kiện nghiệm thì gọi đệ quy để tiếp tục điền ứng viên cho x(i+1)
Bước 5: Loại xi ra khỏi nghiệm (đây chính là điểm mấu chốt của quay lui, hàm ý rằng chúng ta quay lại điền cho vị trí đó nhưng với ứng viên khác trong không gian ứng viên.
Nhiệm vụ
Nhiệm vụ
Page updated
Google Sites
Report abuse