ZixDoc gửi tặng quý thầy cô và các em học sinh Tài liệu bồi dưỡng HSG Tin học 11 chuyên sâu với định dạng word hoàn toàn miễn phí. Tài liệu gồm có 28 trang, gồm lí thuyết và bài tập kĩ năng. Kính mời các em và quý thầy cô tham khảo mùa thi sắp tới.
Trích dẫn Tài liệu bồi dưỡng HSG Tin học 11:
+ Nếu tìm 1 nghiệm tốt nhất ( theo điều kiện ) thì mỗi khi tìm được 1 nghiệm , ta so sánh với nghiệm tốt nhất đã tìm được cho đến lúc này( gọi là nghiệm tối ưu ) . Nếu nghiệm vừa tìm được tốt hơn nghiệm tối ưu thì gán lại nghiệm tối ưu là nghiệm mới
Quá trình tiếp diễn cho đến khi duyệt hết các nghiệm của bài toán ta sẽ được nghiệm tối ưu của bài toán .
Tóm lại thuật toán "duyệt trên cơ sở tìm kiếm và quay lui " - Thuật toán BackTracking - có chứa các nội dung sau :
+ Vét cạn mọi nghiệm bằng tìm kiếm tiến dần về đích đồng thời biết quay lui khi không thể tiến
+ Có thể đặt các "mắt lọc" để việc tìm kiếm nhanh chóng hơn : hoặc loại bỏ hoặc chỉ chọn một số hướng .
+ Có thể so sánh các nghiệm để có nghiệm tối ưu
+ Tuỳ theo yêu cầu , có thể chỉ tìm 1 nghiệm , cũng có thể tìm mọi nghiệm
Do thuật toán BackTracking xây dựng trên cơ sở tìm kiếm dần ,kết quả sau hình thành từ kết quả trước, nên có thể dùng các hàm, thủ tục đệ qui để thực hiện thuật toán Cụ thể có 3 dạng dàn bài thường gặp sau đây :
Trích dẫn Tài liệu bồi dưỡng HSG Tin học 11:
+ Nếu tìm 1 nghiệm tốt nhất ( theo điều kiện ) thì mỗi khi tìm được 1 nghiệm , ta so sánh với nghiệm tốt nhất đã tìm được cho đến lúc này( gọi là nghiệm tối ưu ) . Nếu nghiệm vừa tìm được tốt hơn nghiệm tối ưu thì gán lại nghiệm tối ưu là nghiệm mới
Quá trình tiếp diễn cho đến khi duyệt hết các nghiệm của bài toán ta sẽ được nghiệm tối ưu của bài toán .
Tóm lại thuật toán "duyệt trên cơ sở tìm kiếm và quay lui " - Thuật toán BackTracking - có chứa các nội dung sau :
+ Vét cạn mọi nghiệm bằng tìm kiếm tiến dần về đích đồng thời biết quay lui khi không thể tiến
+ Có thể đặt các "mắt lọc" để việc tìm kiếm nhanh chóng hơn : hoặc loại bỏ hoặc chỉ chọn một số hướng .
+ Có thể so sánh các nghiệm để có nghiệm tối ưu
+ Tuỳ theo yêu cầu , có thể chỉ tìm 1 nghiệm , cũng có thể tìm mọi nghiệm
Do thuật toán BackTracking xây dựng trên cơ sở tìm kiếm dần ,kết quả sau hình thành từ kết quả trước, nên có thể dùng các hàm, thủ tục đệ qui để thực hiện thuật toán Cụ thể có 3 dạng dàn bài thường gặp sau đây :