Nội dung

Backtracking algorithm GV Phi Loan - BM HTTT - Khoa CNTT - HUI 1 Nội dung  Tư tưởng giải thuật  Giải thuật tìm hoán vị  Giải thuật mã đi tuần  Giải thuật tám hậu GV Phi Loan - BM HTTT - Khoa CNTT - HUI 2 Backtracking algorithm  Là 1 giải thuật chung để tìm tất cả lời giải cho 1 bài toán, bằng cách xây dựng từng bước các ứng viên (candidate) cho lời giải và loại bỏ ("backtracks") 1 ứng viên nào đó ngay khi phát hiện ứng viên đó không thể dẫn đến 1 lời giải hợp lệ. GV Phi Loan - BM HTTT - Khoa CNTT - HUI 3 Backtracking algorithm  Bài toán tiêu biểu:  Tám hậu eight queens puzzle: 1 ứng viên đáng kể cho bài toán là sắp xếp k hậu vào k hàng đầu tiên của bàn cờ trong những hàng và cột khác nhau sao cho không có 2 hậu nào tấn công nhau. Bất kz lời giải nào mà chứa 2 hậu có thể tấn công nhau đều phải loại trừ ngay vì không thể nào đưa đến kết quả cuối cùng được. GV Phi Loan - BM HTTT - Khoa CNTT - HUI 4 Ứng dụng của giải thuật Backtracking  Để giải quyết các bài toán thỏa mãn ràng buộc (constraint satisfaction problems) như crosswords, verbal arithmetic, Sudoku, ..  Để giải các bài toán tối ưu hóa tổ hợp (combinatorial optimization problems) như parsing, knapsack problem … GV Phi Loan - BM HTTT - Khoa CNTT - HUI 5 Ý tưởng phương pháp  Có thể xem nghiệm bài toán là một vector x = (x1, x2, ... ,xn) mà xi được chọn trong Ai nào đó  Giả sử đã chọn được k-1 thành phần x1, x2, ..., xk-1 của x  Kế đến chọn thành phần xk bằng cách duyệt mọi khả năng có thể (trong Ak) để đề cử cho xk GV Phi Loan - BM HTTT - Khoa CNTT - HUI 6 Ý tưởng phương pháp  Với mỗi khả năng j, kiểm tra xem có chấp nhận được không, có 2 trường hợp:  Nếu chấp nhận j thì xác định xk theo j, khi k = n thì có một lời giải, ngược lại thì tiếp tục xác định xk+1  ƒNếu thử tất cả các khả năng xk∈ Ak mà không có khả năng nào được chấp nhận thì quay lui lại bước trước để xác định lại xk-1 GV Phi Loan - BM HTTT - Khoa CNTT - HUI 7 Ý tưởng phương pháp  Tại mỗi bước đi qua, khi xác định xk, cần phải ghi nhớ những khả năng nào đã được thử để tránh trùng lặp  Có thể sử dụng một stack để ghi nhớ những khả năng đã được thử ⇒ dùng kỹ thuật đệ qui để thiết kế thuật toán GV Phi Loan - BM HTTT - Khoa CNTT - HUI 8 Lược đồ giải thuật  Back_Tracking(k) // xác định xk, k nguyên 1 For j ←1 to nk // chọn khả năng j, trong nk khả năng 2 3 4 5 6 do if accepting j then if k = n then < recording 1 solution > else Back_Tracking(k+1) GV Phi Loan - BM HTTT - Khoa CNTT - HUI 9 Nhận xét về lược đồ giải thuật  Cần chỉ rõ tập khả năng {1, …, nk} và kiểm tra  Nói chung, ngoài sự phụ thuộc vào j, các xi còn phụ thuộc vào việc chọn các thành phần ở các bước trước  Vì vậy, có thể phải ghi nhớ trạng thái của quá trình tìm kiếm sau khi xác định xk theo j và trả lại trạng thái cũ sau lời gọi Back_Tracking(k+1)  Các trạng thái được ghi nhận bởi biến toàn cục GV Phi Loan - BM HTTT - Khoa CNTT - HUI 10