TSP问题算法分析

算法第二次大作业TSP问题算法分析021251班王昱（02125029）一．问题描述“TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。二．算法描述2.1分支界限法2.1.1算法思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2.1.2算法设计说明设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即：bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn)若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值bound(x1,…,xn)。2.2A*算法算法思想对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有f*(n)=g*(n)+h*(n)。假设f函数是对f*函数的一种估计,并有f(n)=g(n)+h(n)，其中g函数是对g*的估计，h函数是对h*的一种估计。f(n)包括两个部分，其中g(n)表示到达n节点时，已付出代价的估计；而h(n)表示从n节点到达目标节点ti将要付出代价的估计。按f(n)=g*(n)+h*(n)的值来排序ff表的节点，f值小者优先。通常称这种算法为A算法。在A算法的基础上，进一步限制h(n)函数，使得搜索图中的每一个节点n，能满足h(n)=h*(n)、称h函数取h*的下界。这种算法叫A*算法。对ff里的每一个节点做评估函数F分为两部分G和H：假设从A城市走到X城市，又走到Y城市，所以G可表示为：G=A到X的距离+X到Y的距离；未走的的城市数=（总城市数+1）-目前城市的层数。为什得加1，因为最后得走回初始城市，所以总路径的城市数为总城市数+1。H=未走的城市数×目前的最小距离；F=G+H;计算ff表里每个节点的F值，F值最小的节点作为活路径，把它加到bestpath中。三．算法代码3.1分支界限法#includestdio.h#includemalloc.h#defineNoEdge1000structMinHeapNode{intlcost;//子树费用的下界intcc;//当前费用intrcost;//x[s:n-1]中顶点最小出边费用和ints;//根节点到当前节点的路径为x[0:s]int*x;//需要进一步搜索的顶点是//x[s+1:n-1]structMinHeapNode*next;};intn;//图G的顶点数int**a;//图G的邻接矩阵//intNoEdge;//图G的无边标记intcc;//当前费用intbestc;//当前最小费用MinHeapNode*head=0;/*堆头*/MinHeapNode*lq=0;/*堆第一个元素*/MinHeapNode*fq=0;/*堆最后一个元素*/intDeleteMin(MinHeapNode*&E){MinHeapNode*tmp=NULL;tmp=fq;//w=fq-weight;E=fq;if(E==NULL)return0;head-next=fq-next;/*一定不能丢了链表头*/fq=fq-next;//free(tmp);return0;}intInsert(MinHeapNode*hn){if(head-next==NULL){head-next=hn;//将元素放入链表中fq=lq=head-next;//一定要使元素放到链中}else{MinHeapNode*tmp=NULL;tmp=fq;if(tmp-cchn-cc){hn-next=tmp;head-next=hn;fq=head-next;/*链表只有一个元素的情况*/}else{for(;tmp!=NULL;){if(tmp-next!=NULL&&tmp-cchn-cc){hn-next=tmp-next;tmp-next=hn;break;}tmp=tmp-next;}}if(tmp==NULL){lq-next=hn;lq=lq-next;}}return0;}intBBTSP(intv[]){//解旅行售货员问题的优先队列式分支限界法/*初始化最优队列的头结点*/head=(MinHeapNode*)malloc(sizeof(MinHeapNode));head-cc=0;head-x=0;head-lcost=0;head-next=NULL;head-rcost=0;head-s=0;int*MinOut=newint[n+1];/*定义定点i的最小出边费用*///计算MinOut[i]=顶点i的最小出边费用intMinSum=0;//最小出边费用总合for(inti=1;i=n;i++){intMin=NoEdge;/*定义当前最小值*/for(intj=1;j=n;j++)if(a[i][j]!=NoEdge&&/*当定点i,j之间存在回路时*/(a[i][j]Min||Min==NoEdge))/*当顶点i,j之间的距离小于Min*/Min=a[i][j];/*更新当前最小值*/if(Min==NoEdge)returnNoEdge;//无回路MinOut[i]=Min;//printf(%d\n,MinOut[i]);/*顶点i的最小出边费用*/MinSum+=Min;//printf(%d\n,MinSum);/*最小出边费用的总和*/}MinHeapNode*E=0;E=(MinHeapNode*)malloc(sizeof(MinHeapNode));E-x=newint[n];//E.x=newint[n];for(inti=0;in;i++)E-x[i]=i+1;E-s=0;E-cc=0;E-rcost=MinSum;E-next=0;//初始化当前扩展节点intbestc=NoEdge;/*记录当前最小值*///搜索排列空间树while(E-sn-1){//非叶结点if(E-s==n-2){//当前扩展结点是叶结点的父结点/*首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点*/if(a[E-x[n-2]][E-x[n-1]]!=NoEdge&&/*当前要扩展和叶节点有边存在*/a[E-x[n-1]][1]!=NoEdge&&/*当前页节点有回路*/(E-cc+a[E-x[n-2]][E-x[n-1]]+a[E-x[n-1]][1]bestc/*该节点相应费用小于最小费用*/||bestc==NoEdge)){bestc=E-cc+a[E-x[n-2]][E-x[n-1]]+a[E-x[n-1]][1];/*更新当前最新费用*/E-cc=bestc;E-lcost=bestc;E-s++;E-next=NULL;Insert(E);/*将该页节点插入到优先队列中*/}elsefree(E-x);//该页节点不满足条件舍弃扩展结点}else{/*产生当前扩展结点的儿子结点当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。*/for(inti=E-s+1;in;i++)if(a[E-x[E-s]][E-x[i]]!=NoEdge){/*当前扩展节点到其他节点有边存在*///可行儿子结点intcc=E-cc+a[E-x[E-s]][E-x[i]];/*加上节点i后当前节点路径*/intrcost=E-rcost-MinOut[E-x[E-s]];/*剩余节点的和*/intb=cc+rcost;//下界if(bbestc||bestc==NoEdge){//子树可能含最优解,结点插入最小堆MinHeapNode*N;N=(MinHeapNode*)malloc(sizeof(MinHeapNode));N-x=newint[n];for(intj=0;jn;j++)N-x[j]=E-x[j];N-x[E-s+1]=E-x[i];N-x[i]=E-x[E-s+1];/*添加当前路径*/N-cc=cc;/*更新当前路径距离*/N-s=E-s+1;/*更新当前节点*/N-lcost=b;/*更新当前下界*/N-rcost=rcost;N-next=NULL;Insert(N);/*将这个可行儿子结点插入到活结点优先队列中*/}}free(E-x);}//完成结点扩展DeleteMin(E);//取下一扩展结点if(E==NULL)break;//堆已空}if(bestc==NoEdge)returnNoEdge;//无回路for(inti=0;in;i++)v[i+1]=E-x[i];//将最优解复制到v[1:n]while(true){//释放最小堆中所有结点free(E-x);DeleteMin(E);if(E==NULL)break;}returnbestc;}intmain(){n=0;inti=0;//FILE*in,*out;//in=fopen(input.txt,r);//out=fopen(output.txt,w);//if(in==NULL||out==NULL)//{//printf(没有输入输出文件\n);//return1;//}//fscanf(in,%d,&n);n=5;a=(int**)malloc(sizeof(int*)*(n+1));for(i=1;i=n;i++){a[i]=(int*)malloc(sizeof(int)*(n+1));}//for(i=1;i=n;i++)//for(intj=1;j=n;j++)////fscanf(in,%d,&a[i][j]);//a[i][j]=1;a[1][1]=0;a[1][2]=6;a[1][3]=1;a[1][4]=5;a[1][5]=7;a[2][1]=6;a[2][2]