动态规划法回溯法分支限界法求解TSP问题试验报告

1、TSP问题算法实验报告指导教师：季晓慧姓 名：辛瑞乾学 号：提交日期：2021 年11月目录总述动态规划法算法问题分析算法设计实现代码输入输出截图OJ提交截图算法优化分析回溯法算法问题分析算法设计实现代码输入输出截图 OJ提交截图算法优化分析分支限界法算法问题分析算法设计实现代码输入输出截图 OJ提交截图算法优化分析总述TSP问题又称为旅行商问题,是指一个旅行商要历经所有城市一次最后又 回到原来的城市,求最短路程或最小花费,解决TSP可以用好多算法,比方蛮力法,动态规划法具体的时间复杂的也各有差异,本次实验报告包含动 态规划法,回溯法以及分支限界法.动态规划法算法问题分析假设n个顶点分别用0n

2、-1的数字编号,顶点之间的代价存放在数组 mpnn中,下面考虑从顶点0出发求解TSP问题的填表形式.首先,按个 数为1、2、n-1的顺序生成1n-1个元素的子集存放在数组 x2An-1 中, 例 如 当 n=4 时 , x1=1,x2=2,x3=3,x4=1,2,x5=1,3,x6=2,3,x7=1,2,3.设数组dpn2An-1存放迭代结果,其中dpij 表示从顶点i 经过子集xj中的顶点一次且一次,最后回到出发点0的最短路径长度,动 态规划法求解TSP问题的算法如下.算法设计输入：图的代价矩阵mpnn输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度1 .初始化第0列(动

3、态规划的边界问题)for(i=1;i<n;i+)dpi0=mpi02 .依次处理每个子集数组x2An-1for(i=1;i<n;i+)if (子集xj中不包含i )对 xj中的每个元素 k,计算 dij=minmpik+dpkj-1;3 .输出最短路径长度.实现代码#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#include <algorith

4、m> #include <string> #include <vector>#include <deque>#include <list>#include <set>#include <map>#include <stack>#include <queue>#include <cctype>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#i

5、nclude <fstream>#define debug "output for debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f3f#define ll long long int#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1 using namespace std;const int Max = 100005;int n,mp2020,dp2040000;int main()(w

6、hile(scanf("%d",&n)(int ans=inf;memset(mp,0,sizeof mp);for(int i=0; i<n; i+)(for(int j=0; j<n; j+)(if(i=j)(mpij=inf;continue;int tmp;scanf("%d",&tmp);mpij=tmp;int mx=(1<<(n-1);dp00=0；for(int i=1; i<n; i+)(dpi0=mpi0;)dp0mx-1=inf;for(int j=1; j<(mx-1); j+)

7、(for(int i=1; i<n; i+)(if(j&(1<<(i-1)=0)(int x,y=inf;for(int k=1; k<n; k+)(if(j&(1<<(k-1)>0)x=dpk(j-(1<<(k-1)+mpik;y=min(y,x);) dpij=y;dp0mx-1=inf;for(int i=1;i<n;i+)dp0mx-1=min(dp0mx-1,mp0i+dpi(mx-1)-(1<<(i-1);printf("%dn",dp0mx-1);)return 0;)输入

8、输由截图OJ提交截图算法优化分析该算法需要对顶点集合1, 2,n-1的每一个子集进行操作,因此时 间复杂度为O(2M).和蛮力法相比,动态规划法求解TSP问题,把原来的时 间复杂度是O(n!)的排列问题,转化为组合问题,从而降低了算法的时间复 杂度,但仍需要指数时间.回溯法算法问题分析回溯法求解TSP问题,首先把所有的顶点的访问标志初始化为 0,然后在 解空间树中从根节点出发开始搜索,如果从根节点到当前结点对应一个局部 解,即满足上述约束条件,那么在当前结点处选择第一棵子树继续搜索,否那么,对当前子树的兄弟结点进行搜索,如果当前结点的所有子树都已尝试过并且 发生冲突,那么回溯到当前结点的父节点

9、.采用邻接矩阵mpnn存储顶点之 间边的情况,为预防在函数间传递参数,将数组mp设置为全局变量,设数组xn表示哈密顿回路经过的顶点.算法设计输入：无向图G=(V,E)输出：哈密顿回路1、 将顶点数组xn初始化为0,标志数组visn初始化为0;2、 从顶点0出发构造哈密顿回路：vis0=1;x0=1;k=1;3、 While(k>=1)3.1、 xk=xk+1 ,搜索下一个顶点.3.2、 假设n个顶点没有被穷举完,那么执行以下操作6 E,转步骤3.3 ;3.3、 假设数组xn已经形成哈密顿路径,那么输出数组 xn,算法结束；3.4、 假设数组xn构成哈密顿路径的局部解,那么 k=k+1,转

10、步骤3;3.5、 否那么,取消顶点xk的访问标志,重置xk,k=k-1 ,转步骤3实现代码#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <ctime>#include <iostream>#includealgorithm#include <string>#include <vector>#include <deque>#include <list>#include

11、<set>#include <map>#include <stack>#include <queue>#include <cctype>#include <numeric>#include <iomanip> #include <bitset>#include <sstream>#include <fstream>#define debug "output for debugn#define pi (acos(-1.0)#define eps (1e-8)#defi

12、ne inf 0x3f3f3f3f #define ll long long int#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1 using namespace std;int mp2020;int x30,vis30;int n,k,cur,ans;void init()for(int i=0;i<n;i+)for(int j=0;j<n;j+)mpij=-1;ans=-1;cur=0;for(int i=1;i<=n;i+)xi=i;void dfs(int t)i

13、f(t=n)(if(mpxn-1xn!=-1&&(mpxn1!=-1)&&(cur+mpxn-1xn+mpxn1<ans|ans=-1)(for(int i=1;i<=n;i+)visi=xi;ans=cur+mpxn-1xn+mpxn1;else(for(int i=t;i<=n;i+)(if(mpxt-1xi!=-1&&(cur+mpxt-1xi<ans|ans=-1)(swap(xt,xi);cur+=mpxt-1xt;dfs(t+1);swap(xt,xi);)int main()(while(scanf(&quo

14、t;%d",&n)(init();for(int i=1; i<=n; i+)(for(int j=1; j<=n; j+)(if(i=j)continue;scanf("%d",&mpij);)/puts("YES");dfs(2);cout<<ans<<endl;return 0;)输入输由截图OJ提交截图算法优化分析在哈密顿回路的可能解中,考虑到约束条件xi!=xj(1<=I,j<=n,i!=j),那么可能解应该是(1,2,n)的一个排列,对应的解空间树种至少有n!个叶 子结

15、点,每个叶子结点代表一种可能解.当找到可行的最优解时,算法停止.分支限界法算法问题分析分支限界法解决TSP问题首先确定目标函数的界down,up,可以采用贪 心法确定TSP问题的一个上界.如何求得TSP问题的一个合理的下界呢对 于无向图的代价矩阵,吧矩阵中每一行最小的元素想家,可以得到一个简单 的下界,但是还有一个信息量更大的下界：考虑一个TSP问题的完整解,在每条路径上,每个城市都有两条邻接边,一条是进入这个城市的,另一条是 离开这个城市的,那么,如果把矩阵中每一行最小的两个元素相加在除以2,假设图中所有的代价都是整数,再对这个结果向上取整,就得到一个合理的下界.需要强调的是,这个解可能不是

16、一个可行解(可能没有构成哈密顿回路),但给出了一个参考下界.一般情况下,假设当前已确定的路径为 U=(r1,r2,rk),即路径上已确定了 k个顶点,此时,该局部解的目标函数值的计算方法(限界函数)如下：Lb= (2Ecrir(i+1)+ Eri行不在路径上的最小元素+Eri行最小的两个元素)/2算法设计输入：图G=(V,E)输出：最短哈密顿回路1、 根据限界函数计算目标函数的下界 down;采用贪心法得到上界up;2、 计算根节点的目标函数值并参加待处理结点表PT;3、 循环知道某个叶子结点的目标函数值在表 PT中取得极小值3.1、 i=表PT中具有最小值的结点；3.2、 对结点i的每个孩子

17、几点x执行以下操作：4、将叶子结点对应的最优解输出,回溯求得最优解的各个分量.实现代码#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <iostream> #include <algorithm>#include <string>#include <vector>#include <deque>#include <list>#include <set>#in

18、clude <map>#include <stack>#include <queue>#include <cctype>#include <numeric>#include <iomanip>#include <bitset>#include <sstream>#include <fstream>#define debug "output for debugn#define pi (acos(-1.0)#define eps (1e-8)#define inf 0x3f3f3f

19、3f#define ll long long int#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1using namespace std;const int Max = 100005;/*/vector<int>Mp20;vector<int>二iterator it;int mp2020;int vis20;int up,low,n,ans;struct nodeint x20,st,ed,dis,val,num;bool operator<(const n

20、ode &p)constreturn val<p.val;priority_queue<node>q;int getup(int u,int v,int w)if(v=n) return w+mpu1;int sum=inf,p;for(int i=1; i<=n; i+)(if(!visi&&sum>mpui)(sum=mpui;p=i;visp=1;return getup(p,v+1,w+sum);int getlow()(int sum=0;for(int i=1; i<=n; i+)(it=Mpi.begin();sum+=

21、*it;it+;sum+=*it;return sum/2;int gao(node s)(int res=s.dis*2;int t1=inf,t2=inf;for(int i=1; i<=n; i+)(if(!s.xi)(t1=min(t1,mpis.st);t2=min(t2,mps.edi);)res+=t1;res+=t2;int tmp;for(int i=1; i<=n; i+)(tmp=inf;if(!s.xi)(it=Mpi.begin();res+=*it;for(int j=1; j<=n; j+)tmp=min(tmp,mpji);res+=tmp;r

22、eturn !(res%2) ? (res/2):(res/2+1);void bfs(node s)(q.push(s);while(!q.empty()(node head=q.top();q.pop();if(head.num=n-1)(int p;for(int i=1; i<=n; i+)if(!head.xi)p=i； break;)int cnt=head.dis+mpphead.st+mphead.edp;node tmp=q.top();if(cnt<=tmp.val)(ans=min(ans,cnt);return;)else(up=min(up,cnt);an

23、s=min(ans,cnt);continue;)node tmp;for(int i=1; i<=n; i+)(if(!head.xi)(tmp.st=head.st;tmp.dis=head.dis+mphead.edi;tmp.ed=i;tmp.num=head.num+1;for(int j=1; j<=n; j+) tmp.xj=head.xj;tmp.xi=1;tmp.val=gao(tmp);if(tmp.val<=up)q.push(tmp);int main()(while(scanf("%d",&n)(for(int i=0; i<=n; i+)Mpi.clear();for(int i=1; i<=n; i+)for(int j=