TSP问题报告算法分析与设计

1、TSP问题一、问题描述所谓TSP问题是指旅行商要去n个城市推销商品，其中每个城市 到达且仅到达一次，并且要求所走的路程最短(该问题又称货郎担问 题、邮递员问题、售货员问题等)。TSP问题最容易想到、也肯定 能得到最优解的算法是穷举法，即考察所有可能的行走线路，从中选 出最佳的一条。二、解题思路1. 基本思路对于图G=(V,E),从起点出发，其余点作为路径集合，然后列出路 径集合中各个点作为子路径起点，其余点作为路径集合的情况，从中 选取路径长度最短的情况，再对路径集合迭代计算，直到路径集合为 空的时候，这时最短路径的情况即是该点到原点的距离，路径集合是 空集,此时己触碰临界条件，可以不断回溯之

2、前的迭代，进而解决 此问题。2. 最优值函数和边界条件d(kf ) = Ckild(i,W) = mincik + d(k V - k) (k G V)第二行是最优值函数。从i到集合v的最优路径是以v中某一 点作为子路径起点，其余点作为路径集合的路径的长度加上从k至ij i 的距离的最优值。第一行是边界条件。当子路径的路径集合是空集时，最优子问题 的解，木题来说也就是子路径的最短路径就是从子路径的起点到原来 起点的距离。3. 标记函数标记函数同时也是算法的核心函数，完全按照递推公式的思想， 使用迭代的方式。distance是第一个核心函数，主要负责路径的输出; distance 1是第二个核心

3、函数，主要负责寻求子集合的最短路径并计算 长度。第一核心函数中调用了第二核心函数，第一核心函数只负路 径的输出，在将问题细化深入的过程中，将真正的路径寻找和计算交 给第二核心函数。4. 标记函数的解读：(l)distancedouble distance(int aint bint double dNUM4int start)a:子问题起点b:字问题路径集合d:距离矩阵(最开始创建的，所有调用函数过程中，都使用的这个，没有 更改，只有读取)start:原问题起点(达到临界条件时，找到路径长度)边界条件if(c=0)coutstart;return dastart;非临界条件时候，构建所有路径集

4、合的，起点和对应的路径集合，在迭 代的时候会使用到elsefor(i=0;ic;i+)pointi=bi;k=0;for(j=0;jc;j+)eik=bj; /*节点方阵，冗余的*/k+;mindistance=distancel(pointk,ek，c-：l,d,start) +da pointk ；假定下一层的最短路径就是p6以及其对应的路径矩阵ekfor(i=0;i(distancel(po int i+l ,ei+lstart)+dapointi+l)k=i+l;mindistance二distancel(pointk，ekc-ld，start)+dapoin tk;coutpoint

5、k;r eturn dis tan ce(po int k，ek, c-ld start)+da pointk;(2)distanceldouble distancel(int aint bint cdouble dNUMjint start) 边界条件if(c=0)return dastart;非边界条件elsefor(i=0;ic;i+)pointi=bi;k=0;for(j=0;jc;j+)eik=bj;k+;/拆分该点到达起点所需经过的集合该点的下一点到达起点所需经过的集合 mindistance=distancel(point0,e0tart)+dapoint0；for(i=0;i(

6、dis tancel (point i+1 ,ei+：LC：L，d, start) +d apointi+l)mindistance=distancel(pointi+l，ei+l c-l。start)+da pointi+l;return mindistance;求最小值5. 时间复杂度分析整体的时间复朵度是O (2M)。时间集合中共有n个点，每个点 所对应的路径集合中有n-1个点，产生的集合是2A(n-l)个，对于其中 的每个集合，比较的次数是一个常数Ci(O=i#i ncludeusing namespace std;const int NUM = 5;double distancel(

7、int a，int bint cdouble dNUMjint start) int ij;int k;double mindistance;int pointNUM;int eNUMNUM;if(c=0)/若是点经过空集到达起点则返回该点到起点的距离return dastart;elsefor(i=0;ic;i+)pointi=bi;k=0;for(j=0;jc;j+)if(i!勺)eik=bj;k+;/拆分该点到达起点所需经过的集合该点的下点到达起点所需经过的集合mindistance=distancel(point0，e0sC-ld,start)+dapoint0 ;for(i=0;i

8、(distance (po int i+l，ei+：L，c-：l，d,s tart)+da pointi+l)mindistance二distancel(pointi+l，ei+l,c-ld，start)+dap ointi+l;return mindistance;/求最小值double distance(int aint b，intdouble dNUM/*所有用的 d都是现成的那个a*/,int start)int ij;int k;double mindistance;int pointNUM;/*/int eNUMNUM;if(c=0)coutstart;return dastart

9、;elsefor(i=0;ic;i+)pointi=bi;k=0;for(j=0;jc;j+)eik=bj; /*节点方阵，冗余的*/k+;k=0;min dis tance=dis tan cel(po int k，ek,c-:lsd丿 star t) +da po irrtk ；/假定下一层的最短路径就是p0以及其对应的路径矩阵ekfor(i=0;i(dis t ancel( point i+1, ei+lIds tart) +dapointi+l)k=i+l;mindistance二distancel(pointk ,ek ,c-10start) +da point k；cout point k11;return distance(pointk，ekc-ld start) +da pointk;void main()int i,j;int start =4;/设置起点double aNUMNUM;int bNUM-l;ifstrearn