基于群论的频率图在旅行商问题中的应用

  • 打印
  • 收藏
收藏成功
微博 QQ空间 微信


打开文本图片集

摘要： 针对最小生成树（minimum spanning tree，MST）和旅行商问题（travelling salesman problem，TSP），介绍了完全图上的两类特殊图并定义了这些图上的交运算，每类特殊图和交运算构成一个半群。根据半群性质计算出频率图，分析了最优哈密顿圈（optimal Hamiltonian cycle，OHC）和MST中边的频率性质，证明了频率图上OHC中边的频率下界，该频率下界用于缩小OHC的搜索空间，降低了TSP的求解难度。（剩余12471字）

试读结束

目录
monitor