深搜减枝旅行家算法

《深搜减枝旅行家算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法思想：使用Floyd算法求出两点间最小距离，算法使用深度优先搜索，在搜索到可行结果之后，使用Floyd条件，进行算法剪枝。剪枝条件：((curdis+dis[node][i]+mindis[i][49]>=disbound)

2、

3、(mincost[i][49]+cost[node][i]+curcost>=costbound))如果当前距离+本次搜到的节点i到node的距离+i到城市50的最小距离大于我们的最小花费，则必然剪枝，costbound为1500，题目设定条件运行结果：程序代码：//branch.cpp:Definestheentrypointforthecon

4、soleapplication.//#include"stdafx.h"#include#includeusingnamespacestd;constintmaxint=9999;intdis[50][50]={0};intcost[50][50]={0};intmindis[50][50]={0};intmincost[50][50]={0};intdisbound=9999;intcostbound=1500;intbestpath[50]={-1};voidfloyd(intd[50][50]){intn=50;for(intk=

5、0;k

6、tbound=1500;while(l<=r){for(inti=0;i<50;i++)if(dist[q[l].cur][i]!=maxint){if(q[l].dis+mindis[i][49]>=disbound)

7、

8、(q[l].dis+mincost[i][49]>=costbound)}}}*/voidDFS(intnode,intcurdis,intcurcost,intpath[],intstep){if(node==49){if(curdis

9、th[step]=-1;disbound=curdis;//cout<=maxint)continue;if((curdis+dis[node][i]+mindis[i][49]>=disbound)

10、

11、(mincost[i][49]+cost[node][i]+

12、curcost>=costbound))continue;intflag=0;for(intj=0;j

13、ath[step]=-1;}}intmain(){fstreamf;f.open("m1.txt",ios::in);for(inti=0;i<50;i++)for(intj=0;j<50;j++){f>>dis[i][j];dis[i][i]=0;mindis[i][j]=dis[i][j];}f.close();f.open("m2.txt",ios::in);for(inti=0;i<50;i++)for(intj=0;j<50;j++){f>>cost[i][j];mincost[i][j]=cost[i]