Thuật toán tìm kiếm Hill climbing giải bài toán Cây Steiner nhỏ nhất

Hill Climbing Search Algorithm For Solving Steiner Minimum Tree Problem

Abstract

Cây Steiner nhỏ nhất 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. Bài báo này đề xuất một thuật toán hill climbing search để giải bài toán cây steiner nhỏ nhất; trong đó đề xuất cách thức tìm kiếm lân cận và cách thức kết hợp với tìm kiếm lân cận ngẫu nhiên để giải quyết vấn đề tối ưu cục bộ. Kết quả thực nghiệm với hệ thống dữ liệu thực nghiệm chuẩn cho thấy thuật toán đề xuất của chúng tôi cho lời giải với chất lượng tốt hơn so với một số thuật toán heuristic hiện biết trên một số bộ dữ liệu.