logo资料库

tsp贪心算法.docx

发布时间：2022-06-17 发布人：admin 分类：说明书 资料大小：0.26M 资料格式：docx 举报 版权申诉
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
资料共13页，剩余部分请下载后查看
    1、需求分析
    1.程序的功能：
    2.输入输出的要求：
    2、概要设计
    1.程序流程图：
    2.程序组成：
    3、详细设计
    4、调试分析
    1.调试问题：
    2.邻接矩阵：
    3.树：
    4.结果：
    5.存在问题：
    6.改进设想：
    5、核心源程序清单和执行结果
    1.类定义：
    2.函数定义：
    3.成员函数定义：
    4.结果：
    参考文献：
    学 号 09730204 数据结构课程设计 设计说明书 题目 TSP 问题回溯算法 起止日期： 2011 年 12 月 26 日 至 2011 年 12 月 30 日 学 生 姓 名 徐 达 班 成 级 绩 指 导 教 师 ( 签 字 ) 09 级 网 络 (2) 班 电子与信息工程系 2011 年 12 月 30 日
    天津城市建设学院 课程设计任务书 2011—2012 学年第 1 学期 电子与信息工程 系 网络工程 专业 2 班级 课程设计名称： 数据结构课程设计 设计题目： TSP 问题（回溯法求解） 完成期限：自 2011 年 12 月 26 日至 2011 年 12 月 30 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 在本课程设计过程中要求学生： （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭 者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全 部人员皆以零分计入本课程设计成绩。 （3）学生在接受设计任务后，根据要求认真完成。 （4）认真编写课程设计报告。 三、设计内容 TSP 问题（回溯法求解） 1) 问题描述 所谓 TSP 问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求 所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为 人知的问题。 2) 基本要求 (1) 上网查找 TSP 问题的应用实例； (2) 分析求 TSP 问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法；
    (4) 分析算法的时间复杂度。 3) 设计思想 对于 TSP 问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有 可能的旅行路线，从中选择最佳的一条。但是用穷举法求解 TSP 问题的时间复杂度为Ο(n!)， 当 n 大到一定程度后是不可解的。 穷举法的实现过程需要回溯算法。 回溯算法基本思想：回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空 间。开始的结点成为活结点，同时也成为当前的扩展结点，并成为当前扩展结点。如果在当 前的扩展结点处不能再向纵深方向移动，则当前这个活结点成为死结点。此时，应回溯到最 近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归在解 空间中搜索，直至找到所要求的解或解空间中已无活结点为止。 四、参考文献 1. 王红梅，数据结构，清华大学出版社； 2. 王红梅，数据结构学习辅导与实验指导，清华大学出版社； 3. 王晓东，计算机算法设计与分析，电子工业出版社。
    目录 1、需求分析..............................................................................................................................5 1.程序的功能：................................................................................................................5 2.输入输出的要求：........................................................................................................5 2、概要设计..............................................................................................................................6 1.程序流程图：................................................................................................................6 2.程序组成：....................................................................................................................6 3、详细设计..............................................................................................................................7 4、调试分析..............................................................................................................................9 1.调试问题：....................................................................................................................9 2.邻接矩阵：....................................................................................................................9 3.树：................................................................................................................................9 4.结果：..........................................................................................................................10 5.存在问题：..................................................................................................................10 6.改进设想：..................................................................................................................10 5、核心源程序清单和执行结果............................................................................................11 1.类定义：......................................................................................................................11 2.函数定义：..................................................................................................................11 3.成员函数定义：..........................................................................................................12 4.结果：..........................................................................................................................13 参考文献：..............................................................................................................................13
    1、需求分析 1.程序的功能： 一个旅行家要穿过多个城市，已知城市个数，以及城市间距，求出最短路径解 和最短路径长度。 2.输入输出的要求： 输入城市数目 N 为正整数，城市间距离按邻接矩阵方式排列输入，最小值为 0， 共有 N*N 个数值；输出最优解和最优值。
    2、概要设计 1.程序流程图： 2.程序组成： （1）声明一个类，包含带参函数，指针数组，无边标志，当前最优值和最优解，以及用户 要输入的邻接矩阵，结点数； （2）对 TSP 进行定义和初始化部分； （3）定义调换函数，设一个中间值，对 a,b 进行值调换； （4）TSP 成员函数 Backtrack()，通过判断对树进行深度优先遍历，并不断比较更新最优值 和最优解。
    3、详细设计 Backtrack 函数： void Traveling::Backtrack(int i) { if(i==n) { if(a[x[n-1]][x[n]]!=NoEdge &&a[x[n]][1]!=NoEdge &&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<=bestc||bestc==NoEdge)) { } for(int j=1;j<=n;j++) bestx[j]=x[j]; for(j=1;j<=n;j++) bestx[j]=x[j]; bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1]; } 当前扩展结点是排列树的叶结点的父结点，检测是否存在一条从顶点 x[n-1]到顶点 x[n] 和一条从顶点 x[n]到顶点 1 的边。若存在，则找到一条回路。判断是否优于当前最优值 bestc， 若是则更新。 else{ for(int j=i;j<=n;j++) if(a[x[i-1]][x[j]]!=NoEdge &&(cc+a[x[i-1]][x[j]]
    Y.x[i]=i; Y.a=a; Y.n=n; Y.bestc=NoEdge; Y.bestx=v; Y.cc=0; Y.NoEdge=NoEdge; Y.Backtrack(2); int j; cout<<"最优解："; for(j=1;j<=n;j++) { cout<
    分享到：
    赞 收藏

    相关推荐

    资料库

    网络技术

    共收录2367份资料，累计7个分类，关注成员有19位，主要包括：综合布线,网管软件,网络监控,网络设备,其它,系统集成,网络基础

    热门标签

    综合布线 网管软件 网络监控 网络设备 其它 系统集成 网络基础

    最新资料