Kỹ thuật quay lui (backtracking) như tên gọi của nó, là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua. Tại mỗi bước phân tích chúng ra chưa giải quyết được vấn đề do còn thiếu cứ liệu nên cứ phải phân tích cho tới các điểm dừng, nơi chúng ta xác định được lời giải của chúng hoặc là xác định được là không thể (hoặc không nên) tiếp tục theo hướng này. Từ các điểm dừng này chúng ta quay ngược trở lại theo con đường mà chúng ta đã đi qua để giải quyết các vấn đề còn tồn đọng và cuối cùng ta sẽ giải quyết được vấn đề ban đầu.
Ở đây chúng ta sẽ xét 3 kỹ thuật quay lui: "vét cạn" là kỹ thuật phải đi tới tất cả các điểm dừng rồi mới quay lui. "Cắt tỉa Alpha-Beta" và "Nhánh-Cận" là hai kỹ thuật cho phép chúng ta không cần thiết phải đi tới số suy luận để có thể quay lui sớm. Các kỹ thuật này sẽ được trình bày thông qua một số bài toán cụ thể sau.
21 trang |
Chia sẻ: diunt88 | Lượt xem: 2781 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Thiết kế và Phân tích thuật toán_Chương 6: Kỹ thuật Quay lui - Nhánh cận, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 6: 1. Ví dụ: Cây biểu diễn biểu thức (5+3)*(7-2) Qui tắc biểu diễn biểu thức toán học trên cây như sau: Mỗi nút lá có nhãn biểu diễn cho một toán hạng. Mỗi nút trung gian biểu diễn một toán tử. Trị của 1 nút lá chính là trị toán hạng, của nút trong là kết quả thực hiện toán tử trên 2 trị chứa trong 2 nút con. Trị của nút gốc là trị của biểu thức. Như vậy, để định trị biểu thức, xuất phát từ gốc ta định trị 2 nút con và thực hiện toán tử ở gốc. Việc định trị mỗi nút con thực hiện tương tự, … quá trình tiếp tục cho đến khi gặp các nút lá chứa toán tử thì quay lui để định trị các nút mức trên, … cuối cùng định trị nút gốc. Đó chính là kỹ thuật quay lui vét cạn. Trong ví dụ trên, tính trị cho nút gốc * dẫn đến định trị cho nút + và nút -. Định trị cho nút + dựa trên 2 nút lá có trị 5 và 3 được kết quả 8. Định trị nút – dựa trên 2 nút lá có trị 7 và 2 được kết quả 5. Quay lui định trị cho nút gốc * được 40. 2.
