文章摘要
引用本文:林 耿,朱文兴.一种求解最大二等分问题的分散搜索算法[J].福州大学学报(自然科学版),2014,42(6):823~827
一种求解最大二等分问题的分散搜索算法
A scatter search algorithm for solving the max-bisection problem
  
DOI:10.7631/issn.1000-2243.2014.06.0823
中文关键词: 最大二等分问题  分散搜索  局部搜索  启发式算法
英文关键词: max-bisection problem  scatter search  local search  heuristic
基金项目:
作者单位
林 耿 闽江学院数学系福建 福州 350108 
朱文兴 福州大学离散数学研究中心福建 福州 350116 
摘要点击次数: 786
全文下载次数: 670
中文摘要:
      最大二等分问题是图论中的一个NP困难问题. 本研究提出一种基于分散搜索框架的启发式算法求解最大二等分问题. 该分散搜索算法采用Kernighan-Lin算法作为局部搜索算法,利用解的质量和解之间的距离构造参考集,通过两个可行解构造新的可行解. 利用一些标准测试例子测试算法,实验结果与现存算法所得结果比较,表明该算法是有效的.
英文摘要:
      The max-bisection problem is one of NP-hard problems in graph theory,This paper presents a heuristic method based on the scatter search methodology for solving the max-bisection problem. This scatter search algorithm uses Kernighan-Lin algorithm as a local search procedure,and constructs reference sets by the solution quality and the distance between solutions,and generates a new feasible solution from two feasible solutions. A lot of benchmark instances from the literature are used to test the proposed algorithm,the experimental results and the comparison with existed algorithm show that the proposed algorithm is efficient.
查看全文   查看/发表评论  下载PDF阅读器
关闭