1
PH NG PHÁP THI T K ƯƠ Ế Ế
THU T TOÁNẬ
– QUAY LUI –
Ch ng 4ươ
2
N i dungộ
§Gi i thi uớ ệ
§Ph ng pháp ươ
§S đ cài đ tơ ồ ặ
§Các ví dụ
§u đi m và khuy t đi mƯ ể ế ể
3
Hình nhả
…
4
Gi i thi uớ ệ
§Đ nh nghĩa [Quay lui – Backtracking]:ị
•Quay lui là m t ph ng pháp thi t k thu t ộ ươ ế ế ậ
toán đ tìm nghi m c a bài toán b ng cách ể ệ ủ ằ
xét t t c các ph ng ánấ ả ươ .
•M t ph ng án g m nhi u thành ph n, và ộ ươ ồ ề ầ
ph ng pháp quay lui s xây d ng t ng thành ươ ẽ ự ừ
ph n trong m i b cầ ỗ ướ .
•Trong quá trình xây d ng thành ph n th i ự ầ ứ
(tìm nghi m cho thành ph n th i), n u không ệ ầ ứ ế
th xây d ng đ c thì quay l i ch n nghi m ể ự ượ ạ ọ ệ
khác cho thành ph n th (i-1)ầ ứ
5
Bài toán
§Phát bi u bài toán: Gi s nghi m c a bài ể ả ử ệ ủ
toán c n tìm có d ng X=(x1, x2, …, xk, …), ầ ạ
trong đó
•xi là 1 thành ph n nghi m c a bài toánầ ệ ủ
•xi có m t mi n giá tr Di nào đó (xi  Di).ộ ề ị
•S l ng thành ph n xi có th xác đ nh hay ố ượ ầ ể ị
không xác đ nhị
•Bài toán có nh ng ràng bu c là Fữ ộ
§Yêu c u: Hãy xây d ng 1 nghi m hay t t c ầ ự ệ ấ ả
các nghi m c a bài toán th a đi u ki n Fệ ủ ỏ ề ệ