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.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Chương 8: Backtracking algorithm
- 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 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
- 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
- GV 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ờ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
- 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
- Ví dụ
GV Phi Loan - BM HTTT - Khoa CNTT - HUI 14
- Knight’s Tour Problem
GV Phi Loan - BM HTTT - Khoa CNTT - HUI 15
- 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
- Ý 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
- 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
(1un) (1vn) (h[u,v]=0)
GV Phi Loan - BM HTTT - Khoa CNTT - HUI 18
- 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 (1un) (1vn) (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
- 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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
