实验3旅行商问题.doc

实验3 旅行商问题 一：问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条 从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。 二：问题分析 设顶点集V,S为V的子集。顶点i通过顶点集S（i∈V-S）的点到达顶点0的最短路径 长度为min(i,S),则有递归式： min(i,S)=min{di,j+min(j,S-{j})}(j∈S,di,j为顶点i到顶点j的距离) 从而问题的解为min(0,V-{0})(即顶点0通过集合V-{0}的点到达顶点0的最短回路长 度)由于求解的时候需要用到子问题min(j,S-{j}),所以可以用动态规划求解.从S=?开始，依次对|S|=1,2,┅,n-1计算 三：算法描述 1：数据结构描述 1) 考虑到要做图形演示，需要记录min(i,s)顶点i是通过集合s中哪个顶点得到的.故用nextpoint＝j表示i是通过集合s中的点j得到min(i,s). 2) 同时需要记录集合s中有哪些顶点,所有用choose数记录这些顶点.choose[k]=’1’表示顶点 k∈s.choose[k]=’0’表示顶点k不属于s.(为了便于比较，这里choose数组用char类型). 用min表示min(i,s); 如果集合s有m个元素(|s|=m),则s有中选择.故用指针next指向下一个|s|=k的集合s. 综上所述，有结构类型： struct vertex { char choose[MAX]; //MAX定义为最大的顶点数 int min; int nextpoint; struct vertex *next; } 分配一个二维指针数组struct vertex *g[MAX][MAX].g[i][j]记录着顶点i通过大小为|s|=j的集合s到达顶点0的信息. 另外一个结构: struct point { double x,y; }; 用于记录各顶点的坐标，以便进行图形演示. 2:具体算法 1) choose_s(int size,int k,char s[MAX],int n,struct vertex *g[MAX][MAX],int const_size) 该算法进行选择所有大小为|S|=const_size的集合S.s数组记录了这些被选中的顶点.然后调用函数 i_s_v0_g() 对任意顶点i∈v-s计算min(i,S). 2) i_s_v0_g(int i,char s[MAX],struct vertex *g[MAX][MAX],int n,int const_size) 该算法用struct vertex* temp记录min=min(i,S)=min{di,j+min(j,S-{j})}，nextpoint和choose[]=s[].然后将temp加入到g[i][const_size]链中. 算法利用到函数int getmin()返回min(j,s-{j}) 3) int getmin(int j,int n,char s[MAX],struct vertex *g[MAX][MAX],int const_size) 该算法通过查找g[j][const_size]链中的节点temp_recrd-choose[]==s[],然后返回temp-min(即返回min(j,s-{j})) 3：图形算法 算法 findconnectpoint 通过struct vertex *g[][]中记录的信息求最短路径包含的边.其中connect[i]=k和connect[i+1]=m表示最短回路经过边e(k,m). 算法 x_y_vi（）计算顶点i的坐标，存于 p[i]中.其中数组p是一个struct point 类型的结构. 算法printgraph（）利用数组p和数组connect打印最短旅行商回路. 注：绘图使用了那个简单图形函数库里面的图形函数. 四：实验结果分析 1）TSP4.txt 最短回路：25 TSP6.txt 最短回路：175 TSP8.txt 最短回路：242 TSP10.txt 最短回路：279 TSP15.txt 最短回路：371 下图为TSP