论文部分内容阅读
TSP(Traveling Salesman Problem,旅行商问题)是组合优化领域的重要问题之一,同时也是众多现实问题的原形,对其开展深入广泛的研究具有重要的理论价值和实用价值。本文在借鉴国外前沿启发式算法思想的基础上,基于Lin-Kernighan改进型算法引擎,开发了能够高效解决TSP的可视化处理软件。在如下几方面做了深入研究: 首次将TSP处理软件的开发作为一个研究课题。说明对TSP问题的研究,应该将算法设计与软件构建并列考虑,并特别重视对完整软件的开发,以促进优秀算法的广泛传播和改善发展。 本文对可视化TSP处理软件的概念界定是一个研究亮点。基于概念界定设计了合理的软件功能架构,使TSP问题生成的可视化、TSP数据显示的可视化、TSP求解性能的可视化集一大成。 在引进了经典的Lin-Kernighan算法基础上,对该算法作了较大改进。特别深入的探讨了候选边集的生成方法,即运用最小1-树和升级(Ascent)操作确定α-接近度,由此对边的优先性排序。相比于传统的近邻法,α-接近度法确定最优边的性能大大改善。 本文特别重视阐述算法实现细节与其性能间的深刻联系,用两章的篇幅分别介绍了算法引擎的C语言开发和可视化平台的VC开发。其中在算法引擎章,围绕引擎的总体流程,对重要启发式算子的程序实现作了深入说明,并穿插了边成本的快速计算、存储和查找策略;初始解的生成策略;数据结构的选择策略等。在可视化章,围绕软件模块架构,依次介绍了数据处理模块的开发、可视化模块的开发和扩展模块与算法引擎的整合,并穿插了大量的数据结构介绍和容器选取应用策略。这两章内容是难得的开发模块化的高效TSP程序软件的指南。 基于本文开发的可视化TSP处理软件性能优良。首先,它广泛支持TSPLIB的TSP、ATSP、HCP类问题,对TSPLIB中大部分问题都在较短时间内求出了最优解,包括7397点的TSP问题。其次,它的扩展模块支持TSP问题快速生成、地图模式和坐标模式的人机交互操作。文中解决的案例和各类图示都说明该软件对广大研究、应用人员有重要的研究应用价值。