人工智能技术.docx
人工智能技术.doc人工智能技术课程设计报告学号：姓名：年 年 月 日 课程设计题目：货郎担（旅行商）问题：设有个城市，城市之间均有道路，一个旅行商从某城市动身，经过其余个城市一次且仅一次，最终回到动身的城市，他如何走才能使他所走的路程最短？用* * 算法实现，语言不限算法 实现 ：本程序运用*算法实现 *算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而*算法最为核心的部分，就在于它的一个估值函数的设计上：()()() 其中()是每个可能摸索点的估值，它有两部分组成：一部分为()，它表示从起始搜寻点到当前点的代价（通常用某结点在搜寻树中的深度来表示）。另一部分，即()，它表示启发式搜寻中最为重要的一部分，即当前结点到目标结点的估值。一种具有()()()策略的启发式算法能成为*算法的充分条件是：)搜寻树上存在着从起始点到终了点的最优路径。)问题域是有限的。 ）全部结点的子结点的搜寻代价值>。 ）()<*() （*()为实际问题的代价值）。 在 旅行商问题中节点（）的代价起始城市到城的代价城到城的代价 其中的代价可以是距离，费用或者时间等节点（… ）的启发值（城市总数已访问的城市数）* 全部两城之间的代价在程序中的实现：>>>>*(>);>>>其中() () () > >:起始城市到城的代价>:一个二维数组，城到城的代价 : 全部两城之间的代价 : 城市总数 > >:城市节点所处于搜寻树的层次，和已访问的城市数同值在本程序中 定义一个结构体用于表示城市节点：;值值值; 层 *父节点 *后继 *前驱 ; 定义一个结构体表示表和表 *;*; 其中 表用于存放扩展出来的节点 表用于在程序的末尾存放最佳路径 测试数据的输入运用邻接矩阵表示完全图 运用二维数组 存放 程序流程：1 将数组中元素值置下标值： 2 按要求输入邻接矩阵 3 默认从第一个点起先搜寻，并将，表示该点已被纳入路径 4 扩展刚刚被纳入路径的节点，扩展的方法为在数组中搜寻值不为的元素，为之创建节点写入数据（包括值值值节点）并纳入表中 5 在表中搜寻值最小的节点确定为当前的最优路径点,并且将上一次的最优路径点所在的路径上全部节点的表中的元素值改为其下标值，表示删除原路径，同时将所在的路径上全部节点的表中元素值改为，表示创建新路径。6 回第步循环，直至表中全部的元素值均为退出循环 7 由此获得最终一次的最优路径点，利用结构体中的指针得到最佳路径，并将路径存放在表中 8 输出最佳路径 9 程序退出。程序缺陷 ：由于专注于算法的实现，没有设置输入不合法的报错。所以若要获得正确的结果，在输入路径点个数和邻接矩阵时要正确输入 程序截图 ：（以个路径点为例）测试用例 ： 供应四组测试用例（邻接矩阵表示完全图），路径点个数分别是， 第一组：路径如下: >>>> 其次组：路径如下: >>>>> 第三组：路径如下: >>>>> 第四组：路径如下: >>>>>> 心得体会：在这次课程设计中，我第一次运用*算法，遇到的问题还是不少的旅行商问题在以前接触过，当时解决的时候运用的是另外一种算法。*算法中最让我头疼的地方就是()的设计，要满意()<*(),在最初，我运用了 ()*(>),出来的结果并不肯定是最优路径，后来我发觉问题处在上面，运用使得算法变得很简洁，但也不完善，使得搜寻树是一路往下走，没有了回溯的可能性，我将换成了，这样就可以满意()<*()，使之得到正确的结果。在写程序中，定义的表原来目的是存放每次搜寻出来的当前最优路径点，后来发觉因为不行避开出现算出的最优路径点与前一个路径点不在同一分支上，造成回溯，所以放弃运用实时存放最优路径点，而是在结构体中增加了指针，利用该指针构成链表存放路径，并且在每次找到新节点的时候删除原路径，同时创建新路径。最终只要得到最优路径即可。核心 代码： ; 值 值 值 ; 层*父节点*后继*前驱 ; *;*;() 邻接矩阵 ; 路径点集合 ; 路径点的数目 ;存放最大值,用于计算值 ; 存放最小值,用于计算值 ; 用于计数<<" 输入路径点的数目：">>(<) 用，.来表示路径点(<)输入邻接矩阵 (<) >>(>); 初始化，使其为全部路径中的最大值(<) (<) (); (>); 设置为全部路径中的最小值*;>>点>默认从第一个路径点起先搜寻;>>初始化表*,*;*; *;用于确定节点插入表的位置(<)对节点进行扩展，建立搜寻树的第一层插入节点 *; ; > >第一层 >点到其他点的距离 >*(>); >>> > > > > > ; (); 找寻最优路径点(>>>); ;在中删除找到的路径点，因为下面将要对它进行扩展>>>>>>>中不为的个数为未到达路径点扩展找到的路径点（从其次层起先进入循环）() (<) () ; ()数组中全部元素均为,则退出 >(<) () *;>>>由最优路径点的确定子节点的>>>>*(>);>>>>>>>> *> ; () 从表中找寻();找寻最优路径点 (>>>);> 找到最优路径点 上一次的最优路径点 () 撤销上一次路径>>> 新找到的最优路径点 () 重配置新路径>> 再次使得指向最优路径点，为下一次所用 在中删除找到的路径点>>> >>>循环结束初始化表;>>*;()将路径依次存入表中 > > > > ; >省略输出 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第17页 共17页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页第 17 页 共 17 页
