旅行商问题.docx

旅行商问题.docx

《旅行商问题.docx》由会员分享，可在线阅读，更多相关《旅行商问题.docx（16页珍藏版）》请在冰点文库上搜索。

旅行商问题

算法设计与分析实验报告

实验三旅行商问题

院系：

班级：

计算机科学与技术

学号：

姓名：

任课教师：

成绩：

湘潭大学

2016年5月

实验三旅行商问题

一.实验内容

分别编程实现回溯法和分支限界法求TSP问题的最优解，分析比较两种算法的时间复杂度并验证分析结果。

二．实验目的

1、掌握回溯法和分支限界法解决问题的一般步骤，学会使用回溯法和分支限界法解决实际问题；

2、理解回溯法和分支限界法的异同及各自的适用范围。

三.算法描述

旅行商问题的回溯法算法可描述如下：

Template

ClassTraveling{

friendTypeTSP（int**,int[],int,Type）;

Private;

VoidBacktrack（inti）;

Intn,//图G的顶点数

*x;//当前解

*bestx;//当前最优解

Type**a,//图G的邻接矩阵

cc,//当前费用

bestc，//当前最优解

NoEdge;//无边标记

}；

Template

VoidTraveling:

:

backtrack（inti）

{if（i==n）{

if（a[x[n-1]][x[n]]!

=NoEdge&&a[x[n]][1]!

=NoEdge&&（cc+a[x[n-1]][x[n]]+a[x[n]][1]+a[x[n]][1]

for（intj=1;j<=n;j++）bestx[j]=x[j];

bestc==cc+a[x[n-1]][x[n]]+a[x[n]][1]};

}else{

For（intj=i;j<=n;j++）

//是否可进入x[j]子树？

If（a[x[i-1]][x[j]]!

=NoEdge&&（cc+a[x[i-1]][x[j]]

//搜素子树

Swap（x[i],x[j]）;

cc+=a[x[i-1]][x[i]];

Backtrack（i+1）;

cc-=a[x[i-1]][x[i]];

Swap（x[i],x[j]）;

}

}

}

Template

TypeTSP（Type**a,intv[],intn,TypeNoEdge）

{TravelingY;

//初始化Y

Y.x=newint[n+1];

//置x为单位排列

For（inti=1;i<=n;i++）

Y.x[i]=i;

Y.a=a;

Y.n=n;

Y.bestc=NoEdge;

Y.bestx=v;

Y.cc=0;

Y.NoEdge=NoEdge;

//搜索x[2:

n]的全排列

Y.Backtrack

（2）;

Delete[]Y.x;

ReturnY.bestc;

}

算法效率：

如果不考虑更新bestx所需的计算时间，则Backtrack需要O（（n-1）！

）计算时间。

由于算法Backtrack在最坏情款下可能需要更新当前最优解O（（n-1）！

）次，每次更新需O（n）计算时间，从而整个算法的计算时间复杂性为O（n！

）。

旅行商问题的分支界限法算法可描述如下：

使用优先队列来存储活节点，优先队列中的每个活节点都存储从根到该活节点的相应路径。

具体算法可描述如下：

Template

ClassMinHeapNode{

firendTraveling;

Public:

OperatorType（）const{returnlcost;}

Private:

Typelcost,//子树费用的下界

cc,//当前费用

rcost；//x[s:

n-1]中定点最小出边费用和

Ints,//根节点到当前节点的路径为x[0:

s]

*x;//需要进一步搜索的顶点是x[s+1:

n-1]

};

四.算法实现

源程序代码

/*回溯法*/

#include

#include

#defineN5

doublecc,//当前路径费用

bestc;//当前最优解费用

doublea[N+1][N+1];//邻接矩阵，存放图的信息

intbestx[N+1];//当前最优解

intx[N+1];//当前解

voidinputAjac（）

{

inti,j;

for（i=1;i<=N;i++）

{for（j=i+1;j<=N;j++）

{

printf（"请输入第%d个城市到第%d个城市所需路费为：

",i,j）;

scanf（"%lf",&a[i][j]）;

a[j][i]=a[i][j];

}

}

}

voidbacktrack（inti）

{

if（i==N）

{

if（a[x[N-1]][x[N]]>0.0&&a[x[N]][x[1]]>0.0）

{

if（bestc<0.0||bestc>cc+a[x[N-1]][x[N]]+a[x[N]][x[1]]）

{

intj;

for（j=1;j<=N;j++）

{

bestx[j]=x[j];

bestc=cc+a[x[N-1]][x[N]]+a[x[N]][x[1]];

}

}

}

}

else

{

intj;

for（j=i;j<=N;j++）

{

if（a[x[i-1]][x[j]]>0.0）

{

if（bestc<0.0||bestc>cc+a[x[i-1]][x[j]]+a[x[j]][x[1]]）

{

inttemp;

cc+=a[x[i-1]][x[j]];

temp=x[i];

x[i]=x[j];

x[j]=temp;

backtrack（i+1）;

temp=x[i];

x[i]=x[j];

x[j]=temp;

cc-=a[x[i-1]][x[j]];

}

}

}

}

}

doubletsp（）

{

inti;

for（i=1;i<=N;i++）

{x[i]=i;}

cc=0.0,bestc=-1.0;

inputAjac（）;

backtrack

（2）;

returnbestc;

}

voidoutput（）

{

inti;

for（i=1;i<=N;i++）

{

printf（"%4d",bestx[i]）;

}

//printf（"\n"）;

}

voidmain（）

{

doublestart,finish;

start=clock（）;//取开始时间

printf（"城市个数：

5\n"）;

printf（"走%d个城市最少路费为：

%lf\n",N,tsp（））;

printf（"路径:

"）;

output（）;

printf（"1\n"）;

finish=clock（）;

printf（"所需时间%fms\n",（finish-start））;

}

/*分支界限法*/

#include

#include

#include

usingnamespacestd;

#defineMAX_CITY_NUMBER10

#defineMAX_COST10000000

intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];

intCity_Size;

intBest_Cost;

intBest_Cost_Path[MAX_CITY_NUMBER];

typedefstructNode{

intlcost;

intcc;

intrcost;

ints;

intx[MAX_CITY_NUMBER];

structNode*pNext;

}Node;

typedefstructMiniHeap{

Node*pHead;

}MiniHeap;

voidInitMiniHeap（MiniHeap*pMiniHeap）{

pMiniHeap->pHead=newNode;

pMiniHeap->pHead->pNext=NULL;

}

voidput（MiniHeap*pMiniHeap,Nodenode）{

Node*next;

Node*pre;

Node*pinnode=newNode;

pinnode->cc=node.cc;

pinnode->lcost=node.lcost;

pinnode->pNext=node.pNext;

pinnode->rcost=node.rcost;

pinnode->s=node.s;

pinnode->pNext=NULL;

for（intk=0;k

pinnode->x[k]=node.x[k];

}

pre=pMiniHeap->pHead;

next=pMiniHeap->pHead->pNext;

if（next==NULL）{

pMiniHeap->pHead->pNext=pinnode;

}else{

while（next!

=NULL）{

if（（next->lcost）>（pinnode->lcost））{

pinnode->pNext=pre->pNext;

pre->pNext=pinnode;

break;

}

pre=next;

next=next->pNext;

}

pre->pNext=pinnode;

}

}

Node*RemoveMiniHeap（MiniHeap*pMiniHeap）{

Node*pnode=NULL;

if（pMiniHeap->pHead->pNext!

=NULL）{

pnode=pMiniHeap->pHead->pNext;

pMiniHeap->pHead->pNext=pMiniHeap->pHead->pNext->pNext;

}

returnpnode;

}

voidTraveler（）{

inti,j;

inttemp_x[MAX_CITY_NUMBER];

Node*pNode=NULL;

intminiSum;

intminiOut[MAX_CITY_NUMBER];

MiniHeap*heap=newMiniHeap;

InitMiniHeap（heap）;

miniSum=0;

for（i=0;i

miniOut[i]=MAX_COST;

for（j=0;j

if（City_Graph[i][j]>0&&City_Graph[i][j]

miniOut[i]=City_Graph[i][j];

}

}

if（miniOut[i]==MAX_COST）{

Best_Cost=-1;

return;

}

miniSum+=miniOut[i];

}

for（i=0;i

Best_Cost_Path[i]=i;

}

Best_Cost=MAX_COST;

pNode=newNode;

pNode->lcost=0;

pNode->cc=0;

pNode->rcost=miniSum;

pNode->s=0;

pNode->pNext=NULL;

for（intk=0;k

pNode->x[k]=Best_Cost_Path[k];

}

put（heap,*pNode）;

while（pNode!

=NULL&&（pNode->s）

for（intk=0;k

Best_Cost_Path[k]=pNode->x[k];

}

if（（pNode->s）==City_Size-2）{

intedge1=City_Graph[（pNode->x）[City_Size-2]][（pNode->x）[City_Size-1]];

intedge2=City_Graph[（pNode->x）[City_Size-1]][（pNode->x）[0]];

if（edge1>=0&&edge2>=0&&（pNode->cc+edge1+edge2）

Best_Cost=pNode->cc+edge1+edge2;

pNode->cc=Best_Cost;

pNode->lcost=Best_Cost;

pNode->s++;

}

}else{

for（i=pNode->s;i

if（City_Graph[pNode->x[pNode->s]][pNode->x[i]]>=0）{

inttemp_cc=pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];

inttemp_rcost=pNode->rcost-miniOut[pNode->x[pNode->s]];

if（temp_cc+temp_rcost

for（j=0;j

temp_x[j]=Best_Cost_Path[j];

}

temp_x[pNode->x[pNode->s+1]]=Best_Cost_Path[i];

temp_x[i]=Best_Cost_Path[pNode->s+1];

Node*pNextNode=newNode;

pNextNode->cc=temp_cc;

pNextNode->lcost=temp_cc+temp_rcost;

pNextNode->rcost=temp_rcost;

pNextNode->s=pNode->s+1;

pNextNode->pNext=NULL;

for（intk=0;k

pNextNode->x[k]=temp_x[k];

}

put（heap,*pNextNode）;

deletepNextNode;

}

}

}

}

pNode=RemoveMiniHeap（heap）;

}

}

intmain（）{

doublestart,finish;

start=clock（）;

inti,j;

printf（"城市个数：

"）;

scanf（"%d",&City_Size）;

for（i=0;i

printf（"请分别输入每个城市与其它城市的路程花费：

"）;

for（j=0;j

scanf（"%d",&City_Graph[i][j]）;

}

}

Traveler（）;

printf（"最少路费：

""%d\n",Best_Cost）;

finish=clock（）;

printf（"所需时间：

%fms\n",（finish-start））;

return1;

}

五．程序运行结果

回溯法结果截图：

分支界限法结果截图：

六．实验结果分析

回溯法算法的时间复杂度为O（n！

），分支界限发算法的时间复杂度为O（2^n）;从实验结果也可看出分支界限法所需时间少很多。

七．结论

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

  由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

分支限界法的搜索策略是：

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。