- TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài: Thuật toán metaheuristic giải bài toán tập phủ đỉnh. - Nguyễn Đức Nghĩa Nội dung tóm tắt: a) Lý do chọn đề tài: Bài toán tập phủ đỉnh nhỏ nhất trên đồ thị là bài toán NP-khó trong nhóm các bài toán về đồ thị. - Bài toán tập phủ đỉnh nhỏ nhất trên đồ thị được ứng dụng trong nhiều lĩnh vực thực tế như việc đạt trạm quan sát, ứng dụng trong việc xét nghiệm ung thư cổ bằng cách kiểm tra màng tế bào. - Do tầm quan trọng của bài toán, rất nhiều hướng tiếp cận để giải xấp xỉ bài toán đã được đề xuất với mục đích đưa ra lời giải xấp xỉ tốt nhất với thời gian chấp nhận được. - Các cách tiếp cận truyền thống thường sử dụng một thuật toán như giải thuật di truyền, giải thuật đàn kiến hay giải thuật tìm kiếm Tabu và đã thu được kết quả nhất định, trong luận văn này em xin đi theo hướng lai ghép các heuristic để tạo thành metaheuristic giải bài toán tập phủ đỉnh nhỏ nhất. - b) Mục đích nghiên cứu của luận văn, đối tượng, phạm vi nghiên cứu: Với mục đích tạo ra thuật toán metaheuristic, kết hợp các kỹ thuật và thuật toán khác nhau để xây dựng một thuật toán mới hiệu quả hơn( về thời gian, kết quả), vì vậy luận văn tập trung vào các nội dung chính sau. - Phát biểu bài toán Tập phủ đỉnh nhỏ nhất và các ứng dụng của bài toán. - Nghiên cứu các hướng tiếp cận giải bài toán Tập phủ đỉnh nhỏ nhất trên đồ thị tổng quát như giải thuật di truyền, giải thuật của Ashay Dharwadker, giải thuật tìm kiếm Tabu. - Lai ghép để tạo ra thuật toán metaheuristic. - Cài đặt thuật toán tìm kiếm Tabu, thuật toán di truyền, giải thuật của Ashay Dharwadker và metaheuristic cùng giải bài toán Tập phủ đỉnh nhỏ nhất, đưa ra kết quả thực nghiệm để so sánh và đánh giá. - c) Các nội dung chính của luận văn và đóng góp của tác giả: Chương 1: Bài toán tập phủ đỉnh nhỏ nhất trên đồ thị. - Chương này được chia làm hai phần : phần 1 trình bày các kiến thức cơ sở về thuật toán và bài toán tính toán, về đồ thị và lớp bài toán NP-đầy đủ với mục đích làm nền tảng lý thuyết cho các chương tiếp theo. - Phần 2 phát biểu bài toán và các ứng dụng thực tế. - Chương 2: Các cách tiếp cận bài toán. - Trình bày về các trường hợp giải tốt cũng như một số phương pháp giải xấp xỉ và các thuật toán độc lập giải bài toán. - Chương 3: Metaheuristic giải bài toán Tập phủ đỉnh nhỏ nhất. - Trình bày về thuật Metaheuristic – để giải bài toán. - Chương4: Cài đặt chương trình và kết quả thực nghiệm. - Trình bày việc cài đặt chương trình, chạy thử nghiệm và các kết quả thu được. - Đưa ra các nhận xét đánh giá hiệu quả của thuật toán khi chạy một số bộ test. - -Tìm hiểu các thuật toán heuristic giải bài toán và cài đặt các thuật toán heuristic đã tìm hiểu. - Tổng hợp các kỹ thuật của các thuật toán heuristic. - Xây dựng metaheuristic và cài đặt metaheuristic. - Chạy thực nghiệm chương trình, so sánh đánh giá kết quả. - Tìm hiểu, xây dựng và cài đặt các thuật toán heuristic giải bài toán. - Phân tích kỹ thuật mà các thuật toán heuristic sử dụng. - Xây dựng và cài đặt metaheuristic . - 4.Cài đặt chương trình, chạy thực nghiệm và so sánh đánh giá kết quả. - Các kết quả chính đạt được trong đề tài: 1. - Tìm hiểu, xây dựng, cài đặt các thuật toán heuristic giải bài toán tập phủ đỉnh. - Xây dựng metaheuristic, thực nghiệm chương trình, so sánh đánh giá kết quả
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt