Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 13: Kĩ thuật duyệt quay lui

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!

KHOA HỌC MÁY TÍNH

KHỞI ĐỘNG

[…] 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 bản phác thảo đầu tiên của một phương pháp giải bài toán đườ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 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?

BÀI 13: KĨ THUẬT

DUYỆT QUAY LUI

NỘI DUNG BÀI HỌC

1

Kĩ thuật duyệt quay lui

2

Mô hình tổng quát của thuật toán duyệt quay lui

3

Bài toán sinh xâu nhị phân

KĨ THUẬT DUYỆT QUAY LUI

1

Hoạt động 1

Tìm hiểu ý tưởng của thuật toán quay lui

Đọ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.

• 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.

Luôn tìm cách đi tiếp theo

Sơ đồ mã giả của thuật toán quy lui

GIẢI THÍCH

Hàm có chức năng tim bước đi tiếp theo xuất phát từ <vị trí> hiện thời.

Nếu vị trí hiện thời là đích thì thông báo tìm thấy nghiệm tại dòng 3 và dừng chương trình. Dòng 5 sẽ tìm tất cả các phương án có thể đi tiếp.

• Nếu tìm thấy một phương án đi khả thi tại dòng 6 thì thực hiện ngay bước đi này tại dòng 7 để cập nhật thông tin vào <vị trí> mới.
• Sau gọi đệ quy lại hàm gốc để đi tiếp tại dòng 9.

Nếu không thể đi tiếp (lệnh gọi đệ quy dòng 9 không thể thực hiện) thì quay lui tại dòng 10, xoá thông tin bước vừa đi để quay lại vòng lặp 5.

KẾT LUẬN

Ý tưởng của thuật toán quay lui là thiết lập một hàm (thủ tục) xuất phát từ một vị trí hiện thời để tìm kiếm các bước đi tiếp theo.

Đọc thông tin và trả lời các câu hỏi sau đây:

• Câu 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?
• Câu 2: Lệnh gọi hàm chính của chương trình trên là gì?
• Câu 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?

TRẢ LỜI CÂU HỎI

1

Có. Khi thực hiện xong vòng lặp tại dòng 5 thì hàm sẽ dừng. Có nghĩa là từ vị trí hiện thời sẽ không thể đi tiếp được nữa, cần “quay lui".

2

Lệnh gọi hàm chính là "Tìm bước đi tiếp theo.

3

Lệnh này đã có chính là dòng lệnh 2.

MÔ HÌNH TỔNG QUÁT CỦA THUẬT TOÁN DUYỆT QUAY LUI

2

Hoạt động 2

Tìm hiểu mô hình tổng quát của kĩ thuật duyệt quay lui

Quan sát, thực hiện và thảo luận các bước thiết kế mô hình tổng quát của kĩ thuật duyệt quay lui.

Mô hình tổng quát duyệt quay lui sử dụng đệ quy

Lệnh gọi hàm gốc

GIẢI THÍCH

Lưu ý: Vòng lặp for tại dòng 5 sẽ thực hiện duyệt theo thứ tự các phần tử đang có của S Như vậy, yêu cầu các tập hợp D, phải được sắp thứ tự trước.

KẾT LUẬN

Đọc thông tin và trả lời các câu hỏi sau đây:

• Câu 1: Trạng thái "quay lui" của thuật toán trên nằm ở đâu?
• Câu 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?

TRẢ LỜI CÂU HỎI

1

Trạng thái "quay lui” của thuật toán nằm ở sau dòng lệnh 6, khi kết thúc Backtracking() thì cần “quay lui” để quay lại vòng lặp tiếp theo của lệnh for, tại dòng 5.

2

Có. Cần bổ sung một biến tổng thể, ví dụ count, biến này sẽ được tự động tăng lên 1 đơn vị sau lệnh 3, bên trong lệnh if.

BÀI TOÁN SINH XÂU NHỊ PHÂN

3

Hoạt động 3

Thiết kế chương trình sinh tất cả các dãy nhị phân

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.

Để 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.

1

Viết hàm để sinh dãy nhị phân độ dài n:

2

Gọi hàm generate_binary_sequence với độ dài của dãy nhị phân cần sinh:

Kết quả

Chương trình 1

Lời gọi hàm chính

Chương trình 2

Lời gọi hàm chính

KẾT LUẬN

--------------- Còn tiếp ---------------