ĐỀ XUẤT MỘT SỐ THUẬT TOÁN HEURISTIC GIẢI BÀI TOÁN CÂY STEINER NHỎ NHẤT

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 theo các hướng tiếp cận giải chính xác và giải gần đúng. Trong bài báo này, hai thuật toán heuristic giải bài toán SMT được đề xuất; đề xuất thứ nhất là sử dụng ý tưởng chính của thuật toán tìm cây đường đi ngắn nhất và đề xuất thứ hai là kết hợp ý tưởng chính của các thuật toán Prim và Dijkstra. Các thuật toán đề xuất đã được thực nghiệm trên các đồ thị thưa trong hệ thống dữ liệu thực nghiệm chuẩn; kết quả thực nghiệm cho thấy rằng các thuật toán đề xuất là hiệu quả hơn một số thuật toán giải gần đúng hiện biết; nhất là đối với các đồ thị thưa có kích thước lớn. Các kết quả thực nghiệm này là thông tin hữu ích cho các nghiên cứu tiếp theo về bài toán SMT.