Luận Văn Thuật toán nhánh và cân cài đặt trên cây nhị phân

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

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



​