TSP问题算法分析
T S P问题算法分析集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289-
算法第二次大作业
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分支界限法
#include
#include
#defineNoEdge1000
structMinHeapNode
{
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->cc>hn->cc)
{
hn->next=tmp;
head->next=hn;
fq=head->next;/*链表只有一个元素的情况*/
}else
{
for(;tmp!=NULL;)
{
if(tmp->next!=NULL&&tmp->cc>hn->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] 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;i E->x[i]=i+1; E->s=0; E->cc=0; E->rcost=MinSum; E->next=0;//初始化当前扩展节点 intbestc=NoEdge;/*记录当前最小值*/ //搜索排列空间树 while(E->s {//非叶结点 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==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);/*将该页节点插入到优先队列中*/ }else free(E->x);//该页节点不满足条件舍弃扩展结点 }else {/*产生当前扩展结点的儿子结点 当s 展结点所相应的路径是x[0:s]， 其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且 (x[s]，x[i])是所给有向图G中的一条边。 对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。 当lcost for(inti=E->s+1;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(b {//子树可能含最优解,结点插入最小堆 MinHeapNode*N; N=(MinHeapNode*)malloc(sizeof(MinHeapNode)); N->x=newint[n]; for(intj=0;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;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]=0; a[2][3]=6; a[2][4]=4; a[2][5]=3; a[3][1]=1; a[3][2]=6; a[3][3]=0; a[3][4]=8; a[3][5]=2; a[4][1]=5; a[4][2]=4; a[4][3]=8; a[4][4]=0; a[4][5]=5; a[5][1]=7; a[5][2]=3; a[5][3]=2; a[5][4]=5; a[5][5]=0; //prev=(int*)malloc(sizeof(int)*(n+1)); int*v=(int*)malloc(sizeof(int)*(n+1));//MaxLoading(w,c,n); for(i=1;i<=n;i++) v[i]=0; bestc=BBTSP(v); printf("\n"); printf("最优路径为"); for(i=1;i<=n;i++) fprintf(stdout,"%c\t",v[i]+64); fprintf(stdout,"\n"); fprintf(stdout,"总路程为\n",bestc); return0; } 3.2A*算法 #include"stdio.h" constintmax=9999; constintax=50; intisbest(inti,intbestpath[],intp)//检测改节点是否已经加入bestpath[]中 { for(intk=1;k<=p;k++) { if(i==bestpath[k]) break; } if(k!=p+1)//新测试节点在a[]中 return1; else return0; } voidmain() { intmin=max; intminf=max; intnum;//城市数量 intmat[ax][ax];//城市间距离 intbestpath[ax];//最佳路径 intf=0,g=0,h=0; intff[ax];//依次求每个城市的f值 intgg[ax];//城市的g值 printf("城市个数为："); scanf("%d",&num); printf("城市间的距离为：\n");//输入各城市间距离的矩阵 for(inti=0;i for(intj=0;j scanf("%d",&mat[i][j]); bestpath[0]=0;//起点为0，即城市A for(intp=0;p { for(intkk=0;kk ff[kk]=max;//便于后面求最小值 for(i=1;i { if(isbest(i,bestpath,p))//该点已经在bestpath[]中的话，忽略 continue; else//计算该点的g值 gg[i]=g+mat[bestpath[p]][i];//i点的g值 for(intm=0;m { if(isbest(m,bestpath,p))//该点已经在bestpath[]中的话，忽略 continue; for(intt=m+1;t { if(isbest(t,bestpath,p)) continue; if(m!=0||t!=i||p==num-2)//不是最后一个点的话，不算A点到这个点长度 if(mat[m][t] min=mat[m][t]; } } h=min*(num-p-1);//h值 ff[i]=gg[i]+h;//第i个节点的f值 min=max;//重新赋值最大，以便下次循环 } for(i=0;i { if(ff[i] { minf=ff[i]; bestpath[p+1]=i; } } minf=max;//重新赋值最大，以便下次循环 g=g+mat[bestpath[p]][bestpath[p+1]];//更新g值} printf("最优路径为:"); for(i=0;i printf("%c",bestpath[i]+65); printf("A\n"); printf("总路程为:"); intsum=0; for(i=0;i sum=sum+mat[bestpath[i]][bestpath[i+1]]; sum=sum+mat[bestpath[num-1]][0];//总路程最后一个城市要回到A，所以加上其距离 printf("%d\n",sum); } 四．结果截图 4.1分支界限法 4.2A*算法