Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Ta sẽ thực hiện việc đánh giá theo từng bước, nếu không có khả năng tìm thấy kết quả tốt hơn thì sẽ cắt nhánh đó, không thực hiện tìm tiếp mà chuyển ngay sang nhánh khác. Khi đó, chỉ ghi nhận các kết quả tốt hơn lúc ban đầu. Nghiệm của bài toán sẽ tốt dần lên do khi tìm ra kết quả tốt hơn ta sẽ cập nhật lại giá trị hiện thời của bài toán | TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO KHOA HỌC Chuyên đề Xử lí song song Đề tài Thuật toán nhánh cận trên môi trường song song Giáo viên hướng dẫn Đỗ Trung Kiên Sinh viên thực hiện Nguyền Thị Bích Nhật Phạm Thị Thuỳ Trần Thị Thanh Tâm Bùi Thu Hường Trần Thị Hoa Nguyễn Chí Công Hà Nội 15 04 2008 - 1 - MỤC LỤC Chương 1 TỔNG QUAN VỀ THUẬT TOÁN NHÁNH 3 - . Thuật toán nhánh 3 - . Một số ví dụ cụ thể áp dụng thuật toán nhánh 5 - Chương 2 XÂY DỰNG KHUNG THUẬT TOÁN NHÁNH 7 - Nhóm các lớp yêu 8 - Nhóm các lớp cung 10 - . Xây dựng khung nhánh 12 - . Cấu trúc dữ 12 - . Thuật 12 - . Xây dựng khung nhánh cận tuần 15 - . Xây dựng khung nhánh cận song 16 - . Lược đồ song song dữ liệu tập 19 - . Lược đồ song song dữ liệu phân 22 - . Công cụ phát triển hệ 25 - . Lựa chọn mô hình phát triển hệ 25 - Chương 3 SỬ DỤNG THUẬT TOÁN NHÁNH CẬN ĐỂ GIẢI QUYẾT BÀI TOÁN 27 - Bài toán TSP Bài toán người du lịch .- 27 - . Giới thiệu bài 27 - . Định nghĩa bài 27 - . Sử dụng thuật toán nhánh cận để giải bài toán 28 - . Chương trình thực 32 - - 2 - Chương 1 TỔNG QUAN VỀ THUẬT TOÁN NHÁNH CẬN Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Ta sẽ thực hiện việc đánh giá theo từng bước nếu không có khả năng tìm thấy kết quả tốt hơn thì sẽ cắt nhánh đó không thực hiện tìm tiếp mà chuyển ngay sang nhánh khác. Khi đó chỉ ghi nhận các kết quả tốt hơn lúc ban đầu. Nghiệm của bài toán sẽ tốt dần lên do khi tìm ra kết quả tốt hơn ta sẽ cập nhật lại giá trị hiện thời của bài toán. . Thuật toán nhánh cận Một trong những bài toán đặt ra trong thực tế là tìm một nghiệm của bài toán thỏa mãn một số điều kiện nào đó và nghiệm đó là tốt nhất theo một tiêu chí cụ thể nghiên cứu lời giải các bài toán tối ưu thuộc về lĩnh vực quy hoạch toán học. mô hình được sử dụng để tìm .
