tailieunhanh - Đề xuất giải thuật BEES giải bài toán Clique lớn nhất

Bài toán clique lớn nhất (Maximum clique problem) là bài toán tối ưu tổ hợp được ứng dụng trong nhiều lĩnh vực như mạng xã hội, tin sinh học, tài chính, lập lịch và đã được chứng minh là bài toán thuộc lớp NP-Hard. Nghiên cứu này đề xuất giải thuật bầy ong giải bài toán clique lớn nhất dựa trên hệ thống dữ liệu thực nghiệm chuẩn DIMACS gồm 37 bộ dữ liệu thực nghiệm. | TRƯỜNG ĐẠI HỌC SÀI GÒN SAIGON UNIVERSITY TẠP CHÍ KHOA HỌC SCIENTIFIC JOURNAL ĐẠI HỌC SÀI GÒN OF SAIGON UNIVERSITY Số 77 06 2021 No. 77 06 2021 Email tcdhsg@ Website http ĐỀ XUẤT GIẢI THUẬT BEES GIẢI BÀI TOÁN CLIQUE LỚN NHẤT Solving maximum Clique problem using Bees algorithm ThS. Đỗ Minh Vũ 1 ThS. Mai Trương Hoàng Thông 2 Trường THPT chuyên Trần Hưng Đạo Bình Thuận 1 2 Công ty Hệ thống thông tin FPT TÓM TẮT Bài toán clique lớn nhất Maximum clique problem là bài toán tối ưu tổ hợp được ứng dụng trong nhiều lĩnh vực như mạng xã hội tin sinh học tài chính lập lịch. và đã được chứng minh là bài toán thuộc lớp NP-Hard. Nghiên cứu này đề xuất giải thuật bầy ong giải bài toán clique lớn nhất dựa trên hệ thống dữ liệu thực nghiệm chuẩn DIMACS gồm 37 bộ dữ liệu thực nghiệm. Kết quả thực nghiệm của giải thuật đề xuất cho kết quả đạt từ 72 đến 100 so với lời giải kỷ lục hiện nay. Từ khóa bài toán Clique lớn nhất Giải thuật bầy ong Giải thuật Heuristic Giải thuật Metaheuristic NP-Hard ABSTRACT The Maximum clique problem is the combination optimization problem with practical application in many fields such as social networking bioinformatics finance scheduling. and has been proved as a NP-Hard problem. This paper proposes the Bees algorithm to solve the maximum clique problem on 37 datasets standard of datatable DIMACS. The experimental results show that the proposed algorithm achieves the results from to compared to the current optimal results. Keywords maximum Clique problem Bees Algorithm Heuristic Algorithm Metaheuristic Algorithm NP-Hard 1. Giới thiệu Định nghĩa 2. Clique lớn nhất . Một số định nghĩa C được gọi là một clique lớn nhất của Mục này trình bày một số định nghĩa đồ thị G nếu C là một clique và C có số về bài toán clique lớn nhất đỉnh lớn nhất trong số các clique của G. Số Định nghĩa 1. Clique lượng đỉnh của clique lớn nhất trong đồ thị Cho đồ thị vô hướng liên thông G ký hiệu là G và gọi là chỉ số clique G V E trong đó V là