Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 4: Kỹ thuật quay lui (Backtracking)
@Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
1
Bài 4. Kỹ thuật quay lui
Backtracking
Nội dung:
4.1. Khái niệm về kỹ thuật quay lui (6)
4.2. Bài toán 8 con hậu -Eight Queen Problem (7)
4.3. Bài toán mã đi tuần -Knight Tour Problem (5)
4.4. Bài toán chiếc ba lô -Knapsack Problem (6)
Tham khảo:
1. Lecture 11 –Backtracking.htm
@Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
2
4.1. Khái niệm kỹ thuật quay lui (1/6)
Kỹ thuật quay lui là quá trình phân tích từ trên xuống
trong không gian tìm kiếm.
Trong trường hợp tổng quát, giả sử lời giải là một
vector:
a = (a[1], a[2], …, a[n])
trong đó, mỗi phần tử a[i] chọn từ tập hữu hạn S[i]
(các khả năng của a[i]).
@Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
3
4.1. Khái niệm kỹ thuật quay lui (2/6)
Ta s ẽ giải quyết bài toán với kích thước k, có dạng:
a = (a[1], a[2], …, a[k])
và cố gắng mở rộng bằng việc thêm phần tử tiếp theo
vào trong vector.
Sau khi thêm phần tử, kiểm tra xem có thể thực hiện
tiếp được không.
Nếu vẫn có khả năng mở rộng, tiếp tục thực hiện;
Nếu không, xóa phần tử a[k] và làm lại bài toán từ tập
S[k].
@Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
4
4.1. Khái niệm kỹ thuật quay lui (3/6)
Gọi S[1], tập các khả năng của a tại bước đầu tiên.
k = 1
While k > 0 do
While S[k]<>[] do (*advance*)
a[k] = an element in S[k]
If (a[1], a[2],…, a[k]) is solution, print it!
k = k + 1
Tính S[k], tập khả năng của a tại bước k.
k = k - 1 (*backtrack*)
@Copyright PhD. Ngo Huu Phuc, Le Quy Don Technical University
5