Thuật Toán Bees Giải Bài Toán Cây Steiner Nhỏ Nhất Trong Trường Hợp Đồ Thị Thưa

Abstract

Cây Steiner nhỏ nhất (Steiner Minimal Tree - SMT) là bài toán tối ư u t ổ hợp có nhiều ứng dụng quan trọng trong khoa học và kỹ thuật; đây là bài toán thuộc lớp NP-hard. Trong hàng chục năm qua, đã có nhiều bài báo khoa học công bố cách giải bài toán SMT. Trong bài báo này, chúng tôi đề xuất một thuật toán mới dựa t rên s ơ đồ thuật toán bees cơ bản để giải bài toán SMT. Chúng tôi đã cài đặt và thực nghiệm thuật toán đề xuất trên 38 bộ dữ liệu trong hệ thống dữ liệu thực nghiệm chuẩn; kết quả thực nghiệm cho thấy thuật toán đề xuất cho lời giải với chất lượng tốt hơn một số thuật toán heuristic và metaheuristic hiện biết trên một số bộ dữ liệu.