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

Trần Việt Chương, Phan Tấn Quốc, Hà Hải Nam



DOI: 10.15625/vap.2017.00017

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.

Keywords


Steiner minimal tree, sparse graph, heuristic algorithm, metaheuristic algorithm



Copyright (c) 2018 PROCEEDING of Publishing House for Science and Technology



PROCEEDING

PUBLISHING HOUSE FOR SCIENCE AND TECHNOLOGY

Website: http://vap.ac.vn

Contact: nxb@vap.ac.vn