Câu hỏi. Chúng ta đã biết từ bài học trước, thiết lập các thuật toán duyệt sẽ phụ thuộc hoàn toàn vào mô hình và cấu trúc của miền dữ liệu cần tìm kiếm. Từ lâu các nhà khoa học đã nhìn thấy rất nhiều bài toán khó không tìm được cách duyệt hữu hiệu, điển hình nhất là bài toán tìm đường đi trong mê cung.Bài toán tìm đường đi trong mê cung lần đầu tiên được đưa ra trong cuốn sách Récréations Mathématiques của tác giả Édouard Lucas năm 1882 tại Pháp. Cũng trong cuốn sách đó Lucas đã đưa ra phác thảo đầu tiên của một phương pháp giải bài toán tìm đường đi trong mê cung mà bây giờ chúng ta gọi là thuật toán duyệt quay lui, hay đơn giản là thuật toán quay lui (backtracking).
Trong trò chơi mê cung (xem hình) em cần tìm một đường đi xuất phát từ lối vào và ra khỏi mê cung tại lối ra. Em có đề xuất gì để giải bài toán này.
Hướng dẫn trả lời:
Để thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Cứ như vậy cho đến khi ra được khỏi mê cũng
Câu hỏi. Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung.
Hướng dẫn trả lời:
Ý tưởng của thuật toán duyệt quay lui là luôn tìm cách đi tiếp theo. Xuất phát từ vị trí gốc, thuật toán sẽ gọi hàm tìm bước đi tiếp theo. Nếu thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Thuật toán sẽ sử dụng kĩ thuật đệ quy khi gọi hàm cho bước đi tiếp theo.
Câu hỏi 1. Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm có dừng không?
Hướng dẫn trả lời:
Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm không dừng. Nếu đã đến đích thì thông báo tìm thấy thấy nghiệm tại dòng thứ 7, nếu chưa tìm thấy thì gọi đệ quy lại hàm gốc để đi tiếp tại dòng 10. Nếu không thể đi tiếp thì quay lui tại dòng 11, xóa dấu vết và quay lại vòng lặp 2.
Câu hỏi 2. Lệnh gọi hàm chính của chương trình trên là gì?
Hướng dẫn trả lời:
Câu hỏi 3. Nếu yêu cầu bổ sung thêm 1 lệnh “Nếu thấy <lối ra> thì thông báo và dừng chương trình” thì lệnh này sẽ đặt ở đâu trong chương trình trên?
Hướng dẫn trả lời:
Câu hỏi. Trạng thái "quay lui" của thuật toán trên nằm ở đâu?
Hướng dẫn trả lời:
Câu hỏi 2. Có cách nào đếm được tất cả các nghiệm từ thuật toán trên được không? Nếu có thì làm cách nào?
Hướng dẫn trả lời:
Câu hỏi. Cùng thực hiện, trao đổi, thảo luận thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui.
Hướng dẫn trả lời:
Để thiết kế chương trình sinh tất cả các dãy nhị phân độ dài n bằng kĩ thuật quay lui, ta có thể sử dụng đệ quy để thêm lần lượt các số 0 và 1 vào dãy nhị phân.
Bước 1: Viết hàm để sinh dãy nhị phân độ dài n:
Bước 2: Gọi hàm generate_binary_sequence với độ dài của dãy nhị phân cần sinh:
Thu được kết quả:
Câu hỏi 1. Trong chương trình 1, động tác “quay lui” nằm ở đâu?
Hướng dẫn trả lời:
Trong chương trình 1, động tác “quay lui” nằm ở dòng 7: genBinary (A, k+1)
Câu hỏi 2. Giải thích ý nghĩa của lệnh A.pop() tại dòng 8 của chương trình 2. Vì sao lệnh này không có trong chương trình 1?
Hướng dẫn trả lời:
- Lệnh A.pop() tại dòng 8 của chương trình 2 nhằm xóa phần tử đã nhập từ bước trước khi quay lui
- Vì ở chương trình 1, dãy A được thiết lập từ trước có đủ n phần tử nên tại bước này chỉ là lệnh gán giá trị và không cần dùng lệnh pop()
- Ở Chương trình 2, dãy A ban đầu là dãy rộng, do đó A được bổ sung dần. Sau khi kết thúc lệnh gọi đệ quy ở dòng 7 cần gọi lệnh pop() ở dòng 8.
Câu hỏi 1. Sửa các chương trình trên bổ sung thêm chức năng: sau khi in ra tất cả các xâu nhị phân thi thông báo tổng số nghiệm.
Hướng dẫn trả lời:
Câu hỏi 1. Viết chương trình sinh tất cả các xâu (hoặc dãy) bao gồm n kí tự dạng “R”, “G” và "B".
Hướng dẫn trả lời:
Có thể sử dụng thuật toán quay lui như sau
Ví dụ, nếu ta chạy đoạn code sau:
Kết quả sẽ là tất cả các xâu bao gồm 3 kí tự "R", "G" và "B":
Câu hỏi 2. Viết chương trình sinh xâu nhị phân thực sự có độ dài n, tức là kết quả in ra phải là các xâu kí tự chứ không phải là danh sách (list) như trong các chương trình trên.
Hướng dẫn trả lời:
Sử dụng phép cộng chuỗi để có kết quả là chuỗi xâu nhị phân cần tìm