旅行商问题的a算法实现

《旅行商问题的a算法实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、用A*算法解“旅行商问题”“旅行商问题”的A*算法实现学号：040330624姓名：李祥班级：0403306班日期：2007年1月15日指导老师：徐敏南京航空航天大学计算机科学与技术专业-8-用A*算法解“旅行商问题”一、问题描述货郎担（旅行商）问题：设有n个城市，城市之间均有道路，一个旅行商从某城市出发，经过其余n-1个城市一次且仅一次，最后回到出发的城市，他如何走才能使他所走的路程最短？用A*算法实现，语言不限。二、算法A*算法是基于估价函数f(x)的一种加权状态图启发式搜索算法。A*算法的核心是估价函数f(

2、n)，它包括g(n)和h(n)两部分。g(n)是已经走过的代价，h(n)是n到目标的估计代价。A算法限制其估价函数中的启发函数h(x)满足：对所有的节点x均有h(x)≤h*(x)，其中h*(x)是从节点x到目标节点的最小代价(若有多个目标节点则为其中最小的一个)。A*算法的具体步骤如下：步1把附有f(S0)的初始节点S0放入OPEN表；步2若OPEN表为空，则搜索失败，退出。步3移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2

3、；步6扩展N，生成一组附有f(x)的子节点，对这组子节点作如下处理：（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”；（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)值升序排序，转步2。下面为A*算法的伪代码：AStar(){Open=[起始

4、节点]；Closed=[]；while(Open表非空){从Open中取得一个节点X，并从OPEN表中删除；if(X是目标节点){求得路径PATH；返回路径PATH；}for(每一个X的子节点Y){if(Y不在OPEN表和CLOSE表中){求Y的估价值；并将Y插入OPEN表中；}//还没有排序elseif(Y在OPEN表中)-8-用A*算法解“旅行商问题”{if(Y的估价值小于OPEN表的估价值){更新OPEN表中的估价值；}else{将Y插入OPEN表中；}}else//Y在CLOSE表中{if(Y的估价值小于

5、CLOSE表的估价值){更新CLOSE表中的估价值；从CLOSE表中移出节点，并放入OPEN表中；}else{将Y插入OPEN表中；}}}//endfor将X节点插入CLOSE表中；按照估价值将OPEN表中的节点排序；}//endwhile}//endfunc三、测试用例1、用两个城市测试，如下图：-8-用A*算法解“旅行商问题”经过运行后找到最佳路径如下图所示：-8-用A*算法解“旅行商问题”2、用四个城市测试，如下图：经过运行后找到最佳路径如下图所示：-8-用A*算法解“旅行商问题”3、用五个城市测试，如下图

6、：-8-用A*算法解“旅行商问题”经过运行后找到最佳路径如下图所示：-8-用A*算法解“旅行商问题”从以上三个例子我们可以看出，本程序正确无误。四、心得体会1．通过本实验，我深该地掌握了A*算法，弄清A算法与A*算法的区别与联系，弄清了启发式算法较之盲目搜索算的优点。2．懂得算法不等于就能够写出算法对应的程序。算法是思想，要想把思想转化为程序，不仅要求对算法能够深刻地理解，还要能够把算法抽象成程序能如表示的方法（如设计相应的数据结构）。因此，实现算法，既是对算法理解加深的过程，又是提高程序设计能力的过程。五、源程

7、序本程序使用MFC7.0编写，项目名为TravelerField。所有源代码位于同文件夹的TravelerField项目中。-8-