一种基于分层模型的TSP构建算法

提出了一种新算法,有效地减少了最近邻域法和贪婪算法在构建旅行商问题可行解过程中引入不合理长边的问题。该算法先借助一种由伪凸包算子所得到的分层模型对旅行商问题中的城市分布进行分析,之后通过将分层模型中相对外层的点逐个添加到内层的规则得到可行解。借助仿真实验求解TSPLIB标准库中的40实例,并与最近邻域法和贪婪算法进行对比,结果表明分层融合算法具有更高的精度,其平均求解质量达到8.47%。

类双曲壳的概念及算法

论文提出类双曲壳的概念,类双曲壳是一类通过射影平面无穷远直线的凸壳。运用拓扑同胚来帮助提出射影凸集和类双曲壳的概念。并借助于有向射影几何的正平面上可定向的优势,分析了从经典凸壳到类双曲壳的射影变换。构造出一个在欧氏平面上的实时凸壳算法,用于两个区域中间寻找直线簇。