科研之友
微信
新浪微博
Facebook
分享链接
摘要
随着旅行商问题规模的增长，完全图上最优解的搜索空间呈指数增长。为了减小最优解的搜索空间，提出一种针对旅行商问题的割边算法。推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率，采用一定数量的四边形最优圈内的最短路径计算边频率，根据所有边的平均边频率割边，基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率。任给一个完全图，割边算法有4个步骤：1)随机选取包含每条边的若干个四边形；2)采用所选四边形最优圈内的最短路径计算各边的边频率；3)步删除5/6条最小边频率的边；4)对度数小于2的节点进行添边操作。计算实验表明：保留边数为完全图上边数量的1/6左右，采用精确算法求解割边后旅行商问题的计算时间也有所减少。
- 单位
