Bài toán tìm cây khung chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree - MRCST) có thể được tìm thấy trong nhiều bài toán thiết kế mạng. Trong trường hợp tổng quát, bài toán MRCST đã được chứng minh là NP- khó. Bài báo này đề xuất thuật toán giải bài toán MRCST được phát triển dựa trên sơ đồ thuật toán bầy ong. | Tạp chí Tin học và Điều khiển học, , (2013), 265–276 THUẬT TOÁN BẦY ONG GIẢI BÀI TOÁN CÂY KHUNG VỚI CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT∗ PHAN TẤN QUỐC1 , NGUYỄN ĐỨC NGHĨA2 1 Khoa 2 Viện công nghệ thông tin, Trường Đại học Sài Gòn; Email: quocpt@ Công nghệ Thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội Tóm t t. Bài toán tìm cây khung chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree - MRCST) có thể được tìm thấy trong nhiều bài toán thiết kế mạng. Trong trường hợp tổng quát, bài toán MRCST đã được chứng minh là NP- khó. Bài báo này đề xuất thuật toán giải bài toán MRCST được phát triển dựa trên sơ đồ thuật toán bầy ong. Các kết quả tính toán thực nghiệm cho thấy thuật toán đề xuất cho lời giải với chất lượng tốt hơn thuật toán xấp xỉ Wong, các thuật toán meta-heuristics dạng quần thể như Max-Min Ant System (MMAS), thuật toán di truyền (GA), thuật toán Artificial Bee Colony (ABC) và một số thuật toán heuristic hiện biết. Cái giá phải trả để đạt được kết quả này là số lượng cây khung mà thuật toán của chúng tôi phải khảo sát là lớn hơn nhiều so với các thuật toán khác, chẳng hạn, trung bình là gấp 16000 lần so với thuật toán Wong và gấp lần so với thuật toán ABC. T khóa. Cây khung có chi phí định tuyến nhỏ nhất, thuật toán bầy ong, thuật toán meta-heuristic, trí tuệ bầy đàn. Abstract. The task to find Minimum Routing Cost Spanning Tree (MRCST) can be found in many network design problems. In general cases, the MRCST problem is proved to be NP-hard. This paper proposes an algorithm to solve MRCST problem based on the schema of bee algorithm. The computational experiment results show that our proposed algorithm outperforms the Wong’s algorithm, population-based meta-heuristics like Max-Min Ant System (MMAS), Genetic Algorithm (GA), Artificial Bee Colony algorithm (ABC), and other well-known heuristic algorithms. The cost to get this result is the large number of spanning trees examined by our algorithm compared to other .
