Open AccessThuật toán tìm kiếm Hill climbing giải bài toán Cây Steiner nhỏ nhất
Author(s) -
Trần Việt Chương,
Phan Tấn Quốc,
Hà Hải Nam
Publication year - 2020
Publication title -
công trình nghiên cứu công nghệ thông tin truyền thông
Language(s) - Vietnamese
Resource type - Journals
ISSN - 1859-3526
DOI - 10.32913/mic-ict-research-vn.v2020.n1.897
Subject(s) - stereochemistry , combinatorics , chemistry , mathematics
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.