ĐỀ XUẤT THUẬT TOÁN LOCAL SEARCH GIẢI BÀI TOÁN MAX CLIQUE

Abstract

Clique lớn nhất (Max Clique Problem - MCP) là một bài toán tối ưu tổ hợp có nhiều ứng dụng quan trọng trong các lĩnh vực mạng xã hội, thị giác máy tính, nhận biết khuôn mẫu,… MCP là bài toán thuộc lớp NP-Hard và được nghiên cứu rộng rãi trong những năm gần đây. Trong bài báo này, chúng tôi đề xuất một thuật toán Local Search để giải bài toán MCP; thuật toán này được cải tiến từ thuật toán k – opt Local Search (KLS) của nhóm tác giả Kengo Katayama, Akihiro Hamamoto, Hiroyuki Narihisa. Chúng tôi đã so sánh chất lượng của thuật toán cải tiến này với thuật toán k – opt Local Search gốc trên 34 bộ dữ liệu trong hệ thống dữ liệu thực nghiệm chuẩn DIMACS.