Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 Th.s Đỗ 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 CẬN.- 3 - 1.1. Thuật toán nhánh cận.- 3 - 1.2. Một số ví dụ cụ thể áp dụng thuật toán nhánh cận.- 5 - Chương 2 XÂY DỰNG KHUNG THUẬT TOÁN NHÁNH CẬN.- 7 - Nhóm các lớp yêu cầu.- 8 - Nhóm các lớp cung cấp.- 10 - 2.1. Xây dựng khung nhánh cận.- 12 - 2.1.1. Cấu trúc dữ liệu.- 12 - 2.1.2. Thuật toán.- 12 - 2.2. Xây dựng khung nhánh cận tuần tự.- 15 - 2.3. Xây dựng khung nhánh cận song song.- 16 - 2.3.1. Lược đồ song song dữ liệu tập trung.- 19 - 2.3.2. Lược đồ song song dữ liệu phân tán.- 22 - 2.4. Công cụ phát triển hệ thống.- 25 - 2.5. Lựa chọn mô hình phát triển hệ thống.- 25 - Chương 3 SỬ DỤNG THUẬT TOÁN NHÁNH CẬN ĐỂ GIẢI QUYẾT BÀI TOÁN TSP.- 27 - Bài toán TSP Bài toán người du lịch .- 27 - 3.1. Giới thiệu bài toán.- 27 - 3.2. Định nghĩa bài toán.- 27 - 3.3. Sử dụng thuật toán nhánh cận để giải bài toán TSP.- 28 - 3.4. Chương trình thực thi.- 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. 1.1. 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 .
