ĐỀ TÀI: THUẬT TOÁN NHÁNH VÀ CÂN CÀI ĐẶT TRÊN CÂY NHỊ PHÂN.

TRƯỜNG ĐẠI HỌC ĐÔNG ĐÔ KHOA CÔNG NGHỆ THÔNG TIN.LUÂN VĂN TỐT NGHIỆP..ĐỀ TÀI: THUẬT TOÁN NHÁNH VÀ CÂN CÀI ĐẶT TRÊN CÂY NHỊ PHÂN.GIÁO VIÊN HƯỚNG DẪN: TS NGUYỄN ĐÌNH HÓA GIÁO VIÊN PHẢN BIỆN
Nội dung trích xuất từ tài liệu:
.ĐỀ TÀI: THUẬT TOÁN NHÁNH VÀ CÂN CÀI ĐẶT TRÊN CÂY NHỊ PHÂN. TRƯỜNG ĐẠI HỌC ĐÔNG ĐÔ KHOA CÔNG NGHỆ THÔNG TIN LUÂN VĂN TỐT NGHIỆPĐỀ TÀI: THUẬT TOÁN NHÁNH VÀ CÂN CÀI ĐẶT TRÊN CÂY NHỊ PHÂN GIÁO VIÊN HƯỚNG DẪN: TS NGUYỄN ĐÌNH HÓA GIÁO VIÊN PHẢN BIỆN: TS ĐỖ TRUNG TUẤN SINH VIÊN THỰC HIỆN: TRÂN TRIỆU HÙNG LỚP: C96BNỘI DUNG CHÍNH CỦA LUÂN VĂN  THỂ HIÊN THUẬT GIẢI TÌM KIẾM NHÁNH VÀ CẬN  THIẾT KẾ VÀ CÀI ĐẶT CÂY NHỊ PHÂN.  CÀI ĐẶT THUẬT GIẢI TÌM KIẾM NHÁNH VÀ CẬN TRÊN CÂY NHỊ PHÂN PHƯƠNG PHÁP TÌM KIẾM NHÁNH VÀ CẬNBiểu diễn bài toán trong không gian trạng thái:Một bài toán dược xác định bởi 4 yếu tố Trạng thái ban đầu. Các toán tử chuyển trạng thái : Từ 1 trạng thái đã cho đến 1 trạng thái kế tiếp. Trạng thái đích. Chi phí kèm theo mỗi toán tử chuyển trạng thái nếu có.Mọi cấu trúc các đối tượng đều có thể dung để mô tả các trạng tháI: Các sâu ký hiệu, véctơ, mảng 1 chiều, 2 chiều, cây , danh sách… PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢINếu biểu diễn bài toán thành đồ thị trong trong không gian trạng thái -> Tìm kiếm lời giải là đương đi trên đồ thị. Thuật giải tổng quát: - Xuất phát từ nút trạng thái ban đầu. - Lặp: + Nếu không còn nút để triển khai tiếp ->Thất bại(vô nghiệm ). + TráI lại: Chon nút để trirnr khai tiếp theo 1 quy tắc bằng 1 chiến lược nào đó + Kiểm tra trạngt háI đích chưa: - Đúng -> lời giải. - Sai : Khai triển nút và thêm nút mới vào cây.- Hết lặp TÌM KIẾM THEO CHIỀU RỘNG• Tìm kiếm lời giải trên tất cả các nút của 1 mức trong không gian bài toán trước khi chuyển sang các nút ở các mức tiếp theo Bắt đầu A B1 B2 C2 C3 C1 .............. ............. ............. ......... ĐICH ...............