旅行商A星算法c语言程序

1、 1) 实验内容 “旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。旅行商问题在本实验中的具体化：从a城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。2) 实验目的 加深对a星算法的理解了解启发式图搜索策略3) a*算法中f(n)=g(n)+h(n)如何选取？ 对于某一已到达的现行状态, 如已到达图中的n节点, 它是否可能成为最佳路径上的一点的估价, 应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s 到任意一个节点n 的一条最佳路径上的实际耗散值。h*(n

2、)函数值表示从任意节点n 到目标节点ti 的最佳路径的实际耗散值。其中ti 是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n 到达目标节点ti的一条最佳路径的实际耗散值，并有f*(n)=g*(n)+h*(n)。 假设f 函数是对f* 函数的一种估计, 并有f(n)=g(n)+h(n)，其中g 函数是对g* 的估计，h 函数是对h* 的一种估计。f( n) 包括两个部分，其中g(n)表示到达n 节点时，已付出代价的估计；而h(n)表示从n 节点到达目标节点ti 将要付出代价的估计。按f(n)=g*(n)+h*(n)的值来排序ff 表的节点，f 值小者优先。通常称这种算法为a算

3、法。在a 算法的基础上，进一步限制h(n)函数，使得搜索图中的每一个节点n，能满足h(n)=h*(n)、称h 函数取h* 的下界。这种算法叫a* 算法。对ff里的每一个节点做评估函数f分为两部分g和h：假设从a城市走到x城市，又走到y城市，所以g可表示为：g = a到x的距离 + x到y的距离；未走的的城市数=（总城市数+1）-目前城市的层数。为什得加1，因为最后得走回初始城市，所以总路径的城市数为总城市数+1。h = 未走的城市数目前的最小距离；f = g + h ;计算ff表里每个节点的f值，f值最小的节点作为活路径，把它加到bestpath中。4) 完整的源代码 （加注释说明） #inc

4、lude stdio.hconst int max=9999;const int ax=50;int isbest(int i,int bestpath,int p)/检测改节点是否已经加入bestpath中 for(int k=1;k=p;k+)if(i=bestpathk)break;if(k!=p+1)/新测试节点在a中 return 1;elsereturn 0;void main() int min=max;int minf=max;int num;/城市数量int mataxax;/城市间距离int bestpathax;/最佳路径int f=0,g=0,h=0;int ffax;

5、/依次求每个城市的f值int ggax;/城市的g值printf(城市个数为：);scanf(%d,&num);printf(城市间的距离为：n);/输入各城市间距离的矩阵for(int i=0;inum;i+)for(int j=0;jnum;j+)scanf(%d,&matij); bestpath0=0;/起点为0，即城市afor(int p=0;pnum-1;p+)/依次求每个最优节点，每次循环得到一个新的最优城市放到bestpath中for(int kk=0;kknum;kk+)ffkk=max;/便于后面求最小值for(i=1;inum;i+)/起点a不算，从非起点开始找寻最优城市

6、if(isbest(i,bestpath,p)/该点已经在bestpath中的话，忽略continue;else/计算该点的g值ggi=g+matbestpathpi;/i点的g值 for(int m=0;mnum;m+)/开始计算h值 if(isbest(m,bestpath,p)/该点已经在bestpath中的话，忽略 continue;for(int t=m+1;tnum;t+)if(isbest(t,bestpath,p)continue;if(m!=0|t!=i|p=num-2)/不是最后一个点的话，不算a点到这个点长度if(matmtmin)min=matmt; h=min*(nu

7、m-p-1);/h值ffi=ggi+h;/第i个节点的f值min=max;/重新赋值最大，以便下次循环for(i=0;inum;i+)/找寻最优点，即f值最小者if(ffiminf)minf=ffi;bestpathp+1=i;minf=max;/重新赋值最大，以便下次循环g=g+matbestpathpbestpathp+1;/更新g值printf(最优路径为:); for(i=0;inum;i+) printf(%c ,bestpathi+65);printf(an);printf(总路程为:); int sum=0;for(i=0;inum-1;i+) sum=sum+matbestpa

8、thibestpathi+1;sum=sum+matbestpathnum-10;/总路程最后一个城市要回到a，所以加上其距离printf(%dn,sum);5) 实验运行过程截图6) 实验过程中遇到的问题 1. 程序刚写好问题还是挺多的，总是得不到正确的结果，程序不算大，但是循环比较多，所以发现错误还是挺难的，通过程序的分步执行，才逐渐发现错误所在，比如说 g值要及时的更新2. 循环的终点要确定，一开始运行时，一直崩溃。 问题出在if(m!=0|t!=i)这里，计算h值时，取余下路径时，假设现在bestpath中有ad现在在测试b点，那么ba不会在下面路径中走到，不用考虑，但是如果b是最后一个点，那么在剩下路径中只能走ba，必须考虑。所以在判定条件中必须添加一个 p=num-2，变成 if(m!=0|t!=i|p=num-2)，p=num-2就是在寻找回到a前的最后一个点7) 实验心得体会。 通过本次实验，我深入了解了一下a星算法，