Đề 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: C96B NỘ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ẬN Biể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ẢI Nế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 ............. B1 Bắt đầu C1 .............. ĐICH A B2 ......... ............. C2 C3 ...............