用分支限界算法解决旅行商问题.docx
《用分支限界算法解决旅行商问题.docx》由会员分享，可在线阅读，更多相关《用分支限界算法解决旅行商问题.docx（11页珍藏版）》请在冰点文库上搜索。
用分支限界算法解决旅行商问题
//求解旅行商问题的分枝限界算法
#include
#include
#include
#defineTRUE
（1）
#defineFALSE（0）
#defineMAX_CITIES（10）
#defineINFINITY （999）
#defineIINFINITY
typedefintbool;
/*定义边结构*/
typedefstruct_EDGE{
inthead;
inttail;
}EDGE;
/*定义路径结构*/
typedefstruct_PATH{
EDGEedge[MAX_CITIES];
int edgesNumber;
}PATH;
/*定义花费矩阵结构*/
typedefstruct_MATRIX{
intdistance[MAX_CITIES][MAX_CITIES];
intcitiesNumber;
}MATRIX;
/*定义树结点*/
typedefstruct_NODE{
intbound; /*相应于本结点的花费下界*/
MATRIXmatrix; /*当前花费矩阵*/
PATHpath; /*已经选定的边*/
struct_NODE*left; /*左枝*/
struct_NODE*right; /*右枝*/
}NODE;
intSimplify（MATRIX*）;
EDGESelectBestEdge（MATRIX）;
MATRIXLeftNode（MATRIX,EDGE）;
MATRIXRightNode（MATRIX,EDGE,PATH）;
PATHAddEdge（EDGE,PATH）;
PATHBABA（NODE）;
PATHMendPath（PATH,MATRIX）;
intMatrixSize（MATRIX,PATH）;
voidShowMatrix（MATRIX）;
voidShowPath（PATH,MATRIX）;
main（）
{
PATHpath;
NODEroot={
0,/*花费下界*/
{{{I,1,2,7,5},/*花费矩阵*/
{1,I,4,4,3},
{2,4,I,1,2},
{7,4,1,I,3},
{5,3,2,3,I}},5},/*城市数目*/
{{0},0},/*经历过的路径*/
NULL,NULL/*左枝与右枝*/
};
/*归约，建立根结点*/
root.bound+=Simplify（&root.matrix）;
/*进入搜索循环*/
path=BABA（root）;
ShowPath（path,root.matrix）;
return0;
}
/*
*算法主搜索函数，Branch-And-BoundAlgorithmSearch
* root是当前的根结点，已归约，数据完善
*/
PATHBABA（NODEroot）
{
inti;
staticintminDist=INFINITY;
staticPATHminPath;
EDGEselectedEdge;
NODE*left,*right;
puts（"CurrentRoot:
\n------------"）;
ShowMatrix（root.matrix）;
printf（"RootBound:
%d\n",root.bound）;
/*如果当前矩阵大小为2，说明还有两条边没有选，而这两条边必定只能有一种组合，
*才能构成整体回路，所以事实上所有路线已经确定。
*/
if（MatrixSize（root.matrix,root.path）==2）{
if（root.bound minDist=root.bound;
minPath=MendPath（root.path,root.matrix）;
getch（）;
return（minPath）;
}
}
/*根据左下界尽量大的原则选分枝边*/
selectedEdge=SelectBestEdge（root.matrix）;
printf（"SelectedEdge:
（%d,%d）\n",selectedEdge.head+1,selectedEdge.tail+1）;
/*建立左右分枝结点*/
left=（NODE*）malloc（sizeof（NODE））;
right=（NODE*）malloc（sizeof（NODE））;
if（left==NULL||right==NULL）{
fprintf（stderr,"Errormalloc.\n"）;
exit（-1）;
}
/*初始化左右分枝结点*/
left->bound=root.bound;/*继承父结点的下界*/
left->matrix=LeftNode（root.matrix,selectedEdge）;/*删掉分枝边*/
left->path=root.path;/*继承父结点的路径，没有增加新边*/
left->left=NULL;
left->right=NULL;
right->bound= root.bound;
right->matrix=RightNode（root.matrix,selectedEdge,root.path）;/*删除行列和回路边*/
right->path=AddEdge（selectedEdge,root.path）;/*加入所选边*/
right->left=NULL;
right->right=NULL;
/*归约左右分枝结点*/
left->bound+=Simplify（&left->matrix）;
right->bound+=Simplify（&right->matrix）;
/*链接到根*/
root.left=left;
root.right=right;
/*显示到监视器*/
puts（"RightBranch:
\n------------"）;
ShowMatrix（right->matrix）;
puts（"LeftBranch:
\n-----------"）;
ShowMatrix（left->matrix）;
/*如果右结点下界小于当前最佳答案，继续分枝搜索*/
if（right->bound BABA（*right）;
}
/*否则不搜索，因为这条枝已经不可能产生更佳路线*/
else{
printf（"CurrentminDistis%d,",minDist）;
printf（"RightBranch'sBound（=%d）.\n",right->bound）;
printf（"Thisbranchisdead.\n"）;
}
/*如果右结点下界小于当前最佳答案，继续分枝搜索*/
if（left->bound BABA（*left）;
}
/*否则不搜索，因为这条枝已经不可能产生更佳路线*/
else{
printf（"CurrentminDistis%d,",minDist）;
printf（"LeftBranch'sBound（=%d）.\n",left->bound）;
printf（"Thisbranchisdead.\n"）;
}
printf（"Thebestanswernowis%d\n",minDist）;
return（minPath）;
}
/*修补路径*/
PATHMendPath（PATHpath,MATRIXc）
{
introw,col;
EDGEedge;
intn=c.citiesNumber;
for（row=0;row edge.head=row;
for（col=0;col edge.tail=col;
if（c.distance[row][col]==0）{
path=AddEdge（edge,path）;
}
}
}
returnpath;
}
/*归约费用矩阵，返回费用矩阵的归约常数*/
intSimplify（MATRIX*c）
{
introw,col,min_dist,h;
intn=c->citiesNumber;
h=0;
/*行归约*/
for（row=0;row /*找出本行最小的元素*/
min_dist=INFINITY;
for（col=0;col if（c->distance[row][col] min_dist=c->distance[row][col];
}
}
/*如果本行元素都是无穷，说明本行已经被删除*/
if（min_dist==INFINITY）continue;
/*本行每元素减去最小元素*/
for（col=0;col if（c->distance[row][col]!
=INFINITY）{
c->distance[row][col]-=min_dist;
}
}
/*计算归约常数*/
h+=min_dist;
}
/*列归约*/
for（col=0;col /*找出本列最小的元素*/
min_dist=INFINITY;
for（row=0;row if（c->distance[row][col] min_dist=c->distance[row][col];
}
}
/*如果本列元素都是无穷，说明本列已经被删除*/
if（min_dist==INFINITY）continue;
/*本列元素减去最小元素*/
for（row=0;row if（c->distance[row][col]!
=INFINITY）{
c->distance[row][col]-=min_dist;
}
}
/*计算归约常数*/
h+=min_dist;
}
return（h）;
}
/*搜索所有花费为零的边中最合适的，使左枝下界更大*/
EDGESelectBestEdge（MATRIXc）
{
introw,col;
intn=c.citiesNumber;
intmaxD;
EDGEbest,edge;
/*所用函数声明*/
intD（MATRIX,EDGE）;
maxD=0;
for（row=0;row for（col=0;col edge.head=row;
edge.tail=col;
if（!
c.distance[row][col]&&maxD maxD=D（c,edge）;
best=edge;
}
}
}
return（best）;
}
/*计算如果选edge作为分枝边，左枝（不含edge）下界的增量*/
intD（MATRIXc,EDGEedge）
{
introw,col,dRow,dCol;
intn=c.citiesNumber;
dRow=INFINITY;
for（col=0;col if（dRow=edge.tail）{
dRow=c.distance[edge.head][col];
}
}
dCol=INFINITY;
for（row=0;row if（dCol=edge.head）{
dCol=c.distance[row][edge.tail];
}
}
return（dRow+dCol）;
}
/*删掉所选分枝边*/
MATRIXLeftNode（MATRIXc,EDGEedge）
{
c.distance[edge.head][edge.tail]=INFINITY;
returnc;
}
/*删除行列和回路边后的矩阵*/
MATRIX RightNode（MATRIXc,EDGEedge,PATHpath）
{
introw,col;
intn=c.citiesNumber;
EDGEloopEdge;
/*声明所需要的求回路边函数*/
EDGELoopEdge（PATH,EDGE）;
for（col=0;col c.distance[edge.head][col]=INFINITY;
for（row=0;row c.distance[row][edge.tail]=INFINITY;
loopEdge=LoopEdge（path,edge）;
c.distance[loopEdge.head][loopEdge.tail]=INFINITY;
return（c）;
}
/*计算回路边的函数
*除了加入的新边，当前结点路线集合中还可能包含一些已经选定的边，这些边构成一条或
*几条路径，为了不构成回路，必须使其中包含新边的路径头尾不能相连，本函数返回这个
*头尾相连的边，以便把这个回路边的长度设成无穷。
*/
EDGELoopEdge（PATHpath,EDGEedge）
{
inti,j;
EDGEloopEdge;
/*最小的回路边*/
loopEdge.head=edge.tail;
loopEdge.tail=edge.head;
/*寻找回路边的头端点，即包含新边的路径的尾端点*/
for（i=0;i for（j=0;j if（loopEdge.head==path.edge[j].head）{
/*扩大回路边*/
loopEdge.head=path.edge[j].tail;
break;
}
}
}
/*寻找回路边的尾端点，即包含新边的路径的头端点*/
for（i=0;i for（j=0;j if（loopEdge.tail==path.edge[j].tail）{
/*扩大回路边*/
loopEdge.tail=path.edge[j].head;
升级会员 