Thuật toán tìm kiếm TABU giải bài toán cây khung với chi phí định tuyến nhỏ nhất

Abstract

Minimum Routing Cost Spanning Tree (MRCST)  is  one  of  spanning  tree  optimization problems  having  several  applications  in  network design. In general cases, the problem is proved as NP (Non-deterministic  Polynomial)  -  hard.  This  paper proposes  an  algorithm  for  solving  MRCST  problem based  on  the  schema  of  TABU  search  algorithm. Experimental  results  show  that  our  proposal algorithm  is  better  than  Wong  algorithm,  many population-based  meta-heuristics  like  Max-Min  Ant System  (MMAS),  Genetic  Algorithm  (GA)  and outperforms  recently  proposed  Artificial  Bee  Colonyalgorithm  (ABC)  both  in  terms  of  solution  quality  as well as running time.