a 算法实现旅行商问题 人工智能报告，付代码

《a 算法实现旅行商问题 人工智能报告，付代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、A算法实现旅行商问题人工智能报告，付代码一、问题描述"旅行商问题"常被称为"旅行推销员问题"，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。旅行商问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。二、知识表示1、A*算法概述A*算法是N.Nillson于1971年提出的一种有序搜索算法,该算法被认为是求解人工智能问题的最成功的技术理论之一。Nillson指出对于某一已

2、到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设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*的

3、一种估计。f(n)包括两个部分，其中g(n)表示到达n节点时，已付出代价的估计；而h(n)表示从n节点到达目标节点ti将要付出代价的估计。按f(n)=g*(n)+h*(n)的值来排序OPEN表的节点，f值小者优先。通常称这种算法为A算法。在A算法的基础上，进一步限制h(n)函数，使得搜索图中的每一个节点n，能满足h(n)=h*(n)、称h函数取h*的下界。这种算法叫A*算法。2、A*算法的状态所谓状态,是指在一定的时空范围内，问题所涉及的人、物、时间等的布局关系。通常把问题的初始布局关系称为初始状态，问题解决时到达的状态叫

4、目标状态。这两个状态之间存在差异，如何从初始状态到达目标状态就是对问题求解。在状态空间法中问题的求解通常是从初始状态到达目标状态的一条最佳路径，这条路径依靠搜索算法在状态空间中寻找，这就是状态空间法的核心所在。在旅行商问题中，初始状态就是旅行商在A城市准备出发送货，目标状态就是旅行商将所有的货送出归来到A城市。状态空间就是旅行商可以走的所有路径，本实验的解就是最短距离的路径。3、估计函数的意义对于某一已到达的现行状态,假设现在的现行状态是从A走到C(一共五个城市，需走过B、C、D、E)，那么下面可以走B、D、E，如果继续走

5、B就表示为A-C-B，那么在OPEN表里，即可选定活路径就有六种选择：(1)A-C-B'；(2)A-C-D'；(3)A-C-E'；(4)A-B；(5)A-D；(6)A-E。为什么有的是B、B'?在这里B的层数是2层，就是第二步走的是B；而B'的层数是3层，就是第三步走的是B。在OPEN表了的一个节点代表一条路径，而非简单的代表一个城市结点，所以在里面你会看到不同B的表现形式。对OPEN里的每一个节点做评估函数F分为两部分G和H：G=未走的城市数×目前的最小距离；未走的的城市数=(总城市数+1)-目前城市的层数。为什得加1，

6、因为最后得走回初始城市，所以总路径的城市数为总城市数+1。假设从A城市走到X城市，又走到Y城市，所以H可表示为：H=A到X的距离+X到Y的距离；F=G+H；计算OPEN表里每个节点的F值，F值最小的节点作为活路径，从OPEN表中删除，放到CLOSE表里。三、算法实现1、数据结构typedefstruct_node{intf；//f值intg；//g值inth；//h值intlevel；//第几次走到这个点(important)intparent；//父城市；intcity；//citynum；}node；使用node结构体

7、表述每一个城市。typedefstruct_list{struct_list*next；struct_list*pre；struct_list*parent；//父城市节点指针nodecity_node；}nodelist,*nodeptr；使用nodelist,*nodeptr描述路径，城市结点与城市结点的关系。typedefstruct_ttable{struct_ttable*_this；//this指针nodelistopen；//open表,nodelistclose；//close表,(仓库)//一些操作nod

8、eptr(*add_to_open)(int)；nodeptr(*find_least_f)(void)；void(*move_to_close)(nodeptrptr)；void(*print_path)(nodeptrptr)；}ttable；Ttable相当一个总表，相当于面向对象的一个类，成员变