intTypePromotion=1

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

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PDF | Số trang:41

0
53
lượt xem
1
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Chương 8: Backtracking algorithm

  1. Backtracking algorithm GV Phi Loan - BM HTTT - Khoa CNTT - HUI 1
  2. 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
  3. 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
  4. 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
  5. Ứ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
  6. Ý 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
  7. Ý 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
  8. Ý 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
  9. 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 do if accepting j 3 then 4 if k = n 5 then < recording 1 solution > 6 else Back_Tracking(k+1) GV Phi Loan - BM HTTT - Khoa CNTT - HUI 9
  10. 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
  11. GV Phi Loan - BM HTTT - Khoa CNTT - HUI 11
  12. Đặc điểm của giải thuật backtracking “Các bước trong giải thuật đều hướng về lời giả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át hiệ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 12
  13. Ví 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 13
  14. Ví dụ GV Phi Loan - BM HTTT - Khoa CNTT - HUI 14
  15. Knight’s Tour Problem GV Phi Loan - BM HTTT - Khoa CNTT - HUI 15
  16. Knight’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 GV Phi Loan - BM HTTT - Khoa CNTT - HUI 16
  17. Ý tưởng giải thuật tìm bước đi kế tiếp procedure try next move; begin initialize selection of moves; repeat select next candidate from list of next moves; if acceptable then begin record move; if board not full then begin try next move; if not successful then erase previous recording end end until (move was successful)  (no more candidates) end GV Phi Loan - BM HTTT - Khoa CNTT - HUI 17
  18. Cách biểu diễn dữ liệu • Biểu diễn bàn cờ bằng ma trận h. type index = 1..n ; var h: array[index, index] of integer; • Biểu diễn trạng thái các ô cờ h[x, y] = 0: ô chưa hề được viếng h[x, y] = i: ô đã được viếng tại bước chuyển thứ i (1 i n2) • Điều kiện “board not full”  “i < n2”. • Gọi u, v: tọa độ của ô sẽ chuyển đến. • Điều kiện “acceptable” có thể được diễn tả bằng (1un)  (1vn)  (h[u,v]=0) GV Phi Loan - BM HTTT - Khoa CNTT - HUI 18
  19. Tinh chỉnh giải thuật procedure try(i: integer; x,y : index; var q: boolean); var u, v: integer; q1 : boolean; begin initialize selection for moves; repeat let u, v be the coordinates of the next move ; if (1un)  (1vn)  (h[u,v]=0) then begin h[u,v]:=i; if i < sqr(n) then begin try(i + 1, u, v, q1); if  q1 then h[u,v]:=0 end else q1:= true end until q1  (no more candidates); q:=q1 end GV Phi Loan - BM HTTT - Khoa CNTT - HUI 19
  20. Cho tọa độ của ô hiện hành , có 8 khả năng để chọn ô kế tiếp để đi tới. Chúng được đánh số từ 1 đến 8 như sau: 3 2 4 1  5 8 6 7 GV Phi Loan - BM HTTT - Khoa CNTT - HUI 20
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2