TSP问题的解决方案(0619073928).pdf
,. ; 算法设计与分析实验报告一 学号：姓名： 日期：20161230 得分： 一、实验内容： TSP 问题 二、所用算法的基本思想及复杂度分析： 1、 蛮力法 1） 基本思想 借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点 到自身节点的距离为无穷大。在第一行找到最小项a1j ，从而跳转到 第 j 行，再找到最小值 ajk ，再到第 k 行进行查找。 。然后构造各行允 许数组 rown=1,1 1，各列允许数组colablen=0,1,1 .1，其中 1 表示允许访问，即该节点未被访问；0 表示不允许访问，即该节点已经 被访问。如果改行或该列不允许访问，跳过该点访问下一节点。程序再 发问最后一个节点前，所访问的行中至少有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)，表示从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、回溯法 1）基本思想 确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以 深度优先方式搜索整个解空间。 这个开始结点成为活结点， 同时也成 为当前的扩展结点处， 搜索向纵深方向移至一个新结点。这个新结点 即成为新的活结点， 并为当前扩展结点。 如果在当前的扩展结点处不 能再向纵深方向移动， 则当前扩展结点就成为死结点。此时，应往回 移动（回溯）至最近的一个活结点处， 并使这个活结点成为当前的扩 ,. ; 展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所 要求的解或解空间中已无活结点时为止。 回溯法求解 TSP问题，首先把所有的顶点的访问标志初始化为0，然 后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对 应一个部分解， 即满足上述约束条件， 则在当前结点处选择第一棵子 树继续搜索， 否则，对当前子树的兄弟结点进行搜索，如果当前结点 的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。 采用邻接矩阵 mpnn 存储顶点之间边的情况， 为避免在函数间传递 参数，将数组 mp 设置为全局变量，设数组xn表示哈密顿回路经过 的顶点。 2）复杂度分析 在哈密顿回路的可能解中，考虑到约束条件xi!=xj(1%dn“,i,j); s=s+aij; i=j; printf(“最短 总距离 为：%dn“,s); int min(int *a) int j=0,m=a0,k=0; while(colablej=0|rowj=0) j+; m=aj; / 求最短距离 for(;j=aj) m=aj;/m始终保持最短距离 k=j; return k; ,. ; 2、动态规划法 int init() int i; int j; int t; if(scanf(“%d“, for(i=0; i0) if(getcon(t,i)+gikn) ,. ; if(graphroadn1!=INF for(int i=1;iab; cingraphab; graphba=graphab; vis1=1; road1=1; /假设是从1 开始 backtrack(2); coutp.lb; ; priority_queue q; int low,up; int inq22; / 确定上界 int dfs(int u,int k,int l) if(k=n) return l+mpu1; int minlen=INF , p; for(int i=1; impui)/*取与所有点的连边中最小的边*/ minlen=mpui; p=i; ,. ; inqp=1; return dfs(p,k+1,l+minlen); int get_lb(node p) int ret=p.sumv*2;/路径上的点的距离 int min1=INF,min2=INF;/起点和终点连出来的边 for(int i=1; impip.st) min1=mpip.st; ret+=min1; for(int i=1; impp.edi) min2=mpp.edi; ret+=min2; for(int i=1; impij) min1=mpij; for(int j=1; jmpji) min2=mpji; ret+=min1+min2; return ret%2=0?(ret/2):(ret/2+1); void get_up() inq1=1; up=dfs(1,1,0); void get_low() low=0; for(int i=1; iup) continue; q.push(next); ,. ; return ret; 四、运行输出结果： （1）蛮力法 （2）动态规划法 （3）回朔法 ,. ; （4）分支限界 五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： TSP 问题在很多地方都可以运用到，并且好多问题都是由TSP 问题延伸和发展 的，也可以称之为TSP 问题，不过其思路大致相似，于是我们可以运用已学过 的算法对其进行解决。我在学习算法课以前的TSP 问题大都用动态规划以及回 溯法，究其时间复杂度以及代码的复杂度比较低，思路比较清晰， 在解决此类延 伸问题时容易调试和修改。 学完算法后最有感触的一点就是，算法的精髓并不在 ,. ; 于其方式方法， 而在于其思想思路。 有了算法的思想， 那么潜移默化中问题就可 以得到解决
