《旅行商A星算法C语言程序》由会员分享，可在线阅读，更多相关《旅行商A星算法C语言程序（4页珍藏版）》请在金锄头文库上搜索。
1、1)1)实验内容实验内容 “旅行商问题”常被称为“旅行推销员问题” ，是指一名推销员要拜访多个地点时，如何找到 在拜访每个地点一次后再回到起点的最短路径。 旅行商问题在本实验中的具体化：从 A 城市出发，到达每个城市并且一个城市只允许访问一次， 最后又回到原来的城市，寻找一条最短距离的路径。 2)2)实验目的实验目的 加深对 A 星算法的理解 了解启发式图搜索策略 3)3)A*A*算法中算法中 f(n)=g(n)+h(n)f(n)=g(n)+h(n)如何选取？如何选取？ 对于某一已到达的现行状态, 如已到达图中的n节点, 它是否可能成为最佳路径上的一点的 估价, 应由估价函数 f(n)值来决定
2、。假设 g*(n)函数值表示从起始节点 s 到任意一个节点 n 的 一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点 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)表
3、示从 n 节点到达目标节点 ti 将要付出代价的估计。 按 f(n)=g*(n)+h*(n)的值来排序 ff 表的节点， f 值小者优先。 通常称这种算法为 A 算法。 在 A 算 法的基础上， 进一步限制 h(n)函数， 使得搜索图中的每一个节点 n， 能满足 h(n)=h*(n)、 称 h 函 数取 h* 的下界。这种算法叫 A* 算法。 对 ff 里的每一个节点做评估函数 F 分为两部分 G 和 H： 假设从 A 城市走到 X 城市，又走到 Y 城市，所以 G 可表示为： G G = = A A 到到 X X 的距离的距离 + + X X 到到 Y Y 的距离；的距离； 未走的的城市数=
4、（总城市数+1）-目前城市的层数。为什得加 1，因为最后得走回初始城市，所 以总路径的城市数为总城市数+1。 H H = = 未走的城市数未走的城市数目前的最小距离；目前的最小距离； F = G + H ; 计算 ff 表里每个节点的 F 值，F 值最小的节点作为活路径，把它加到 bestpath 中。 4)4)完整的源代码完整的源代码 （加注释说明）（加注释说明） #include stdio.h const int max=9999; const int ax=50; int isbest(int i,int bestpath,int p)/检测改节点是否已经加入 bestpath中 fo
5、r(int k=1;k=p;k+) if(i=bestpathk) break; if(k!=p+1)/新测试节点在 a中 return 1; else return 0; void main() int min=max; int minf=max; int num;/城市数量 int mataxax;/城市间距离 int bestpathax;/最佳路径 int f=0,g=0,h=0; int ffax;/依次求每个城市的 f 值 int ggax;/城市的 g 值 printf(城市个数为：); scanf(%d, printf(城市间的距离为：n);/输入各城市间距离的矩阵 for(i
6、nt i=0;inum;i+) for(int j=0;jnum;j+) scanf(%d, bestpath0=0;/起点为 0，即城市 A for(int p=0;pnum-1;p+)/依次求每个最优节点，每次循环得到一个新的最优城市放到 bestpath中 for(int kk=0;kknum;kk+) ffkk=max;/便于后面求最小值 for(i=1;inum;i+)/起点 A 不算，从非起点开始找寻最优城市 if(isbest(i,bestpath,p)/该点已经在 bestpath中的话，忽略 continue; else/计算该点的 g 值 ggi=g+matbestpath
7、pi;/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*(num-p-1);/h 值 ffi=ggi+h;/第 i 个节点的 f 值 min=max;/重新赋值最大，以便下次循环 for(i=0;
8、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+matbestpathibestpathi+1; sum=sum+matbestpathnum-10;/总路程
9、最后一个城市要回到 A，所以加上其距离 printf(%dn,sum); 5)5)实验运行过程截图实验运行过程截图 6)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)7)实验心得体会。实验心得体会。 通过本次实验，我深入了解了一下 A 星算法，从算法到程序的实现还是有点困难的 ，尤其 对 F,G,H 的理解实现在学习了解的过程中慢慢弄懂，理解启发式图搜索策略的好处，启发式实际 上就是途程构建法和途程改善法的结合，能够更优的解决问题。除此之外，我感到还要加强编程 能力的培养。 教师评价优良中及 格 不 及 格 教师 签名 日 期
