TSP问题的解决方案报告书.docxVIP

姓 得 姓 得 《算法设计与分析》实验报告一 学 号： 日 期： 一、实验内容： TSP 问题 二、所用算法的根本思想及复杂度分析： 1、蛮力法 名： 分： 1)根本思想 借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点 到自身节点的距离为无穷大。在第一行找到最小项 a[1][j] ，从而跳转到 第 j 行，再找到最小值 a[j][k] ，再到第 k 行进展查找。 。。然后构造各行允 许数组 row[n]={1,1 … 1} ，各列允许数组 colable[n]={0,1,1 … .1} ，其中 1 表示允许访问，即该节点未被访问； 0 表示不允许访问，即该节点已经 被访问。如果改行或该列不允许访问，跳过该点访问下一节点。程序再 发问最后一个节点前，所访问的行中至少有 1 个允许访问的节点，依次 访问这些节点找到最小的即可；在访问最后一个节点后，再次访问，会 返回 k=0 ，即实现访问源节点，得出一条简单回路。 2)复杂度分析 根本语句是访问下一个行列中最小的点，主要操作是求平方，假设有 n 个点，则计算的次数为 n^2-n。T(n)=n*(n- 1)=O(n^2)。 ...wd... 2、动态规划法 1)根本思想 假设从顶点 s 出发， 令 d(i, V’)表示从顶点 i 出发经过 V’(是一个点的集合)中各个顶点一次且 仅一次，最后回到出发点 s 的最短路径长度。 推导： (分情况来讨论) ① 当 V’为空集，那么 d(i, V’)，表示从 i 不经过任何点就回到 s 了，如上图的 城市 3-城 市 0(0 为起点城市)。此时 d(i, V’)=Cis(就是 城市 i 到 城市 s 的距离)、 ②如果 V’不为空，那么就是对子问题的最优求解。你必须在 V’这个城市集合中，尝试每一 个，并求出最优解。 d(i, V’)=min{Cik + d(k, V’-{k})} 注： Cik 表示你选择的城市和城市 i 的距离， d(k, V’-{k})是一个子问题。 综上所述， TSP 问题的动态规划方程就出来了： 2〕复杂度分析 和蛮力法相比，动态规划求解 tsp 问题，把原来时间复杂性 O〔n ！〕的 排列转化为组合问题，从而降低了时间复杂度，但仍需要指数时间。 3、回溯法 1 )根本思想 确定了解空间的组织构造后，回溯法从开场结点〔根结点〕出发，以 深度优先方式有哪些信誉好的足球投注网站整个解空间。 这个开场结点成为活结点， 同时也成 为当前的扩展结点处， 有哪些信誉好的足球投注网站向纵深方向移至一个新结点。 这个新结点 即成为新的活结点，并为当前扩展结点。 如果在当前的扩展结点处不 能再向纵深方向移动， 则当前扩展结点就成为死结点。 此时，应往回 移动 〔回溯〕 至最近的一个活结点处， 并使这个活结点成为当前的扩 展结点。 回溯法以这种工作方式递归地在解空间中有哪些信誉好的足球投注网站， 直至找到所 要求的解或解空间中已无活结点时为止。 回溯法求解 TSP 问题，首先把所有的顶点的访问标志初始化为 0 ，然 ...wd... 后在解空间树中从根节点出发开场有哪些信誉好的足球投注网站，如果从根节点到当前结点对 应一个局部解，即满足上述约束条件，则在当前结点处选择第一棵子 树继续有哪些信誉好的足球投注网站，否则，对当前子树的兄弟结点进展有哪些信誉好的足球投注网站， 如果当前结点 的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。 采用邻接矩阵 mp[n][n]存储顶点之间边的情况，为防止在函数间传递 参数，将数组 mp 设置为全局变量，设数组 x[n]表示哈密顿回路经过 的顶点。 2)复杂度分析 在哈密顿回路的可能解中，考虑到约束条件 xi!=xj(1=I,j=n,i!=j),则 可能解应该是〔1,2,… ,n〕的一个排列，对应的解空间树种至少有 n! 个叶子结点，每个叶子结点代表一种可能解。当找到可行的最优解时 ， 算法停顿。根据递归条件不同时间复杂度也会不同 ，这里为 O〔n ！〕。 4、分支限界法 1 )根本思想 分支界限法以广度优先或以最小消耗〔最大效益〕优势的方式有哪些信誉好的足球投注网站问 题的解空间树。 问题的解空间树是表示问题解空间的一棵有序树， 常 见的有子集树和排列树。 在有哪些信誉好的足球投注网站问题的解空间树时 ，分支界限法与回 溯法的主要区别在于他们对当前扩展结点所采用的扩展方式不同。在 分支界限法中，每一个活结点只有一次时机成为扩展结点。 活结点一 旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中， 导致不可行解或导致非最优解得儿子结点被舍弃 ，其余儿子结点被参 加活结点表中。 算法开场时创立一个最小堆 ，用于表示活结点优先队 ...wd... 列。堆中每个结点的子树费用的下界 lcost 值是优先队列的优先级。 接着