数据结构与算法分析2.docx

文档介绍：数据结构与算法分析算法设计报告书班级惠普测试学号姓名指导教师庞志永算法设计项目名称::城市集合城市之间距离C{c,c,...,c},d(c,c)Z,mij其中:,。d(c,c)d(c,c)d(c,c)c,ijjkikijk询问:寻找个城市的一个排列<,...,>,使得:mcc()(m)m,)(i)(i+)i=其中是,的一个全排列,且(),...,(m),...,mc(m)c()。.基本要求(),并选择适当的编程语言在计算机上实现。()程序能够正常运行,计算结果正确,满足设计要求。.算法描述()对TSP问题实例的赋权完全图G(V,E)调用最小生成树算法,,得到G的最小生成树T;()复制最小生成树T的每条边,形成欧拉图G';()在G'中寻找欧拉回路;()采用"抄近路"方法,将欧拉回路变成TSP旅游回路。.模块划分(仅供参考)()描述及输入原始数据模块()求解最小生成树模块()构造欧拉图模块()搜索欧拉回路模块()抄近路计算模块():在给定一系列城市和每对城市之间的距离的情况下,求解访问每一座城市一次并回到起始城市的最短回路。解答本课题的思路:以最小生成树T求解旅游回路:复制树的每条边构建欧拉图,运用深度优先搜索寻找欧拉图的欧拉回路,而树的深度优先搜索序列与此欧拉回路相同,可用深度优先搜索算法优化求解欧拉回路和抄近路算法的过程。.运行结果及其相关描述要求实例中城市的数量在—之间。命令行输入此次实验验证个城市即为个顶点,条边