Bài viết Đề xuất chiến lược tìm kiếm lân cận cho bài toán cây Steiner nhỏ nhất đề xuất hai chiến lược tìm kiếm lân cận và chúng tôi sử dụng các chiến lược tìm kiếm lân cận này trong ngữ cảnh của thuật toán tìm kiếm lân cận biến đổi để 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 ĐỀ XUẤT CHIẾN LƯỢC TÌM KIẾM LÂN CẬN CHO 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 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 Khoa Công nghệ thông tin Trường Đại học Sài Gòn Viện Công nghiệp phần mềm và nội dung số Việt Nam Bộ Thông tin và Truyền thông Tóm tắt - Cây Steiner nhỏ nhất là bài toán tối ưu đồ thị Tập L được gọi là tập terminal các đỉnh thuộc tập L được có nhiều ứng dụng quan trọng trong khoa học và kỹ thuật. gọi là đỉnh terminal. Đỉnh thuộc cây T mà không thuộc tập Đây là bài toán thuộc lớp NP-hard. Hiện đã có nhiều hướng L được gọi là đỉnh Steiner của cây T đối với tập L. tiếp cận giải bài toán cây Steiner nhỏ nhất như các thuật toán tìm lời giải đúng các thuật toán tìm lời giải gần đúng Định nghĩa 2. Chi phí cây Steiner 3 cận tỉ lệ các thuật toán heuristic các thuật toán Cho T V T E T là một cây Steiner của đồ thị G. Chi metaheuristic trong đó các chiến lược tìm kiếm lân cận phí của cây T ký hiệu là C T là tổng trọng số của các cạnh có vai trò quyết định đối với việc cải thiện chất lượng lời thuộc cây T tức C T e E T w e . giải của các thuật toán metaheuristic. Trong bài báo này Định nghĩa 3. Cây Steiner nhỏ nhất 3 chúng tôi đề xuất hai chiến lược tìm kiếm lân cận và chúng Cho đồ thị G được mô tả như trên bài toán tìm cây tôi sử dụng các chiến lược tìm kiếm lân cận này trong ngữ Steiner có chi phí nhỏ nhất được gọi là bài toán cây Steiner cảnh của thuật toán tìm kiếm lân cận biến đổi để giải bài nhỏ nhất Steiner Minimal Trees Problem - SMT hoặc toán cây Steiner nhỏ nhất. Kết quả thực nghiệm với hệ được gọi ngắn gọn là bài toán cây Steiner Steiner Trees thống dữ liệu thực nghiệm chuẩn cho thấy rằng thuật toán Problem . đề xuất của chúng tôi cho lời giải với chất lượng tốt hơn so SMT là bài toán tối ưu đồ thị. Trong trường hợp tổng với một số thuật toán heuristic và một số thuật toán quát SMT đã được chứng minh thuộc lớp NP-hard .
