THUẬT TOÁN GẦN ĐÚNG DỰA TRÊN PHƯƠNG THỨC KHỞI TẠO LỜI GIẢI NHIỀU LẦN GIẢI BÀI TOÁN MINIMUM S-CLUB COVER

Tóm tắt

Phủ đồ thị là một trong các chủ đề cơ bản trong nghiên cứu lý thuyết về khoa học máy tính. Đối với hướng nghiên cứu về phủ tập đỉnh của đồ thị, mô hình s-club được ứng dụng nhiều trong phân tích mạng xã hội, phân tích tương tác protein,... trong đó bài toán Minimum s-club cover nhận được sự quan tâm nghiên cứu trong thời gian gần đây. Mặc dù đã có thuật toán gần đúng để giải bài toán Minimum s-club cover, tuy nhiên, thuật toán này chỉ được áp dụng cho trường hợp s = 2 và do sử dụng chiến lược tham nên chất lượng lời giải của thuật toán phụ thuộc nhiều vào đồ thị đầu vào. Do đó, nghiên cứu này đề xuất thuật toán gần đúng dựa trên việc khởi tạo lời giải nhiều lần để giải bài toán Minimum s-club cover. Để nâng cao chất lượng lời giải tìm được, nghiên cứu còn đề xuất chiến lược tham lam để tìm club tốt nhất tại mỗi bước, cũng như phương pháp tạo lân cận và đánh giá lân cận của lời giải hiện tại. Hiệu quả của thuật toán đề xuất được chứng minh qua việc so sánh với thuật toán gần đúng được công bố trước đây trên hai tập dữ liệu khác nhau từ thư viện DIMACS. Kết quả thực nghiệm cho thấy, thuật toán đề xuất tìm được lời giải tốt hơn trên một phần ba bộ dữ liệu và tìm được lời giải bằng nhau trên hai phần ba bộ dữ liệu.