Đang chuẩn bị liên kết để tải về tài liệu:
Cải tiến một số thuật toán heuristic giải bài toán clique lớn nhất

Bài viết trình bày việc cải tiến hai thuật toán dạng heuristic giải bài toán clique lớn nhất; Các thuật toán cải tiến của chúng tôi dựa trên hai thuật toán heuristic hiệu quả hiện biết. Đã cài đặt và thực nghiệm các thuật toán này trên 78 bộ dữ liệu trong hai hệ thống dữ liệu thực nghiệm chuẩn DIMACS và BHOSLIB. | Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR Huế ngày 07-08 6 2019 DOI 10.15625 vap.2019.0009 CẢI TIẾN MỘT SỐ THUẬT TOÁN HEURISTIC GIẢI BÀI TOÁN CLIQUE LỚN NHẤT Phan Tấn Quốc1 Huỳnh Thị Châu Ái2 1 Khoa Công nghệ thông tin Trường Đại học Sài Gòn 2 Khoa Kỹ thuật công nghệ Trường Đại học Văn Hiến quocpt@sgu.edu.vn aihtc@vhu.edu.vn TÓM TẮT Clique lớn nhất maximum clique problem là bài toán tối ưu tổ hợp có nhiều ứng dụng trong khoa học và kỹ thuật như mạng xã hội máy học mã hóa thị giác máy tính mạng viễn thông lập lịch thu hồi thông tin tin sinh học tài chính hóa học clique lớn nhất là bài toán thuộc lớp NP-hard. Hiện có nhiều hướng tiếp cận giải bài toán clique lớn nhất như các thuật toán tìm lời giải chính xác các thuật toán heuristic các thuật toán metaheuristic . Trong bài báo này chúng tôi cải tiến hai thuật toán dạng heuristic giải bài toán clique lớn nhất các thuật toán cải tiến của chúng tôi dựa trên hai thuật toán heuristic hiệu quả hiện biết. Chúng tôi đã cài đặt và thực nghiệm các thuật toán này trên 78 bộ dữ liệu trong hai hệ thống dữ liệu thực nghiệm chuẩn DIMACS và BHOSLIB. Kết quả thực nghiệm cho thấy rằng các thuật toán cải tiến của chúng tôi cho chất lượng lời giải phần lớn tốt hơn so với các thuật toán gốc. Các thuật toán cải tiến này và kết quả thực nghiệm tương ứng là thông tin hữu ích cho những nghiên cứu tiếp theo về bài toán clique lớn nhất. Từ khóa Maximum clique problem community detection in social networks heuristic algorithm metaheuristic algorithm NP-hard problem. I. GIỚI THIỆU A. Một số định nghĩa Mục này trình bày một số định nghĩa cơ sở cho bài toán clique lớn nhất 2 . Định nghĩa 1. Clique Cho đồ thị vô hướng liên thông G V E trong đó V là tập đỉnh E là tập cạnh. Tập đỉnh C V được gọi là một clique của đồ thị G nếu mọi cặp đỉnh u v trong C đều là cạnh thuộc tập E. Số lượng đỉnh hay còn gọi là kích thước của một clique C ký hiệu là C . Nếu clique C chứa đỉnh v thì C deg v 1. Định .