人工智能技术.doc

1、人工智能技术.doc 人工智能技术 课程设计报告 学号： 姓名： 年 年 月 日 课程设计题目： 货郎担（旅行商）问题： 设有个城市，城市之间均有道路，一个旅行商从某城市出发，经过其余个城市一次且仅一次，最后回到出发的城市，他如何走才能使他所走的路程最短？ 用* * 算法实现，语言不限 算法 实现 ： 本程序使用*算法实现 *算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而*算法最为核心的部分，就在于它的一个估值函数的设计上： ()()() 其中()是每个可能试探点的估值，它有两部分组成：一部分为()，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树

2、中的深度来表示）。另一部分，即()，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。 一种具有()()()策略的启发式算法能成为*算法的充分条件是： ) 搜索树上存在着从起始点到终了点的最优路径。 ) 问题域是有限的。 ） 所有结点的子结点的搜索代价值。 ） ()*() （*()为实际问题的代价值）。 在 旅行商问题中 节点（）的代价起始城市到城的代价城到城的代价 其中的代价可以是距离，费用或者时间等 节点（ ）的启发值（城市总数已访问的城市数）* 所有两城之间的代价 在程序中的实现： ; *(); ; 其中() () () :起始城市到城的代价 :一个二维数组，城到城的代价

3、: 所有两城之间的代价 : 城市总数 :城市节点所处于搜索树的层次，和已访问的城市数同值 在本程序中 定义一个结构体用于表示城市节点： ; 值 值 值 ; 层 *父节点 *后继 *前驱 ; 定义一个结构体表示表和表 *; *; ; 其中 表用于存放扩展出来的节点 表用于在程序的末尾存放最佳路径 测试数据的输入使用邻接矩阵表示完全图 使用二维数组 存放 程序流程： 1 将数组中元素值置下标值： 2 按要求输入邻接矩阵 3 默认从第一个点开始搜索，并将，表示该点已被纳入路径 4 扩展刚刚被纳入路径的节点，扩展的方法为在数组中搜索值不为的元素，为之创建节点写入数据（包括值值值节点）并纳入表中 5 在

4、表中搜索值最小的节点确定为当前的最优路径点,并且将上一次的最优路径点所在的路径上所有节点的表中的元素值改为其下标值，表示删除原路径，同时将所在的路径上所有节点的表中元素值改为，表示创建新路径。 6 回第步循环，直至表中所有的元素值均为退出循环 7 由此获得最后一次的最优路径点，利用结构体中的指针得到最佳路径，并将路径存放在表中 8 输出最佳路径 9 程序退出。 程序缺陷 ： 由于专注于算法的实现，没有设置输入不合法的报错。 所以若要获得正确的结果，在输入路径点个数和邻接矩阵时要正确输入 程序截图 ：（以个路径点为例） 测试用例 ： 提供四组测试用例（邻接矩阵表示完全图），路径点个数分别是， 第

5、一组： 路径如下: 第二组： 路径如下: 第三组： 路径如下: 第四组： 路径如下: 心得体会： 在这次课程设计中，我第一次使用*算法，遇到的问题还是不少的 旅行商问题在以前接触过，当时解决的时候使用的是另外一种算法。 *算法中最让我头疼的地方就是()的设计，要满足()*(),在最初，我使用了 ()*(),出来的结果并不一定是最优路径，后来我发现问题处在上面，使用使得算法变得很简单，但也不完善，使得搜索树是一路往下走，没有了回溯的可能性，我将换成了，这样就可以满足()*()，使之得到正确的结果。 在写程序中，定义的表本来目的是存放每次搜索出来的当前最优路径点，后来发现因为不可避免出现算出的最优

6、路径点与前一个路径点不在同一分支上，造成回溯，所以放弃使用实时存放最优路径点，而是在结构体中增加了指针，利用该指针构成链表存放路径，并且在每次找到新节点的时候删除原路径，同时创建新路径。最终只要得到最优路径即可。 核心 代码： ; 值 值 值 ; 层 *父节点 *后继 *前驱 ; *; *; ; () 邻接矩阵 ; 路径点集合 ; 路径点的数目 ; 存放最大值,用于计算值 ; 存放最小值,用于计算值 ; 用于计数 输入路径点的数目：; ; () 用，.来表示路径点 () 输入邻接矩阵 () ; (); 初始化，使其为所有路径中的最大值 () () (); () ; 设置为所有路径中的最小值 *

7、 ; ; 点 ; 默认从第一个路径点开始搜索 ; ; ; 初始化表 *,*; *; *; ; ; 用于确定节点插入表的位置 () 对节点进行扩展，建立搜索树的第一层 插入节点 *; ; ; 第一层 点到其他点的距离 *(); ; ; ; ; ; ; ; (); 寻找最优路径点 (); ; 在中删除找到的路径点，因为下面将要对它进行扩展 ; ; ; 中不为的个数为未到达路径点 扩展找到的路径点（从第二层开始进入循环） () () () ; ()数组中所有元素均为,则退出 ; ; () () *; ; ; 由最优路径点的确定子节点的 ; *(); ; ; ; ; ; ; ; *; ; () 从表中寻找 (); 寻找最优路径点 (); ; ; 找到最优路径点 上一次的最优路径点 () 撤销上一次路径 ; ; 新找