Bài giảng Chương 8: Backtracking algorithm

Bài giảng Chương 8: Backtracking algorithm trình bày những nội dung về 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. Mời các bạn tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 8: Backtracking algorithmBacktracking algorithm GV Phi Loan - BM HTTT - Khoa CNTT - HUI 1Nộ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 2Backtracking 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 3Backtracking 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 8Lược đồ giải thuật Back_Tracking(k) // xác định xk, k nguyên1 For j ←1 to nk // chọn khả năng j, trong nk khả năng2 do if accepting j3 then 4 if k = n5 then < recording 1 solution >6 else Back_Tracking(k+1) GV Phi Loan - BM HTTT - Khoa CNTT - HUI 9Nhậ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 10GV Phi Loan - BM HTTT - Khoa CNTT - HUI 11Đặc điểm của giải thuật backtracking “Các bước trong giải thuật đều hướng về lờigiải đầy đủ và ghi lại thông tin mỗi bước màsau đó nó có thể bị tháo gỡ và xóa đi khi pháthiện rằng bước này đã không dẫn đến lời giảiđầy đủ, tức là một bước đi dẫn đến “tình thếbế tắc”(dead-end). (Hành vi này được gọi làquay lui -bactracking.) GV Phi Loan - BM HTTT - Khoa CNTT - HUI 12Ví dụ 1 Liệt kê các hoán vị của n phần tử từ tập A = {1, 2,..., n}Giải Biểu diễn mỗi hoán vị như là một vector p = (p1, p2, ..., pn) trong đó pi∈A và pi ≠ pjƒ pk nhận giá trị j =1, 2, .., n và khác với p1, p2,..., pk-1 Dùng biến logic bj (j =1,..., n) để ghi nhận j đã được gán cho một pi trong hoán vị Các bj được khởi tạo là true và được gán bằng false nếu đã sử dụng j GV Phi Loan - BM HTTT - Khoa CNTT - HUI 13Ví dụ GV Phi Loan - BM HTTT - Khoa CNTT - HUI 14Knight’s Tour Problem GV Phi Loan - BM HTTT - Khoa CNTT - HUI 15Knight’s Tour Problem Cho một bàn cờ n  n với n2 ô. Quân mã – di chuyển theo luật chơi cờ vua – được đặt trên bàn cờ tại ô đầu tiên có tọa độ x0, y0. Cần tìm một lộ trình gồm n2 –1 bước sao cho phủ toàn bộ bàn cờ (mỗi ô được viếng đúng một lần). Để tiến tới bài toán phủ n2 ô là xét bài toán:  Thực hiện bước đi kế tiếp, hay  Phát hiện rằng không kiếm được bước đi hợp lệ kế tiếp ...