深搜減枝旅行家算法

1、算法思想：使用Floyd算法求出兩點(diǎn)間最小距離，算法使用深度優(yōu)先搜索，在搜索到可行結(jié)果之后，使用Floyd條件，進(jìn)行算法剪枝。剪枝條件：(curdis+disnodei+mindisi49>=disbound)|(mincosti49+costnodei+curcost>=costbound) 如果當(dāng)前距離+本次搜到的節(jié)點(diǎn)i到node的距離+i到城市50的最小距離大于我們的最小花費(fèi)，則必然剪枝，costbound為1500，題目設(shè)定條件運(yùn)行結(jié)果：程序代碼：/ branch.cpp : Defines the entry point for the console applicati

2、on./#include "stdafx.h"#include<iostream>#include<fstream>using 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;k<n;k+) fo

3、r (int i=0;i<50;i+) for (int j=0;j<50;j+) if (dik+dkj<dij) 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

4、 (int i=0;i<50;i+) if (distql.curi!=maxint) if (ql.dis+mindisi49>=disbound)|(ql.dis+mincosti49>=costbound) */void DFS(int node,int curdis,int curcost,int path,int step) if (node=49) if (curdis<disbound) for (int i=0;i<step;i+) bestpathi=pathi; bestpathstep=-1; disbound=curdis;/ cout&l

5、t;<disbound<<" " / for (int s=0;s<step;s+) cout<<paths<<" " / cout<<" "<<endl; return; if (node=47) int a=1;for (int i=0;i<50;i+) if (i=49) int c=1; if (disnodei>=maxint) continue; if (curdis+disnodei+mindisi49>=disbound)|(mi

6、ncosti49+costnodei+curcost>=costbound) continue; int flag=0; for (int j=0;j<step;j+) if (pathj=i) flag=1; if (flag=1) continue; pathstep=i; step+; / if (pathi!=0) continue; / for (int i=0;i<step;i+)/ cout<<pathi<<" " cout<<endl;/ cout<<curdis<<endl; D

7、FS(i,curdis+disnodei,curcost+costnodei,path,step); step-; pathstep=-1; int main() fstream f; f.open("m1.txt",ios:in); for (int i=0;i<50;i+) for(int j=0;j<50;j+) f>>disij; disii=0; mindisij=disij; f.close(); f.open("m2.txt",ios:in); for (int i=0;i<50;i+) for(int j=0;j<50;j+) f>>costij; 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<<"1 " while (bestpathi!=-1) cout<<bestpathi+1<<" " i+; c