Bài viết này đề xuấ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 tất định và cách thức kết hợp tìm kiếm lân cận tất định với tìm kiếm lân cận ngẫu nhiên để giải quyết bài toán Cây Steiner nhỏ nhất. | Các công trình nghiên cứu phát triển và ứng dụng Công nghệ Thông tin và Truyền thông Thuật toán tìm kiếm Hill climbing giải bài toán Cây Steiner nhỏ nhất Trần Việt Chương1 Phan Tấn Quốc2 Hà Hải Nam3 1 Trung tâm Công nghệ thông tin và Truyền thông Sở Thông tin và Truyền thông tỉnh Cà Mau 2 Khoa Công nghệ thông tin Trường Đại học Sài Gòn 3 Viện Khoa học Kỹ thuật Bưu điện Học viện Công nghệ Bưu chính Viễn thông Tác giả liên hệ Trần Việt Chương chuongcm74@ Ngày nhận bài 26 10 2019 ngày sửa chữa 06 03 2020 Định danh DOI Tóm tắt Cây Steiner nhỏ nhất Steiner Minimum 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. Trước đây đã có nhiều công trình nghiên cứu theo các hướng tiếp cận khác nhau đưa ra các thuật toán để giải bài toán SMT. Bài báo này đề xuấ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 tất định và cách thức kết hợp tìm kiếm lân cận tất định với tìm kiếm lân cận ngẫu nhiên để giải quyết bài toán Cây Steiner nhỏ nhất. 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. Từ khóa thuật toán tìm kiếm leo đồi Cây Steiner nhỏ nhất thuật toán heuristic thuật toán metaheuristic lân cận tất định lân cận ngẫu nhiên tối ưu cục bộ. Title Hill Climbing Search Algorithm For Solving Steiner Minimum Tree Problem Abstract Steiner Minimum Tree SMT is a complex optimization problem that has many important applications in science and technology. This is a NP-hard problem. In the past there were many research projects based on different approaches offering algorithms to solve SMT problems. This paper proposes a Hill climbing search algorithm to solve the SMT problem which suggests how to search nearby and how to combine with random .
