TSP问题的解决方案(0619073928).pdf
《TSP问题的解决方案(0619073928).pdf》由会员分享,可在线阅读,更多相关《TSP问题的解决方案(0619073928).pdf(19页珍藏版)》请在三一文库上搜索。
1、,. ; 算法设计与分析实验报告一 学号:姓名: 日期:20161230 得分: 一、实验内容: TSP 问题 二、所用算法的基本思想及复杂度分析: 1、 蛮力法 1) 基本思想 借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵,任意节点 到自身节点的距离为无穷大。在第一行找到最小项a1j ,从而跳转到 第 j 行,再找到最小值 ajk ,再到第 k 行进行查找。 。然后构造各行允 许数组 rown=1,1 1,各列允许数组colablen=0,1,1 .1,其中 1 表示允许访问,即该节点未被访问;0 表示不允许访问,即该节点已经 被访问。如果改行或该列不允许访问,跳过该点访问下一节点。
2、程序再 发问最后一个节点前,所访问的行中至少有1 个允许访问的节点,依次 访问这些节点找到最小的即可;在访问最后一个节点后,再次访问,会 返回 k=0,即实现访问源节点,得出一条简单回路。 2) 复杂度分析 基本语句是访问下一个行列中最小的点,主要操作是求平方,假设有n ,. ; 个点,则计算的次数为n2-n。T(n)=n*(n-1)=O(n2) 。 2、 动态规划法 1) 基本思想 假设从顶点s 出发, 令 d(i, V)表示从顶点i 出发经过V(是一个点的集合)中各个顶点一次且 仅一次,最后回到出发点s 的最短路径长度。 推导: (分情况来讨论) 当 V 为空集,那么d(i, V),表示从
3、i 不经过任何点就回到s 了,如上图的城市 3-城 市 0(0 为起点城市 )。此时 d(i, V)=Cis(就是城市 i 到 城市 s 的距离 )、 如果 V 不为空,那么就是对子问题的最优求解。你必须在V 这个城市集合中,尝试每一 个,并求出最优解。 d(i, V)=minCik +d(k, V-k) 注: Cik 表示你选择的城市和城市i 的距离, d(k, V-k) 是一个子问题。 综上所述, TSP 问题的动态规划方程就出来了: 2)复杂度分析 和蛮力法相比,动态规划求解tsp 问题,把原来时间复杂性O(n! )的 排列转化为组合问题,从而降低了时间复杂度,但仍需要指数时间。 3、回
4、溯法 1)基本思想 确定了解空间的组织结构后,回溯法从开始结点(根结点)出发,以 深度优先方式搜索整个解空间。 这个开始结点成为活结点, 同时也成 为当前的扩展结点处, 搜索向纵深方向移至一个新结点。这个新结点 即成为新的活结点, 并为当前扩展结点。 如果在当前的扩展结点处不 能再向纵深方向移动, 则当前扩展结点就成为死结点。此时,应往回 移动(回溯)至最近的一个活结点处, 并使这个活结点成为当前的扩 ,. ; 展结点。回溯法以这种工作方式递归地在解空间中搜索,直至找到所 要求的解或解空间中已无活结点时为止。 回溯法求解 TSP问题,首先把所有的顶点的访问标志初始化为0,然 后在解空间树中从根
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- TSP 问题 解决方案 0619073928
链接地址:https://www.31doc.com/p-5596387.html