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

Application of Frequency Graph Based on Group Theory in the Traveling Salesman Problem

作　　者：王永[1] WANG Yong(School of New Energy,North China Electric Power University,Beijing 102206,China)

机构地区：[1]华北电力大学新能源学院,北京102206

出　　处：《郑州大学学报（理学版）》2025年第1期74-80,共7页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家重点研发计划项目(2022YFE0207000)。

摘　　要：针对最小生成树(minimum spanning tree,MST)和旅行商问题(travelling salesman problem,TSP),介绍了完全图上的两类特殊图并定义了这些图上的交运算,每类特殊图和交运算构成一个半群。根据半群性质计算出频率图,分析了最优哈密顿圈(optimal Hamiltonian cycle,OHC)和MST中边的频率性质,证明了频率图上OHC中边的频率下界,该频率下界用于缩小OHC的搜索空间,降低了TSP的求解难度。此外,采用一些TSP算例验证了频率图上OHC中边的频率性质。For the minimum spanning tree(MST)and travelling salesman problem(TSP),two kinds of special graphs in complete graph were introduced and the intersection operation for the graphs was defined.Each kind of special graphs and the intersection operation formed one semi-group.According to the property of semi-group,the frequency graph was computed.The frequency properties for edges in optimal Hamiltonian cycle(OHC)and MST were analyzed.The lower frequency bound for the OHC edges was proven,and it greatly reduced the search space of OHC and decreased the hardness of TSP.Furthermore,the frequency properties for the OHC edges in frequency graphs were verified with some TSP instances.

关 键 词：半群 特殊图 频率图 旅行商问题 最小生成树 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]