深搜减枝旅行家算法

1、算法思想：使用Floyd算法求出两点间最小距离，算法使用深度优先搜索，在搜索到可行结果之后，使用Floyd条件，进行算法剪枝。剪枝条件：(curdis+disnodei+mindisi49=disbound)|(mincosti49+costnodei+curcost=costbound) 如果当前距离+本次搜到的节点i到node的距离+i到城市50的最小距离大于我们的最小花费，则必然剪枝，costbound为1500，题目设定条件运行结果：程序代码：/ branch.cpp : Defines the entry point for the console application./#inc

2、lude stdafx.h#include#includeusing namespace std;const int maxint=9999;int dis5050=0;int cost5050=0;int mindis5050=0;int mincost5050=0;int disbound=9999;int costbound=1500;int bestpath50=-1; void floyd(int d5050) int n=50; for (int k=0;kn;k+) for (int i=0;i50;i+) for (int j=0;j50;j+) if (dik+dkjdij)

3、 dij=dik+dkj; /* struct st int cur; int pre; int dis; int cost; ;void branch(int dis,int cost,int mindis,int mincost) struct st q1000=0; q0.cur=0; q0.pre=-1; int l=0; int r=0; int disbound=9999; int costbound=1500;while (l=r) for (int i=0;i=disbound)|(ql.dis+mincosti49=costbound) */void DFS(int node

4、,int curdis,int curcost,int path,int step) if (node=49) if (curdisdisbound) for (int i=0;istep;i+) bestpathi=pathi; bestpathstep=-1; disbound=curdis;/ coutdisbound ; / for (int s=0;sstep;s+) coutpaths ; / cout endl; return; if (node=47) int a=1;for (int i=0;i=maxint) continue; if (curdis+disnodei+mi

5、ndisi49=disbound)|(mincosti49+costnodei+curcost=costbound) continue; int flag=0; for (int j=0;jstep;j+) if (pathj=i) flag=1; if (flag=1) continue; pathstep=i; step+; / if (pathi!=0) continue; / for (int i=0;istep;i+)/ coutpathi ; coutendl;/ coutcurdisendl; DFS(i,curdis+disnodei,curcost+costnodei,pat

6、h,step); step-; pathstep=-1; int main() fstream f; f.open(m1.txt,ios:in); for (int i=0;i50;i+) for(int j=0;jdisij; disii=0; mindisij=disij; f.close(); f.open(m2.txt,ios:in); for (int i=0;i50;i+) for(int j=0;jcostij; mincostij=costij; f.close(); floyd(mindis); floyd(mincost); int path50=-1; cout - endl;/ path0=0; DFS(0,0,0,path,0); int i=0; cout